经典十大排序算法的总结与实现_各种排序算法的实现实验小结

排序算法相关概念

经典的排序算法

经典的十大排序算法包括：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序，本文将在后面对其原理和实现做详细说明。

排序算法的稳定性

在一个待排序的序列中，如果有两个元素 R[i] 和 R[j]，它们排序码 k[i] == k[j]，如果在排序前，元素 R[i] 排在 R[j]前面，如果在排序之后，元素 R[i] 仍在元素 R[j] 的前面，那么就认为这个排序算法是稳定的，否则称这个排序算法是不稳定的。稳定和不稳定的排序都有各自适应的场景，对于某些应用来说这些特性是非常关键的。

内部排序和外部排序

在排序中，如果排序的元素全部放在内存中排序，称为内部排序；反之，由于排序期间元素个数太多，不能全部放在内存中的排序，而是通过排序的要求不断在内存、外存之间移动的排序，称为外排序。

比较和非比较类排序

比较排序：常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。也就是在排序的最终结果里，元素之间的次序依赖于它们之间的比较，每个数必须和其他数进行比较，才能确定自己的位置。比较类的排序的优势是适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说比较排序适用于一切排序的情况。

非比较排序：常见的计数排序、基数排序、桶排序则属于非比较类排序。非比较类排序只要确定每个元素之前的已有元素个数即可，所有一次遍历即可解决，算法时间复杂度是O(n)，但是由于非比较类排序需要占用空间来确定唯一位置，所以是一种空间换时间的方法，对数据规模和数据分布也有一定要求。

排序的性能评估

排序算法的执行时间是衡量算法好坏的最重要的参数。排序的时间开销可用算法执行中的数据比较次数、数据移动次数衡量，一般都是按算法的平均情况来估算。而受到那种排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。同时算法执行所需的额外存储也需要考虑。

十大排序算法的思想与实现

冒泡排序

基本思想：

首先待排序的元素序列共有 n 个元素，每一趟都是从第一个元素开始，依次与后一个元素比较，如果前一个元素的排序码大于后一个元素（或小于），则将这两个元素交换，直到每趟排序的最大交换位置（每次循环最多只需要循环下标 0 ~ n-i-1 即可，因为后面的元素已经是有序的了），这称之为一趟冒泡，正是因为每一趟都将该趟的最大的（或最小的）元素移动到最后的合适位置，所以才被称为冒泡排序。共有 n 个元素，只需要做 n-1 趟冒泡，其次需要优化的地方是：1. 如果一趟冒泡没有元素交换，我们就可以认为剩下的全部的元素已经排好序，就不需要再进行排序，只需要加一个标志判断即可。2. 同时每一趟冒泡即使发生了元素交换，但不一定每个位置都发生交换，我们只需要记住该趟元素发生交换的位置 p，下一趟只需要循环下标 0~p 即可，因为如果只有前几个元素是无序的，而后几个本身是有序的，后几个元素就不需要在进行对比了。

代码实现：

