算法2 - 冒泡排序

算法说明

上篇文章我们做了一个简单的桶排序，其基本思想就是申请足够大的空间来存放我们需要排序的数字，这个方法有一个弊端就是，非常浪费空间。例如需要排序的数字范围是0-1000000之间，我们则需要申请a[1000001]个空间，但是你可能只是排序几个数字而已。为了解决这个问题，我们有了一种新的排序方法：冒泡排序。

冒泡排序的基本思想就是：每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。

算法代码

我们先上代码，之后进行说明。

void bubble_sort() {
    int a[100],i,j,t,n;
    scanf("%d",&n); // 输入一个数字，表示接下来有n个数
    for (i = 1; i <= n; i++) {
        scanf("%d",&a[i]); // 循环读入数字到数组中
    }
    // 冒泡排序的核心部分
    for (i = 1; i <= n-1; i++) { // 对于n个数字，只需要循环n-1次
        for (j = 1; j <= n-i; j++) {    // 从第一位开始比较知道最后一个尚未归位的数字
            if (a[j] < a[j+1]) {
                t       = a[j];
                a[j]    = a[j+1];
                a[j+1]  = t;
            }
        }
    }
    
    for (i = 1; i <= n; i++) {
        printf("%d ",a[i]);
    }
}

算法说明

例如我们需要对12,35,99,18,76这几个数字从大到小排序。也就是说我们的核心思想就是:越小的数字越靠后。

1. 第一步比较第一位和第二位，发现12，比35小，交换这两个数的位置，交换后的排序35,12,99,18,76。然后继续比较第二位和第三位，发现12比99小，继续交换位置，交换后的排序35，99，12，18，76。继续第三位和第四位比较，发现12比18小，交换位置，交换后顺序为35，99，18，12，76。再次第四位和第五位比较，发现12比76小，交换位置，交换后顺序为35，99，18，76，12。经过5-1次我们发现最后一位已经是最小的数字了。这里我们只是把5个数字中的最小的一个归位了。
2. 第二趟我们只需要对5位中的前4位进行对比就行。排序后的顺序为99，35，76，18，12
3. 第三趟我们只需要对前三位进行排序。排序后的顺序为99，76，35，18，12。
4. 第四趟我们需要对前两位进行排序。排序后的顺序为99，76，35，18，12。
   至此我们已经排序完成
   冒泡排序的核心算法是双重掏钱循环，不难看出冒泡排序的时间复杂度是O(N²)