程序员面试系列——冒泡排序

比眉伴天荒 2022-06-12 11:22 182阅读 0赞

虽然冒泡排序是排序算法里面最简单的一种，但是不可轻视。我在应届生的面试和社招的面试中，都被问到了冒泡排序。

基本思想：冒泡排序属于蛮力法，它比较表中的相邻元素，如果它们是逆序的话就交换它们的位置。重复多次后，最终，最大的元素就“冒”到列表的最后一个位置。第二遍操作将第二大的元素“冒”出来。这样一直重复，直到`n-1`遍（列表共有n个元素）以后，该列表就排序好了。

以n=4为例，示意图如下。

![这里写图片描述][SouthEast]

C语言代码如下：

void swap(int *a, int *b)
    {
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    //arr是数组首地址，len是数组长度
    void bubble_sort(int *arr, int len)  
    {
        int i;
        int j;
        for(i=0; i<len-1; ++i)
        {
            for(j=0; j<len-1-i; ++j)
            {
                if(arr[j] > arr[j+1])   //从左至右按非降序排列
                {
                    swap(arr+j, arr+j+1);
                }
            }       
        }
    }

以上的`void bubble_sort(int *arr, int len)`函数是非常主流的写法，还有一种版本的写法如下。

void bubble_sort(int *arr, int len)
    {
        int start;
        int end;
    
        for (end=len-1; end>0; end--) 
        {
            for (start=0; start<end; ++start) 
            {
                if(arr[start] > arr[start+1])
                    swap(arr+start, arr+start+1);       
            }
        }
    }

这种写法的示意图如下。

![这里写图片描述][SouthEast 1]

【完】

[SouthEast]: /images/20220612/1033a4deff4e412fb19d9d2fdf512063.png
[SouthEast 1]: /images/20220612/5b8b6dfacbe646548e2a5e1ec2291555.png