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

ARM 108浏览

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

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

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

这里写图片描述

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);       
        }
    }
}

这种写法的示意图如下。

这里写图片描述

【完】