//冒泡排序
void BubbleSort(int *arr, int size)
{
    if (!arr || size == 0)
        return;
    int pos = size - 1; //标记每趟排序的最大交换位置
    int swap_pos;   //记下元素发生交换的位置
    int swap_flag;  //每一趟是否发生过交换
    int i;
    int j;

    for (i = 0; i < size - 1; ++i) //排序的趟数，共size-1趟
    {
        swap_flag = 0;            //每一趟比较之前将flag标志先置为0
        for (j = 0; j < pos; ++j) //每趟只比较到最大交换位置
        {
            if (arr[j] > arr[j + 1])
            {
                std::swap(arr[j], arr[j + 1]);
                swap_flag = 1; //某一趟的比较中元素发生了交换需要记下来
                swap_pos = j;  //记下元素发生交换的位置
            }
        }
        pos = swap_pos;
        if (!swap_flag) //一趟下来无元素交换，说明已经有序
            return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

算法分析：

冒泡排序是稳定的排序算法，最好情况下的时间复杂度为 O(n)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(n^2)。

插入排序

插入排序的基本思想是每一步将一个待排序的元素，按照其排序码大小，插入到前面已经排好序的一组元素的适当位置上，直到所有的元素全部插入为止。可以选择不同的方法在已经排好序的有序数据表中寻找插入位置。以查找方法的不同，有多种插入排序的方法。

直接插入排序

基本思想：

当插入第 i 个元素时，前面第 0 ~ i-1 个元素已经排好序。这时用第 i 个元素的排序码与第 i-1, i-2, i-3, … 的排序码顺序进行比较，找到要插入的位置将第 i 个元素插入，然后将原来位置上的元素依次向后移动。

这里有个优化点：逐个与之前的有序的排序码进行比较，如果整个待排序的元素序列是无序性的，如果元素太多，比较效率比较低，可以采用折半查找的方法。但是如果待排序的元素序列本身接近有序，直接插入的比较次数可能比折半插入的更少，我们在下面将会介绍折半插入，这里先介绍直接插入排序的方法。

代码实现：

//直接插入排序
void InsertSort(int *arr, int size)
{
    if (!arr || size == 0)
        return;
    int i;
    int j;
    int temp;
    for (i = 1; i < size; ++i)
    {
        if (arr[i] < arr[i - 1]) //如果第i个元素和前面的已排序的最后一个元素反序时,才开始移动
        {
            temp = arr[i];                                //记住这个反序的元素的值
            for (j = i - 1; j >= 0 && arr[j] > temp; --j) //将之前比第i个元素大的所有元素统一向后移动
            {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = temp; //在条件不满足之前--j，最终需要在j+1处放入temp
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法分析：

直接插入排序是稳定的排序算法，最好情况下的时间复杂度为 O(n)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(n^2)。

折半插入排序

基本思想：

在直接插入排序中，当已排好序的元素非常多，而且整个待排序的元素序列有很强的无序性，在有序区中寻找插入位置比较的次数太多，会降低效率，而采用折半查找的方法找到要插入的位置，可以明显加快查找效率，但是找到位置后，还是一样需要将之后的有序的元素向后移动而且其处理和直接插入排序相同，仅仅是提升了查找效率。

代码实现：

//折半插入排序
void BinaryInsertSort(int *arr, int size)
{
    if (!arr || size == 0)
        return;
    int i;
    int j;
    int temp;
    int low, high, mid;
    for (i = 1; i < size; ++i)
    {
        if (arr[i] < arr[i - 1])
        {
            temp = arr[i];
            //进行有序元素的二分查找
            low = 0;
            high = i - 1;
            while (low <= high)
            {
                mid = (low + high) / 2;  //13,15,17
                if (temp < arr[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } //找到位置high
            for (j = i - 1; j >= high + 1; --j) //将之前比第i个元素大的所有元素统一向后移动
            {
                arr[j + 1] = arr[j];
            }
            arr[high + 1] = temp; //在high+1处放入temp
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

算法分析：

折半插入排序是稳定的排序算法，最好情况下的时间复杂度为 O(n)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(n^2)。

希尔排序

基本思想：

希尔排序也是一种插入排序，又被称为缩小增量排序。在效率上相较于其他插入排序有较大的改进。

基本思想：若待排序的元素序列有 n 个元素，取一个整数 d < n 作为间隔（也成为增量值），将全部元素分为 d 个子序列，所有距离为 d 的元素放在同一个子序列中。在每一个子序列中分别进行直接插入（例如，待排序元素有 10 个，若 d 取值为 5，则将整个元素分为 5 个子序列，每个子序列中有两个元素，而且这两个元素之间的间隔为 5，然后对这 5 个子序列先进行插入排序）。然后再缩小间隔 d，例如取 d = d/2，重复上面所述的子序列划分和排序过程，直到最后取 d == 1，将所有元素放在同一个序列中排序为止。

由于开始 d 的取值较大，每个子序列中的元素较少，排序速度较快。到了排序后期，d 的取值逐渐变小，子序列中的元素个数逐渐变多，但是由于前面工作的基础，大多数元素已基本有序，所以排序速度仍然非常快。

代码实现：

//希尔排序
void ShellSort(int *arr, int size)
{
    if (!arr || size == 0)
        return;
    int i, j;
    int temp;
    int d = size / 2; //增量初始值
    while (d > 0)     //每次循环较小增量
    {
        //从增量d开始，也就是相当于直接插入排序中的从下标为1的元素开始
        //后面的逐个元素都是与它所在子序列的元素进行比较，也就是每间隔d个所处的元素
        for (i = d; i < size; ++i)
        {
            temp = arr[i];
            //对间隔d位置的子序列进行直接插入排序操作
            for (j = i - d; j >= 0 && temp < arr[j]; j -= d)
            {
                arr[j + d] = arr[j];
            }
            arr[j + d] = temp;
        }
        d = d / 2; //减小增量
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

算法分析：

增量 d 的取法有各种方案，最初 Shell 提出取 d = n/2，d = d/2，直到 d = 1，但是由于直到最后一步，在奇数位置的元素才会和偶数位置的元素进行比较，这样使得这个序列的效率将很低。后来 Knuth 提出取 d = d/3 +1。还有人提出都取奇数好，也有人提出取质数好。不同的序列对希尔排序算法的性能影响很大，但是有些序列的效率会明显很高，例如：1，8，23，77，281，1073，4193，16577 … 。

希尔排序的时间复杂度分析很困难，因为受到增量选择的依赖关系，现在还没有人能够给出完整的数学分析。但是通过大量的实验统计资料得出当 n 很大，排序码的比较次数和元素平均移动次数大约在 n^1.25 ~ 1.6n^1.25 范围内，

总的来说，希尔排序是一种不稳定的排序算法，平均时间复杂度约为 O(n^1.3)。

选择排序

基本思想：

每一趟（第 i 趟，i = 0, 1, … , n-2）默认未排序区的首个元素是最小，在后面 n - i 个待排序元素中选出排序码最小的元素，作为有序元素的第 i 个元素（也就是当前未排序的首个元素和选出的最小元素交换），待到第 n -2 趟作完，待排序元素只剩下一个元素已经有序了，不需要再选择。

代码实现：

//选择排序
void SelectSort(int *arr, int size)
{
    if (!arr || size == 0)
        return;
    int i, j;
    int minIndex;
    for (i = 0; i < size - 1; ++i)
    {
        minIndex = i;
        for (j = i + 1; j < size; ++j)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        if (minIndex != i)
            std::swap(arr[i], arr[minIndex]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

算法分析：

选择排序是不稳定的排序算法，最好情况下的时间复杂度为 O(n^2)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(n^2)。

快速排序

算法思想：

快速排序也叫做分区排序（采用分治法），是目前应用最广泛的排序算法。基本思想是任取待排序元素序列中的某个元素作为基准（一般取第一个元素）作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列，左侧子序列中所有元素的排序码都小于这个基准元素的排序码，右侧子序列中所有元素的排序码都大于等于基准元素的排序码，而基准元素则排在这两个子序列的中间（这也是该元素最终应该安放的位置，也就是说这个基准元素相对所有元素来说就处于最终排序后的所在的位置），然后我们重复上面的方法过程，直到划分的子序列的长度为 0 或 1（递归出口），也就是所有的元素都排在相应的位置上为止。

代码实现：

//快速排序
void QuickSort(int *arr, int left, int right)
{
    if (!arr)
        return;
    if (left < right)
    {
        int low = left; //最后还要用传入的left和right的值其不能变，所以使用low和high
        int high = right;
        int pivot = arr[left]; //基准值
        while (low < high)
        {
            while (low < high && arr[high] >= pivot)
            {
                --high;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot)
            {
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[high] = pivot;

        QuickSort(arr, left, low - 1);
        QuickSort(arr, low + 1, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

快速排序是不稳定的排序算法，最好情况下的时间复杂度为 O(nlogn)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(nlogn)。

堆排序

堆的概念：

堆，非为大根堆和小根堆，是顺序存储的完全二叉树，并且满足以下特征之一：

1. 任意非终端结点关键字不小于左右子节点（大堆），Ki ≥ K2i+1 且 Ki ≥ K2i+2，其中 0 ≤ i ≤ (n-1)/2，n 是数组元的的个数。
2. 任意非终端结点关键字不大于左右子节点（小堆），Ki ≤ K2i+1 且 Ki ≤ K2i+2，其中 0 ≤ i ≤ (n-1)/2，n 是数组元的的个数。

堆的调整：

对于堆的调整，从当前结点开始（要求必须是非终端结点），对于大堆，要求当前结点关键字不小于两个子结点，如果不符合，则将其中最大的子结点与当前结点交换。循环迭代交换后的子树，确保所有子树都符合大堆特性。而小堆的调整过程则类似。

如下最小堆的示例：

现在有一个包含8个元素的数组：
49    38    65    97    76    13    27    49'
现在将其转换为完全二叉树如下：
            49                                      
          /    \                                   
        38      65                                       
       /  \    /  \                                                           
     97   76  13   27                   
    /                             
   49'                     
首先数组共包含 8 个元素，所以 n = 8；
最后一个非叶子结点的下标为 (n - 1) / 2 = 3；
总共需要调整的次数为 (n - 1) / 2 + 1 = 4;
我们现在从最后一个非终端结点（非叶子结点）开始，向前进行调整，确保符合堆的特性。
第一次调整：
选择最后一个非叶子结点 97（下标为 3）为当前父结点，与其子节点进行比较，选择最小的结点作为当前父节点。
调整后的数组：
49    38    65    49'    76    13    27    97
调整后的堆如下：
            49                                      
          /    \                                   
        38      65                                       
       /  \    /  \                                                           
     49'  76  13  27                   
    /                             
   97
第二次调整：
选择上一次的非叶子结点的前一个结点，也就是结点 65（下标为 2）为当前结点开始进行上面相同方法的调整。
调整后的数组：
49    38    13    49'    76    65    27    97
调整后的堆如下：
            49                                      
          /    \                                   
        38      13                                       
       /  \    /  \                                                           
     49'  76  65  27                   
    /                             
   97
第三次调整：
继续选择上次处理的结点的前一个结点，也就是结点 38（下标为 1）为当前结点开始进行上面相同方法的调整。
因为当前结点 38 本身小于左右子节点，所以不用进行调整。
第四次调整：
继续选择上次处理的结点的前一个结点，也就是结点 49（根节点，下标为 0）为当前结点开始进行上面相同方法的调整。
注意：之前的三次都没有包含子树的调整，这次因为父节点 49 大于子节点 13，需要进行交换；
但交换后，其右子树中以结点 49 为父节点，大于其子节点 27，不符合小堆的特性，还要再进行迭代调整。
调整后的数组：
13    38    27    49'    76    65    49    97
调整后的堆如下：
            13                                      
          /    \                                   
        38      27                                       
       /  \    /  \                                                           
     49'  76  65  49                   
    /                             
   97
到这里我们就建好了一个小堆，堆的堆顶元素（也就是树的根节点）就是数组中最小的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

堆排序算法思想：
上面已经详细说明小根堆的调整过程，我们建立的堆已经满足了最小堆的条件，这也将作为堆排序中创建的初始堆，则堆的第一个元素 heap[0] 是最小的元素，我们将第一个元素 heap[0] 与 heap[n-1] 进行对调，把最小的元素交换到最后，再对前面的 n-1 个元素使用堆的调整算法，重新建立最小堆。结果次最小的元素又上浮到堆顶，即 heap[0] 位置，再对调 heap[0] 和 heap[n-2]，再对前面的 n-2 个元素使用堆的调整算法，重新建立最小堆，……，如此反复就能得到全部排序好的元素序列。

代码实现：

//大堆的调整
void HeapAdjust(int *arr, int i, int size)
{
    if (i > size / 2 - 1) //叶子结点，无子树
        return;
    // 检查结点i是否符合大堆特性, 如果不符合, 需要与最大子结点交换
    for (int k = 2 * i + 1; k < size; k = 2 * k + 1)
    {
        // 判断右结点是否比左结点更大
        if (k + 1 < size && arr[k + 1] > arr[k])
            ++k;
        if (arr[i] < arr[k])
        {
            std::swap(arr[i], arr[k]);
            i = k;
        }
        else //符合大堆特性
        {
            break;
        }
    }
}
//堆排序
void HeapSort(int *arr, int size)
{
    //这里是先建一个初始堆,也就是第一个元素arr[0]已经是最大元素
    for (int i = (size - 1) / 2; i >= 0; --i)
    {
        HeapAdjust(arr, i, size);
    }
    //每次将第一个最大的元素，与后面的元素交换，后面的元素就是逐个排序了
    for (int j = size - 1; j > 0; --j)
    {
        std::swap(arr[0], arr[j]);
        HeapAdjust(arr, 0, j - 1); //然后再对面前 j-1个元素进行堆调整
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

算法分析：

堆排序是不稳定的排序算法，最好情况下的时间复杂度为 O(nlogn)，最坏情况下时间复杂度为 O(nlogn)，平均时间复杂度为 O(nlogn)。

归并排序

算法思想：

归并排序是一种概念上最简单的排序算法。和快速排序类似，归并排序也是基于分治法。其算法思想是：归并排序将待排序的元素划分为两个长度相等的子序列，对于这两个子序列继续执行两路划分，直到子序列为空或者只有一个元素为止。然后开始进行归并，将两个子序列进行归并，一直执行直到整个序列有序为止。

归并排序分可以自顶向下进行排序，也可以自底向上进行排序。

• 自顶向下的二路归并排序过程示例：

假如现在有一个序列为：
{2,  5,  1,  7,  10,  6,  9,  4,  3,  8}
将序列进行划分：
{2,  5,  1,  7,  10} {6,  9,  4,  3,  8}
{2,  5,  1} {7,  10} {6,  9,  4} {3,  8}
{2,  5} {1} {7} {10} {6,  9} {4} {3} {8}
{2} {5} {1} {7} {10} {6} {9} {4} {3} {8}
不能继续再划分，开始进行归并：
{2,  5} {1} {7} {10} {6,  9} {4} {3} {8}
{1,  2,  5} {7,  10} {4,  6,  9} {3,  8}
{1,  2,  5,  7,  10} {3,  4,  6,  8,  9}
{1,  2,  3,  4,  5,  6,  7,  8,  9,  10}
1
2
3
4
5
6
7
8
9
10
11
12

对于自顶向下的归并排序中，我们将子序列一直进行划分，直到变成最小子序列，而最小子序列只有一个元素肯定是有序的，将两个最小子序列进行有序合并操作，得到的序列还是有序的，所以我们每次都是在合并两个有序的子序列，可以参考下面代码实现的 Merge 函数的实现。

• 自低向上的二路归并排序算法：

既然自顶向下的二路归并算法在划分到最小子序列时，每个子序列包含一个元素；那么我们可不可以认为这个数组的每一个元素是已经划分好的每一个元素了，直接进行二路归并呢？当然是可以的，但是在操作和自顶向下的肯定又区别。我们可以对这个数组进行如下步骤：

1. 将长度为 n 的原序列分解成 length 长度的若干子序列（每趟 length 依次取 1，2，…，log2n）。
2. 将相邻的两个子序列调用 Merge 算法合并成一个有序子序列。
3. 由于整个序列存放在数组 arr 中，排序就是就地进行的，和并步骤不需要执行任何操作。

如下示例：

假如现在有一个序列为：
{2,  5,  1,  7,  10,  6,  9,  4,  3,  8}
我们将其每一趟都分解成若干个length长度的子序列
并将相邻的两个子序列调用Merge算法合并
{2} {5} {1} {7} {10} {6} {9} {4} {3} {8}
{2,  5} {1,  7} {6,  10} {4,  9} {3,  8}
{1,  2,  5,  7} {4,  6,  9,  10} {3,  8}
{1,  2,  3,  4   5,  6,  7,   8,  9, 10}
1
2
3
4
5
6
7
8

代码实现：

//归并算法
void Merge(int *arr, int left, int mid, int right)
{
    if (!arr) return;
    int i = left;
    int j = mid + 1;
    int k = 0;
    //辅助数组大小是要合并的两个有序子表大小之和
    int *tmp_arr = new int[right - left + 1];
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j]) //将第1子表中的元素放入tmp_arr中
        {
            tmp_arr[k] = arr[i];
            ++i;
            ++k;
        }
        else //将第2子表中的元素放入tmp_arr中
        {
            tmp_arr[k] = arr[j];
            ++j;
            ++k;
        }
    }
    while (i <= mid)
    {
        tmp_arr[k] = arr[i];
        ++i;
        ++k;
    }
    while (j <= right)
    {
        tmp_arr[k] = arr[j];
        ++j;
        ++k;
    }
    for (k = 0, i = left; i <= right; ++k, ++i) //将tmp_arr复制回原arr中对应的位置上
    {
        arr[i] = tmp_arr[k];
    }
    delete[] tmp_arr;
}

//自顶向下的归并排序算法
void MergeSort(int *arr, int left, int right)
{
    if (!arr) return;
    if (left < right) //子序列中有两个或以上元素
    {
        int mid = (left + right) / 2;   //取中间值
        MergeSort(arr, left, mid);      //对a[left..mid]子序列排序
        MergeSort(arr, mid + 1, right); //对a[mid+1..right]子序列排序
        Merge(arr, left, mid, right);   //将两子序列合并，见前面的算法
    }
}

//自低向上的二路归并排序算法：
void MergePass(int *arr, int length, int size) //一趟二路归并排序
{
    if (!arr)
        return;
    int i;
    for (i = 0; i + 2 * length - 1 < size; i += 2 * length) //归并length长的两相邻子表
    {
        Merge(arr, i, i + length - 1, i + 2 * length - 1);
    }
    if (i + length - 1 < size) //余下两个子表，后者长度小于length
    {
        Merge(arr, i, i + length - 1, size - 1); //归并这两个子表
    }
}

void MergeSort2(int *arr, int size)
{
    if (!arr)
        return;
    for (int length = 1; length < size; length *= 2)
    {
        MergePass(arr, length, size);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

算法分析：

归并排序是稳定的排序算法，其需要一个与原数组大小一样的辅助数组空间，最好情况下的时间复杂度为 O(nlogn)，最坏情况下时间复杂度为 O(nlogn)，平均时间复杂度为 O(nlogn)。

桶排序

桶排序是一种分配排序，与前面介绍的几种算法略有不同，前面介绍的方法都是建立在对元素排序码进行比较的基础上，而分配排序是采用“分配”与“收集”的办法。

算法思想：

桶排序也是一种分配排序，也为称为“箱排序”，工作原理是将待排序元素分到有限数量的桶里，假设待排序的元素均匀的分布在一个范围内，我们将这个范围划分为 n 个子区间，这些子区间被称为“桶”。然后基于某种函数函数的映射 f，将待排序的元素 k 映射到第 i 个桶中，那么该元素 k 就作为桶 B[i] 中的元素（之前说过待排序的元素均匀分布，所以每个桶内都不期望有太多太少排序元素）。我们只需要将各个桶内的元素排好序，然后按桶的编号依次输出各个桶内的元素，就可以得到整个有序的元素序列。

补充：为了使桶排序更加高效，注意如下几点：

1. 在额外空间足够的情况下，尽量增大桶的数量。

2. 使用的映射函数能够将输入的所有数据均匀的分配到每个桶中，同时对于桶中的元素排序，选择何种比较排序算法对于性能的影响至关重要。

过程示例如下：

假如现在有一个序列为：
{63,  157,  189,  51,  101,  47,  141,  121,  157,  156,  194,  117,  98,  139,  67,  133,  181,  13,  28,  109}
现在开始分配桶，最大数为194，最小数为13，如果分6个桶，每个桶分布如下：
桶1：[13 ~ 44)     13 -> 28
桶2：[44 ~ 75)     47 -> 51 -> 63
桶3：[75 ~ 106)    98 -> 101
桶4：[106 ~ 137)   109 -> 117 -> 121
桶5：[137 ~ 168)   133 -> 139 -> 141 -> 156 -> 157 -> 157
桶6：[168 ~ 199)   181 -> 189 -> 194
现在开始合并每个桶的数据得到的有序序列如下：
{13,  28,  47,  51,  63,  67,  98,  101,  109,  117,  121,  133,  139,  141,  156,  157,  157,  181,  189,  194}
1
2
3
4
5
6
7
8
9
10
11

代码实现：

代码中为了方标表达桶排序的思想，使用了 std::vector，在为单个桶排序使用 STL 的 sort 算法。

//桶的数量
const int BUCKET_NUM = 6;

//根据某个元素的值获得桶的编号
int GetBucketNo(int min, int max, int val)
{
    assert(min <= val && val <= max);
    int bucket_size = int(max - min) / BUCKET_NUM + 1; //每个桶的容量
    for (int i = 0; i < BUCKET_NUM; ++i)
    {
        int tmp = min + i * bucket_size;
        if (tmp <= val && val < tmp + bucket_size)
            return i;
    }
    return 0;
}

//桶排序
void BucketSort(int *arr, int size)
{
    int max = arr[0];
    int min = arr[0];
    int i;
    for (i = 0; i < size; ++i) //得到最大元素和最小元素
    {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }
    std::vector<int> bucket[BUCKET_NUM]; //假设桶的数量为6个

    for (i = 0; i < size; ++i)
    {
        int no = GetBucketNo(min, max, arr[i]); //获得元素对应的桶编号
        assert(0 <= no && no < BUCKET_NUM);
        bucket[no].push_back(arr[i]);
    }

    for (i = 0; i < BUCKET_NUM; ++i)
    {
        if (bucket[i].size() > 0)
        {
            std::sort(bucket[i].begin(), bucket[i].end()); //桶内排序
        }
    }

    int index = 0;
    for (i = 0; i < BUCKET_NUM; ++i) //桶遍历
    {
        for (const auto &it : bucket[i]) //每个桶的元素遍历
        {
            arr[index++] = it;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

算法分析：

桶排序是稳定的排序算法，最好情况下的时间复杂度为 O(n + k)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(n + k) ，空间复杂度为 O(n + k)。其中 k 表示桶排序中“桶”的个数，n 表示数据的规模。

基数排序

算法思想：

如果一个待排序的序列的每个元素的排序码都是由多个数据项组成，则对它排序时就需要利用多排序码排序，一般有两种常用的方法，一种方法是最高位优先（MSD 基数排序），另一种方法是最低位优先（LSD 基数排序），利用多排序码排序实现对单个排序码排序的算法称为基数排序。

先来说MSD，假设有一组元素，排序码的取值范围为 0~999，我们可以将这些排序码看作是百位、十位、个位的组合，我们可以使用百位、十位、个位的顺序对所有元素进行排序，每个数的各位上可能的取值都是 0~9，总共可能的取值有 10 种，称每位数可能取值数称为基数，如十进制数字的 radix = 10，英文字母的 radix = 26。

在排序过程中，我们首先根据百位上的数字进行排序（也可以从个位数开始），按各元素在百位数上的取值，分配到各个子序列（桶）中，然后按照子序列（桶）的编号，对逐个子序列（桶）进行递归的基数排序。在每个子序列中，其数据规模已经大大减少，而且子序列中所有元素在百位数上的数字取值相同，然后再按各元素的十位上的数字取值继续进行分配子序列，之后再对按各元素的各位上的数字进行分配子序列，从而使得待排序序列所有元素排好序。

而常用的基数排序思想其实是 LSD 基数排序，LSD 基数排序抽取排序码的顺序和 MSD 相反，利用“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。用上面 MSD 的实例来说，其每个数的各位上可能取值都是 0~9，总共可能的取值有 10 种，我们将取元素的个位上的值，将其分配到个位数对应的编号的子序列（桶）中，“分配”到同一个子序列（桶）用链表连接起来，然后我们再按编号顺序将排序元素“收集”到原数组中，将链表清空（实际不一定要清空，只是一种思想，链表的选择有多种，可以使用环形链表），再将十位数取值分配到对应编号的链表中，再收集到原数组中，百位也是一样的操作，最终我们数组中的数据便已经完成排序。

LSD 基数排序的具体示例如下：

假如现在有一个序列为（最大3位数）：
{332,  633,  589,  232,  664,  179,  457,  825,  405,  361}

进行第1趟分配（个位）：
fr[0]   fr[1]   fr[2]   fr[3]   fr[4]   fr[5]   fr[6]   fr[7]   fr[8]   fr[9]
  ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓
  ↓      361     332     633     664     825      ↓      457      ↓      589
  ↓       ↓      232      ↓       ↓      405      ↓       ↓       ↓      179     
  ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓  
re[0]   re[1]   re[2]   re[3]   re[4]   re[5]   re[6]   re[7]   re[8]   re[9]
第1趟收集：
{361,  332,  232,  633,  664,  825,  405,  457,  589,  179}

进行第2趟分配（十位）：
fr[0]   fr[1]   fr[2]   fr[3]   fr[4]   fr[5]   fr[6]   fr[7]   fr[8]   fr[9]
  ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓
 405      ↓      825     332      ↓      457     361     179     589      ↓
  ↓       ↓       ↓      232      ↓       ↓      664      ↓       ↓       ↓
  ↓       ↓       ↓      633      ↓       ↓       ↓       ↓       ↓       ↓
  ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓  
re[0]   re[1]   re[2]   re[3]   re[4]   re[5]   re[6]   re[7]   re[8]   re[9]
第2趟收集：
{405,  825,  332,  232,  633,  457,  361,  664,  179,  589}

进行第3趟分配（百位）：
fr[0]   fr[1]   fr[2]   fr[3]   fr[4]   fr[5]   fr[6]   fr[7]   fr[8]   fr[9]
  ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓
  ↓      179     232     332     405     589     633      ↓      825      ↓
  ↓       ↓       ↓      361     457      ↓      664      ↓       ↓       ↓ 
  ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓       ↓  
re[0]   re[1]   re[2]   re[3]   re[4]   re[5]   re[6]   re[7]   re[8]   re[9]
第3趟收集：
{179,  232,  332,  361,  405,  457,  589,  633,  664,  825}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

LSD 和 MSD 基数排序不同的是，它不是递归地，而是控制从低位到高位进行分配和收集，基数排序中的 LSD 步骤被广泛采用，因为其控制非常简单，其基本操作适合机器语言执行，可以直接改编到特殊功能的高效硬件中，在这种环境中，运行 LSD 基数排序可能是最快的。

算法实现：

为了使算法思想简洁明了，代码直接使用了 STL 中的 list。

//分配操作
void Distribute(int *arr, int size, int d, std::list<int> *lists)
{
    if (!arr || !lists) return;
    for (int i = 0; i < size; ++i)
    {
        int index = GetKey(arr[i], d);
        lists[index].push_back(arr[i]);
    }
}

//收集操作
void Collect(int *arr, list<int> *lists)
{
    if (!arr || !lists) return;
    int index = 0;
    list<int>::iterator it;
    for (int i = 0; i < 10; ++i)
    {
        it = lists[i].begin();
        while (it != lists[i].end())
        {
            arr[index++] = *it;
            ++it;
        }
        lists[i].clear(); //收集完成清空链表
    }
}
//基数排序
void RadixSort(int *arr, int size)
{
    if (!arr) return;
    int d = 3;                //对1000内的数进行排序
    std::list<int> lists[10]; //基数为10，表示从0-9共10个链表
    for (int i = 1; i <= d; ++i)
    {
        Distribute(arr, size, i, lists); //三位数分配三次，每次都会插入对应的桶的链表中
        Collect(arr, lists); //每一次回收将链表中的数据都会被重新放在数组中
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

算法分析：

基数排序是稳定的排序算法，对于有 n 个元素的链表，每趟分配的 while 循环需要执行 n 次，把 n 个元素分配到 radix 个队列中，进行收集的 for 循环需要执行 radix 次，从各个队列中把元素收集起来按顺序链接。若每个排序码有 d 位，需要重复 d 趟分配和收集，最差、最好、平均下的时间复杂度均为 O(d(n + radix))，若基数 radix 相同，对于元素个数较多而排序码位数较少的情况，使用链式基数排序好。

计数排序

算法思想：

计数排序是一种线性排序算法，主要是利用了一个数组，因为数组的下标是线性增长的，所以它就把元素的值转换成数组的下标。那么有一个问题：数组中的值有正负，但是下标都是非负啊？我们只需要做一个简单的转化就行了：找到数组中最小的元素，让每个元素值都减去这个最小的元素（最小的元素就从0开始了，其他元素依次偏移最小元素的绝对值），有点类似于一个映射函数，如下示例：

//比如有一个待排序数组：
{-1, -5, -6, -2,  1,  2,  8,  2,  1,  8}
最小元素是-6，我们将数组中每个元素都减去-6，得到的待排序元素如下：
{5,  1,  0,  4,  7,  8,  14,  8,  7,  14}
1
2
3
4

因为上面转换后的数组中的最大元素为 14，我们的数组空间也需要 14 +1 = 15（max - min + 1，为了数组下标和待排序元素的数值统一，下标为 0 的不使用），然后新的数组中就存当前下标数值在待排序的转换后的序列中出现的次数，如果转换后的待排序元素没有下标数值就存的是 0，所以数组中元素的差距很大，比较浪费空间，这是一种空间换时间的排序方法。现在对上面转换后的待排序元素进行排序：

count:  1  1  0  0  1  1  0  2  2  0  0   0   0   0   2
index:  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14
1
2

最后我们遍历这个数组，如果 count 大于 0，我们取出它的下标数值，然后再做转换写回原来的 arr 中就完成排序了。

算法代码：

//计数排序
void CountSort(int *arr, int size)
{
    if (!arr)
        return;
    int max = arr[0];
    int min = arr[0];
    int i;
    for (i = 0; i < size; ++i)
    {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }
    int range = max - min + 1;
    int *count_arr = new int[range]; //新的数组范围
    memset(count_arr, 0, sizeof(int) * range);

    for (i = 0; i < size; ++i) //统计每个数出现的次数
    {
        count_arr[arr[i] - min]++;
    }
    int index = 0;
    for (i = 0; i < range; ++i) //写回到原数组
    {
        while (count_arr[i]--)
        {
            arr[index++] = i + min;
        }
    }
    delete[] count_arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

算法分析：

计数排序是稳定的排序算法，其最差、最好、平均时间复杂度均为 O(n + k)，空间复杂度为 O(k)。这是一种以空间换时间的排序算法，在数据量少且数据范围很小的情况下，效率非常高。

十大排序算法的总结

一般情况下，对于一个有 n 个元素的待排序序列，期望在在排序时所比较的次数为 O(nlogn)，这也是一般情况下排序算法可期待的最好的时间复杂度。

下面给出排序算法的综合图：

其中：n 为数据规模，k 为桶的个数。

基本排序算法包括直接插入排序、冒泡排序、直接选择排序其平均时间复杂度都是 O(n^2)，也不需要其他额外内存。

高效的排序算法包括快速排序、堆排序、归并排序适合于元素个数 n 很大的情况。其平均时间复杂度均为 O(nlogn)，但归并排序主要缺点是直接执行时需要 O(n) 的附加空间，虽然可以克服这个缺点，但是代价是算法变得复杂且时间复杂度增加，实际应用中一般不这么做，优点是它是一种稳定的排序算法。

希尔排序的时间复杂度介于基本排序算法和高效排序算法之间，至今对其性能的分析还不精确，但其代码简单，不需要额外内存，但其是不稳定的排序算法。

基数排序是一种相对特殊的排序算法，需要对排序码的不同部分进行比较，虽然它具有线性增长的时间复杂度，但实际编程中，索引统计内部循环中包含大量操作，其数目比快速排序和归并排序算法的内部循环多得多，所以它的实际不比快速排序

时间开销小很多，并且其分配和收集操作受到排序元素的影响，适应性也不如普通的比较和交换操作，因此通常使用常规的高效排序算法比较多。

在众多排序算法中，无论什么样的运行环境和实际应用，都有一两种算法能够表现出更好的性能，每种算法都有自己的价值。同时我们可以将各种算法混合使用，这也是普遍的一种算法改进的方法，例如将直接插入排序集成到快速排序中。这种混合算法能够充分发挥不同算法的优势，在整体上得到更好的性能。