十大经典排序算法

最近在工作中偶然间涉及到数据库的存储和访问，数据库里存放着员工的指纹、年龄以及姓名等信息，当然指纹是通过md5加密存储的。目前需要对员工的年龄、学历、工作年限等进行排序，如果只有几十个上百个样本，应该不会那么麻烦；关键这是几万名员工的数据，这个量很大，马虎不得。悄悄的告诉你，别惹我，我懂得删库跑路哦。

脑海中对排序的记忆有点模糊，只对「归并排序」印象较为深刻，为了加深理解，重拾「数据结构与算法」，并总结了一下常用的十大经典排序算法，由于平台为linux，因此代码全部用C++实现，全部源码均在linux下编译通过并测试成功，可以作为参考。

排序算法在程序猿的编程生涯中虽然用的不多，但是作为基本功，还是要掌握一下。排序算法是「数据结构与算法」中最基本的算法，它分为「内部排序」和「外部排序」；「内部排序」一般在内存中实现；当数据量很大时，内存有限，不能将所有的数据都放到内存中来，这个时候必须使用「外部排序」。

先看一张图，对常用算法的时间复杂度做个比较：

这里的「稳定」是指当排序后两个相等键值的顺序和排序之前的顺序相同；

一冒泡排序

冒泡排序是排序算法中较为简单的一种，英文称为Bubble Sort。它遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。

如果有

个数据，那么需要

的比较次数，所以当数据量很大时，冒泡算法的效率并不高。
当输入的数据是反序时，花的时间最长，当输入的数据是正序时，时间最短。

 1#include <iostream>
 2#include <algorithm>
 3using namespace std;
 4template<typename T> //整数或浮点数皆可使用
 5void bubble_sort(T arr[], int len) {
 6    int i, j;
 7    for (i = 0; i < len - 1; i++){
 8        for (j = 0; j < len - 1 - i; j++)
 9            if (arr[j] > arr[j + 1])
10                swap(arr[j], arr[j + 1]);
11       }
12}
13int main() {
14    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
15    int len = (int) sizeof(arr) / sizeof(*arr);
16    bubble_sort(arr, len);
17    for (int i = 0; i < len; i++)
18        cout << arr[i] << ' ';
19    cout << endl;
20    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
21    len = (int) sizeof(arrf) / sizeof(*arrf);
22    bubble_sort(arrf, len);
23    for (int i = 0; i < len; i++)
24        cout << arrf[i] << ' ';
25    return 0;
26}

新建代码文件bubble_sort.cpp，将以上代码写入，linux下编译：

1$ g++ -o bubble_sort bubble_sort.cpp

测试：

1$ ./bubble_sort

输出结果：

11 17 21 22 29 34 50 60 61 62 72
20.6 1.5 1.9 3.8 4.4 5.4 10.5 12.4 17.5 19.1 19.7 23.8 25.4 28.6

以下的编译方法和测试方法和这里一样，所以下面不再重复编译和测试的说明。

二选择排序

选择排序简单直观，英文称为Selection Sort，先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。很显然，选择排序也是一个费时的排序算法，无论什么数据，都需要

 1#include <iostream>
 2#include <algorithm>
 3
 4
 5using namespace std;
 6
 7template<typename T> //整数或浮点数皆可使用
 8
 9void selection_sort(T arr[],int len ) {
10    for (int i = 0; i < len  - 1; i++) {
11        int min = i;
12        for (int j = i + 1; j < len; j++)
13            if (arr[j] < arr[min])
14                min = j;
15        std::swap(arr[i], arr[min]);
16    }
17}
18int main() {
19
20    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
21    int len = (int) sizeof(arrf) / sizeof(*arrf);   
22    selection_sort(arrf,len);
23    for (int i = 0; i < len; i++)
24        cout << arrf[i] << ' ';
25    return 0;
26}

三插入排序

插入排序英文称为Insertion Sort，它通过构建有序序列，对于未排序的数据序列，在已排序序列中从后向前扫描，找到相应的位置并插入，类似打扑克牌时的码牌。插入排序有一种优化的算法，可以进行拆半插入。

基本思路是先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；然后从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，直到所有数据都完成排序；如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

 1#include <iostream>
 2#include <algorithm>
 3
 4
 5using namespace std;
 6
 7template<typename T> //整数或浮点数皆可使用
 8
 9void insertion_sort(T arr,int len){
10        for(int i=1;i<len;i++){
11                T key=arr[i];
12                int j;
13                for(j=i-1;j>=0 && key<arr[j];j--)
14                        arr[j+1]=arr[j];
15                arr[j+1]=key;
16        }
17}
18int main() {
19
20    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
21    int len = (int) sizeof(arrf) / sizeof(*arrf);   
22    insertion_sort(arrf,len);
23    for (int i = 0; i < len; i++)
24        cout << arrf[i] << ' ';
25    return 0;
26}

