从冒泡排序到模拟 qsort 函数——排序算法初探

冒泡排序：最经典的排序算法

假设有一个包含十个元素的整型数组，初始状态为完全逆序。现在，我们需要将其按升序重新排列。

如果我们使用冒泡排序，其逻辑如下：

首先让最左边的数字和他右边的数字比较：9>8，将 9 和 8 互换位置：

让 9 继续和他右边的数字比较，再互换位置：

以此类推，9 不断比较、移动，最后到达最右边。这样，我们就让最大的数字放在了正确的位置：

然后是 8，接下来是 7、6、5……直到最后，数列变成 0, 1, 2, 3, 4, 5, 6, 7, 8, 9。

我们将一个数字通过不断和他右边的数字'比较，移动'，直到这个数字到达它基于升序排序应该到达的位置，这一整个过程称为'一趟'。将每一个数字的一趟中的每一次移动称为'一次'。

那么，冒泡排序函数应该是这样的：

arr表示接收数组首元素的地址，sz是数组元素个数。

变量 i 表示趟数：一共有 sz-1 趟。因为有 sz 个数字，而将前 sz-1 个数字全部排好后，最后一个数字默认到达了他应该在的位置。

变量 j 表示次数：每一趟有 sz - 1 - i 次。因为某一个数字在考虑最坏的情况下，他可能要移动到数列的最后一个，即他后面有几个数字就移动几次。紧接着第二趟（此时 i+1），同样在考虑最坏的情况下，他后面有几个数字就要移动几次但是要去掉目前最后一个数字。第一趟额外减 0，第二趟额外减 1，这与 i 的变化完全一致，所以使用 sz - 1 - i 来说明每趟需要的次数。

呈现一下源代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#

  
{
     i = ;
     (i = ; i < sz - ; i++)
    {
         j = ;
         (j = ; j < sz -  - i; j++)
        {
             (arr[j] > arr[j + ])
            {
                 tmp = arr[j];
                arr[j] = arr[j + ];
                arr[j + ] = tmp;
            }
        }
    }
}

 
{
     i;
     (i = ; i < sz; i++)
    {
        (, arr[i]);
    }
}

 
{
     arr[] = { ,,,,,,,,, };
     sz = (arr) / (arr[]);
    bubble_sort(arr, sz);
    print_arr(arr, sz);
     ;
}