四希尔排序

希尔排序也称递减增量排序，是插入排序的一种改进版本，英文称为Shell Sort，效率虽高，但它是一种不稳定的排序算法。

插入排序在对几乎已经排好序的数据操作时，效果是非常好的；但是插入排序每次只能移动一位数据，因此插入排序效率比较低。

希尔排序在插入排序的基础上进行了改进，它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序。

平均时间复杂度：：

空间复杂度：：

假如有这样一组数据，[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果以步长5进行分割，每一列为一组，那么这组数据应该首先分成这样

113 14 94 33 82
225 59 94 65 23
345 27 73 25 39
410

之后对每列进行插入排序：

110 14 73 25 23
213 27 94 33 39
325 59 94 65 82
445

将上述四行数据依序拼接在一起，得到[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]，此时10已经移到正确的顺序了，之后以步长3进行插入排序：

排序之后变为：

最后以步长1进行排序。
步长的选择是希尔排序的关键，只要最终步长为1，任何步长序列都可以。建议最初步长选择为数据长度的一半，直到最终的步长为1。

图解：

代码：

 1#include <iostream>
 2#include <algorithm>
 3
 4
 5using namespace std;
 6
 7template<typename T>
 8
 9void shell_sort(T array[], int length) {
10    int h = 1;
11    while (h < length / 3) {
12        h = 3 * h + 1;
13    }
14    while (h >= 1) {
15        for (int i = h; i < length; i++) {
16            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
17                std::swap(array[j], array[j - h]);
18            }
19        }
20        h = h / 3;
21    }
22}
23int main() {
24
25    int arrf[] = { 13，14，94，33，82，25，59，94，65，23，45，27，73，25，39，10 };
26    int len = (int) sizeof(arrf) / sizeof(*arrf);   
27    shell_sort(arrf,len);
28    for (int i = 0; i < len; i++)
29        cout << arrf[i] << ' ';
30    return 0;
31}

五归并排序

归并排序英文称为Merge Sort，归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。它首先将数据样本拆分为两个子数据样本, 并分别对它们排序, 最后再将两个子数据样本合并在一起; 拆分后的两个子数据样本序列, 再继续递归的拆分为更小的子数据样本序列, 再分别进行排序, 直到最后数据序列为1，而不再拆分，此时即完成对数据样本的最终排序。

归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法.

作为一种典型的分而治之思想的算法应用，归并排序的实现分为两种方法：

 1#include <iostream>
 2#include <algorithm>
 3
 4using namespace std;
 5
 6template<typename T> 
 7void merge_sort_iteration(T arr[], int len) {//迭代法
 8    T* a = arr;
 9    T* b = new T[len];
10    for (int seg = 1; seg < len; seg += seg) {
11        for (int start = 0; start < len; start += seg + seg) {
12            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
13            int k = low;
14            int start1 = low, end1 = mid;
15            int start2 = mid, end2 = high;
16            while (start1 < end1 && start2 < end2)
17                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
18            while (start1 < end1)
19                b[k++] = a[start1++];
20            while (start2 < end2)
21                b[k++] = a[start2++];
22        }
23        T* temp = a;
24        a = b;
25        b = temp;
26    }
27    if (a != arr) {
28        for (int i = 0; i < len; i++)
29            b[i] = a[i];
30        b = a;
31    }
32    delete[] b;
33}
34template<typename T> 
35void merge_sort_recursive_t(T arr[], T reg[], int start, int end) {//递归法
36    if (start >= end)
37        return;
38    int len = end - start, mid = (len >> 1) + start;
39    int start1 = start, end1 = mid;
40    int start2 = mid + 1, end2 = end;
41    merge_sort_recursive_t(arr, reg, start1, end1);
42    merge_sort_recursive_t(arr, reg, start2, end2);
43    int k = start;
44    while (start1 <= end1 && start2 <= end2)
45        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
46    while (start1 <= end1)
47        reg[k++] = arr[start1++];
48    while (start2 <= end2)
49        reg[k++] = arr[start2++];
50    for (k = start; k <= end; k++)
51        arr[k] = reg[k];
52}
53template<typename T> 
54void merge_sort_recursive(T arr[], const int len) {
55    T *reg = new T[len];
56    merge_sort_recursive_t(arr, reg, 0, len - 1);
57    delete[] reg;
58}
59
60int main() {
61
62    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
63    int len = (int) sizeof(arrf) / sizeof(*arrf);   
64    merge_sort_recursive(arrf,len);
65    for (int i = 0; i < len; i++)
66        cout << arrf[i] << ' ';
67
68    merge_sort_iteration(arrf,len);
69    for (int i = 0; i < len; i++)
70        cout << arrf[i] << ' ';
71    return 0;
72}

六快速排序

快速排序,英文称为Quicksort，又称划分交换排序 partition-exchange sort 简称快排。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。首先从数列中挑出一个元素，并将这个元素称为「基准」，英文pivot。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。
在平均状况下，排序n个项目要

次比较。在最坏状况下则需要

次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

代码分两种方式实现，分别为迭代法和递归法。
迭代法：

 1struct Range {
 2    int start, end;
 3    Range(int s = 0, int e = 0) {
 4        start = s, end = e;
 5    }
 6};
 7template <typename T> // 
 8void quick_sort(T arr[], const int len) {
 9    if (len <= 0)
10        return; // 
11
12    Range r[len];
13    int p = 0;
14    r[p++] = Range(0, len - 1);
15    while (p) {
16        Range range = r[--p];
17        if (range.start >= range.end)
18            continue;
19        T mid = arr[range.end];
20        int left = range.start, right = range.end - 1;
21        while (left < right) {
22            while (arr[left] < mid && left < right) left++;
23            while (arr[right] >= mid && left < right) right--;
24            std::swap(arr[left], arr[right]);
25        }
26        if (arr[left] >= arr[range.end])
27            std::swap(arr[left], arr[range.end]);
28        else
29            left++;
30        r[p++] = Range(range.start, left - 1);
31        r[p++] = Range(left + 1, range.end);
32    }
33}

递归法：

 1template <typename T>
 2void quick_sort_recursive(T arr[], int start, int end) {
 3    if (start >= end)
 4        return;
 5    T mid = arr[end];
 6    int left = start, right = end - 1;
 7    while (left < right) {
 8        while (arr[left] < mid && left < right)
 9            left++;
10        while (arr[right] >= mid && left < right)
11            right--;
12        std::swap(arr[left], arr[right]);
13    }
14    if (arr[left] >= arr[end])
15        std::swap(arr[left], arr[end]);
16    else
17        left++;
18    quick_sort_recursive(arr, start, left - 1);
19    quick_sort_recursive(arr, left + 1, end);
20}
21template <typename T> //
22void quick_sort(T arr[], int len) {
23    quick_sort_recursive(arr, 0, len - 1);
24}

七堆排序

堆排序，英文称Heapsort，是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序实现分为两种方法：

 1#include <iostream>
 2#include <algorithm>
 3using namespace std;
 4
 5void max_heapify(int arr[], int start, int end) {
 6    //建立父节点指标和子节点指标
 7    int dad = start;
 8    int son = dad * 2 + 1;
 9    while (son <= end) { //子节点指标在范围内才做比较
10        if (son + 1 <= end && arr[son] < arr[son + 1]) //比较两个子节点大小，选择最大的
11            son++;
12        if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数
13            return;
14        else { //否則交换父子内容再继续子节点和孙节点比较
15            swap(arr[dad], arr[son]);
16            dad = son;
17            son = dad * 2 + 1;
18        }
19    }
20}
21
22void heap_sort(int arr[], int len) {
23    //初始化，i从最后一个父节点开始调整
24    for (int i = len / 2 - 1; i >= 0; i--)
25        max_heapify(arr, i, len - 1);
26    //先將第一个元素和已经排好的元素前一位做交换，再重调整，(刚调整的元素之前的元素)，直到排序完毕
27    for (int i = len - 1; i > 0; i--) {
28        swap(arr[0], arr[i]);
29        max_heapify(arr, 0, i - 1);
30    }
31}
32
33int main() {
34    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
35    int len = (int) sizeof(arr) / sizeof(*arr);
36    heap_sort(arr, len);
37    for (int i = 0; i < len; i++)
38        cout << arr[i] << ' ';
39    cout << endl;
40    return 0;
41}

八计数排序

计数排序英文称Counting sort，是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于 i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。基本的步骤如下：

 1void  Count_Sort(int* Data, int Len)
 2{
 3    int* Cout = NULL;           
 4    Cout = (int*)malloc(sizeof(int) * Len);   
 5    //初始化记数为0
 6    for (int i = 0; i < Len; i++)
 7    {
 8        Cout[i] = 0;
 9    }
10
11    //记录重复的个数
12    for (int i = 0; i < Len; i++)
13    {
14        Cout[Data[i]] += 1;   
15    }
16
17    //确定不比该位置大的数据个数。
18    for (int i = 1; i < Len; i++)
19    {
20        Cout[i] += Cout[i - 1];    
21    }
22
23    int* Sort = NULL;           
24    Sort = (int*)malloc(sizeof(int) * Len);   
25
26    for (int i = 0; i < Len; i++)
27    {
28        //将数组反向填充到Sort，每次拿出一个就减一
29        Cout[Data[i]] -= 1;   
30        Sort[Cout[Data[i]]] = Data[i];        
31
32    }
33
34    //排序结束，将排序好的数据复制到原来数组中。
35    for (int i = 0; i < Len; ++i)
36    {
37        Data[i] = Sort[i];
38    }
39
40    //释放申请的空间。
41    free(Cout);
42    free(Sort);
43
44}

九桶排序

桶排序也称为箱排序，英文称为 Bucket Sort。它是将数组划分到一定数量的有序的桶里，然后再对每个桶中的数据进行排序，最后再将各个桶里的数据有序的合并到一起。

 1#include <iostream>
 2#include <vector>
 3#include <stdio.h>
 4#include <stdlib.h>
 5#include <string.h>
 6using namespace std;
 7
 8struct tNode
 9{
10    int tValue; 
11    tNode *next; 
12
13    tNode(int val) 
14    {
15        this->tValue = val;
16        this->next = NULL;
17    }
18};
19
20
21
22bool bucket_sort(int *arrf, const int SIZE)
23{
24    tNode **pNode = (tNode **)malloc(sizeof(tNode *) * 512);
25    if (NULL == pNode)
26        return false;
27
28    memset(pNode, 0, sizeof(tNode *) * 512);
29
30    int shiftNum = 0;
31    tNode *p = NULL;
32    tNode *pLast = NULL;
33    tNode *pNewNode = NULL;
34
35    for (int i = 0; i < SIZE; ++i)
36    {
37        shiftNum = arrf[i] >> 24;
38        p = pNode[shiftNum];
39
40        pNewNode = new tNode(arrf[i]);
41        if (NULL == pNewNode)
42            return false;
43
44        if (NULL == p)
45        {
46            pNode[shiftNum] = pNewNode;
47        }
48        else if (arrf[i] <= p->tValue) 
49        {
50            pNode[shiftNum] = pNewNode;
51            pNewNode->next = p;
52        }
53        else 
54        {
55            while (NULL != p->next)
56            {
57                if (arrf[i] > p->next->tValue)
58                    p = p->next;
59                else
60                    break;
61            }
62            pNewNode->next = p->next;
63            p->next = pNewNode;
64        }
65    }
66
67    for (int i = 0, k = 0; i < 512; i++)
68    {
69        p = pNode[i];
70
71        while (NULL != p)
72        {
73            arrf[k++] = p->tValue;
74            p = p->next;
75        }
76    }
77
78    return true;
79}
80int main(int argc, char **argv)
81{
82    int arr[] = { 5,558,772,935,344,487,96,665,302,735,954,308,718,147,185,371,166,849,202,478,874,169,980,125,44,15,279,882,466,974 };
83
84
85    bucket_sort(arr,30);
86    for (int i = 0; i < 30; ++i)
87    {
88        cout<<arr[i]<<" ";
89    }
90
91    cout<<endl;
92
93    return 0;
94}

十基数排序

基数排序英文称Radix sort，是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串和特定格式的浮点数，所以基数排序也仅限于整数。它首先将所有待比较数值，统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

 1int maxbit(int data[], int n) //辅助函数，求数据的最大位数
 2{
 3    int maxData = data[0];        ///< 最大数
 4    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
 5    for (int i = 1; i < n; ++i)
 6    {
 7        if (maxData < data[i])
 8            maxData = data[i];
 9    }
10    int d = 1;
11    int p = 10;
12    while (maxData >= p)
13    {
14        //p *= 10; // Maybe overflow
15        maxData /= 10;
16        ++d;
17    }
18    return d;
19/*    int d = 1; //保存最大的位数
20    int p = 10;
21    for(int i = 0; i < n; ++i)
22    {
23        while(data[i] >= p)
24        {
25            p *= 10;
26            ++d;
27        }
28    }
29    return d;*/
30}
31void radixsort(int data[], int n) //基数排序
32{
33    int d = maxbit(data, n);
34    int *tmp = new int[n];
35    int *count = new int[10]; //计数器
36    int i, j, k;
37    int radix = 1;
38    for(i = 1; i <= d; i++) //进行d次排序
39    {
40        for(j = 0; j < 10; j++)
41            count[j] = 0; //每次分配前清空计数器
42        for(j = 0; j < n; j++)
43        {
44            k = (data[j] / radix) % 10; //统计每个桶中的记录数
45            count[k]++;
46        }
47        for(j = 1; j < 10; j++)
48            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
49        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
50        {
51            k = (data[j] / radix) % 10;
52            tmp[count[k] - 1] = data[j];
53            count[k]--;
54        }
55        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
56            data[j] = tmp[j];
57        radix = radix * 10;
58    }
59    delete []tmp;
60    delete []count;
61}

参考

wiki
https://github.com/hustcc/JS-Sorting-Algorithm
「数据结构与算法」
「算法导论」

编辑于 2024-02-25 10:27・IP 属地天津

数据结构

排序算法

算法