常见排序算法

简单选择排序

简单选择排序和堆排序，简单选择排序的基本思想是每一趟在待排序元素中选取关键字最小的元素加入有序子序列，直到所有元素有序，总共进行 n−1n-1 趟。

简单选择排序为不稳定排序。

简单选择排序时间复杂度：

时间复杂度：O(n2)O(n^2)
空间复杂度：O(1)O(1)

堆排序

堆排序的基本思想见文末图片，堆排序为不稳定排序。

堆排序时间复杂度：

一个节点每下降一层，最多只需要比较两次关键字。若树高度为 hh，某节点在第 ii 层，则将这个节点向下调整最多只需要下降 h−ih-i 层，那么对比次数不超过 2(h−i){2}(h-i)，nn 个节点的完全二叉树树高 h=⌊log⁡2n⌋+1h = \left\lfloor {\log _2}n \right\rfloor + 1。

将整棵树调整为大根堆，关键字比较次数不超过：

∑i=h−112i−12(h−i)=∑i=h−112i(h−i)=∑j=1h−12h−jj≤2n∑j=1h−1j2j≤4n\sum\limits_{ {\rm{i} } = h - 1}^1 { {2^{i - 1} }2(h - i) = } \sum\limits_{ {\rm{i} } = h - 1}^1 { {2^i}(h - i) = } \sum\limits_{j = 1}^{h - 1} { {2^{h - j} }j \le 2n\sum\limits_{j = 1}^{h - 1} {\frac{j}{ { {2^j} } } } } \le 4n

建堆的过程关键字的对比次数不超过 4n{4}n，建堆的时间复杂度：O(n)O(n)

heapSort总共需要 n−1n-1 趟，每一趟完成后都需要将根节点下坠，根节点最多下降 h−1h-1 层，因此，每一趟排序的复杂度不超过 O(h)=O(log⁡2n)O(h)=O({\log _2}n)，总共 n−1n-1 趟，故总时间复杂度：O(nlog⁡2n)O(n{\log _2}n)

故堆排序的时间复杂度：O(n)+O(nlog⁡2n)=O(nlog⁡2n)O(n)+O(n{\log _2}n)=O(n{\log _2}n)
空间复杂度：O(1)O(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
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
#include <iostream>

using namespace std;

void swap(int &a, int &b);
void selectSort(int arr[], int n);  //简单选择排序

void buildMaxHeap(int arr[], int len);  //建立大根堆
void headAdjust(int arr[], int k, int len);  //调整节点，使其较小节点下坠，使其符合大根堆的特性

void heapSort(int arr[], int len);  //堆排序（基于大根堆）

int main()
{
    int arr[] = {5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, heap_arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    selectSort(arr, length);
    for(auto item:arr)
        cout << item << " ";
    cout << endl;

    heapSort(heap_arr, length);
    for(int i = 1; i < length + 1; i++)
        cout << heap_arr[i] << " ";

    return 0;
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void selectSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)     //进行n-1次即可，最后一个数必然是最大的
    {
        int min = i;
        for (int j = i + 1; j < n; j++)     //从i后面一个数开始，找到一个最小的数
        {
            if (arr[j] < arr[min])
                min = j;    //记录最小数的下标
        }
        swap(arr[i], arr[min]);     //将最小数与i位置的数交换
    }
}

void buildMaxHeap(int arr[], int len)
{
    for (int i = len / 2; i > 0; i--)  //从最后一个分支节点开始调整，0为暂存节点
        headAdjust(arr, i, len);
}

void headAdjust(int arr[], int k, int len)
{
    arr[0] = arr[k];  //将当前节点暂存给arr[0]
    for (int i = 2 * k; i <= len; i *= 2)   //沿值较大的节点向下查找
    {
        if(i < len && arr[i] < arr[i + 1])  //i < len 保证当前节点有右孩子
            i++;    //记录左右子节点中较大的节点
        if(arr[0] >= arr[i])
            break;    //如果当前节点大于等于左右子节点，则不需要调整
        else{
            arr[k] = arr[i];   //将左右子节点中较大的节点放入当前双亲节点
            k = i;  //替换为较大的节点，进入下一次循环，看是否满足大于左右孩子的条件
        }
    }
    arr[k] = arr[0];  //将待调整的节点的值放入最终位置
}

void heapSort(int arr[], int len)
{
    buildMaxHeap(arr, len);     //建立大根堆
    for (int i = len; i > 1; i--)
    {
        swap(arr[1], arr[i]);   //堆顶和堆底交换，使堆底元素最大，注意堆顶是arr[1]，arr[0]是暂存节点
        headAdjust(arr, 1, i - 1);  //调整剩余的堆（i及其后面的序列已经有序），让堆顶元素下坠
    }
}
堆排序导图
堆排序导图

插入排序

插入排序，基本思想是将待排序的记录按其关键字的大小逐个插入到一个有序序列（通常为左半部分），直到所有记录插入完成，是一种稳定排序。
空间复杂度：O(1)O(1)
平均时间复杂度：O(n2)O(n^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
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
#include <iostream>

using namespace std;

//直接插入排序（含哨兵）优点：不用判断j>=0，哨兵即为循环结束标志
void insertSort_1(int arr[], int n);
//直接插入排序（不含哨兵）
void insertSort_2(int arr[], int n);
//折半（二分）插入排序 对直接插入排序的优化
void insertSort_3(int arr[], int n);

int main()
{
    int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, arr_2[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, arr_normal[] = {5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    insertSort_1(arr, length);
    insertSort_2(arr_normal, length - 1);
    for (int i = 1; i < length; i++)
        cout << arr[i] << " ";
    cout << endl;
    for(auto item:arr_normal)
        cout << item << " ";
    cout << endl;
    insertSort_3(arr_2, length);
    for (int i = 1; i < length; i++)
        cout << arr_2[i] << " ";
    return 0;
}

void insertSort_1(int arr[],int n)
{
    int i, j;
    for (i = 2; i < n; i++)     //从第二个元素开始，arr[0]为哨兵
    {
        if(arr[i] < arr[i - 1])     //arr[i - 1]为上一个有序序列中的最大元素
        {
            arr[0] = arr[i];
            for (j = i - 1; arr[0] < arr[j]; --j)  //当前元素若小于或等于哨兵元素，则停止移动，哨兵插入该位置后
                arr[j + 1] = arr[j];    //往后移，为待插入元素腾出空位
            arr[j + 1] = arr[0];    //将哨兵插入
        }
    }
}

void insertSort_2(int arr[],int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)     //从第二个元素开始，arr[0]为哨兵
    {
        if(arr[i] < arr[i - 1])     //arr[i - 1]为上一个有序序列中的最大元素
        {
            temp = arr[i];  //临时存储待插入元素
            for (j = i - 1; j >= 0 && temp < arr[j]; --j)  //当前元素若小于或等于待插入元素，则停止移动，待插入元素插入该位置后
                arr[j + 1] = arr[j];    //往后移，为待插入元素腾出空位
            arr[j + 1] = temp;    //待插入元素插入
        }
    }
}

void insertSort_3(int arr[], int n)
{
    int i, j, low, high, mid;
    for (i = 2; i < n; i++)
    {
        arr[0] = arr[i];    //待插入元素存入哨兵节点
        low = 1, high = i - 1;  //折半查找的区域
        while(low <= high){
            mid = (low + high) / 2;
            if(arr[mid] > arr[0])
                high = mid - 1;     //查找左半部分
            else
                low = high + 1;     //查找右半部分，同时当arr[mid]==arr[0]时，继续在mid右方查找插入位置，保证算法稳定性
        }
        for (j = i - 1; j >= high + 1; j--)     //循环大于哨兵的所有元素，均往后移动一位
            arr[j + 1] = arr[j];    //往后移，为待插入元素腾出空位
        arr[high + 1] = arr[0];    //待插入元素插入
    }
}
插入排序导图
插入排序导图

快速排序

快速排序，即交换排序的一种，是对冒泡排序的一种改进，是一种不稳定排序。
平均时间复杂度：O(nlogn)O(nlogn)
最坏时间复杂度（退化至冒泡排序）：O(n2)O(n^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
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
#include <iostream>

using namespace std;

//快速排序
void quickSort(int arr[], int low, int high);
void quickSort_another(int *arr, int left, int right);
//划分函数
int partition(int arr[], int low, int high);

int main()
{
    int arr[] = {5, 2, 4, 6, 1, 3};
    quickSort(arr, 0, 5);
    for(auto cur:arr)
        cout << cur << " ";
    cout << endl;
    quickSort_another(arr, 0, 5);
    for(auto cur:arr)
        cout << cur << " ";
    return 0;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];   //第一个元素作为基准
    while(low < high)   //low == high时结束
    {
        while(low < high && arr[high] >= pivot)
            --high;
        arr[low] = arr[high];   //此时arr[high]小于基准元素
        while (low < high && arr[low] <= pivot)
            ++low;
        arr[high] = arr[low];   //此时arr[low]大于基准元素
    }
    arr[low] = pivot;   //此时low == high
    return low;     //返回基准元素的下标
}
void quickSort(int arr[], int low, int high)
{
    if(low < high)
    {
        int pivot_pos = partition(arr, low, high);
        quickSort(arr, low, pivot_pos - 1);     //对基准元素左边的数组进行快速排序
        quickSort(arr, pivot_pos + 1, high);    //对基准元素右边的数组进行快速排序
    }
}

//写法二
void quickSort_another(int *arr, int left, int right)
{
    if (left >= right)
        return;
    int pivot = arr[left];
    int i = left + 1, j = right;
    while (i <= j)
    {
        while (i <= right && arr[i] < pivot)
            i++;
        while (j >= left && arr[j] > pivot)
            j--;
        if (i <= j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    arr[left] = arr[j];
    arr[j] = pivot;
    quickSort_another(arr, left, j - 1);
    quickSort_another(arr, j + 1, right);
}
快速排序导图
快速排序导图

希尔排序

希尔排序，基本思想是选定一个增量 d<nd<n，将元素按此增量分组（所有相距 dd 的元素为一组），然后在各个子序列内进行插入排序，完成后缩小增量 d′(d′<d)d'(d'<d)，如此反复操作，直到增量 d=1d = 1 为止，此时就成了标准的插入排序，但此时大部分元素已经有序，只需要少量操作，甚至不用操作即可完成排序。该排序算法为不稳定排序。

希尔排序还是比较绕的，需要多看看，多画一画。

最坏时间复杂度：O(n2)O(n^2)
nn 在某范围内可达：O(n1.3)O(n^{1.3})
目前无法用数学手段证明确切的时间复杂度。

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
#include <iostream>

using namespace std;

void shellSort(int arr[], int n);

int main()
{
    int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    shellSort(arr, length);
    for (int i = 1; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

void shellSort(int arr[], int n)
{
    int d, i, j;
    //arr[0]为暂存单元
    for (d = n / 2; d > 0; d /= 2)  //d为步长
    {
        for (i = d + 1; i <= n; i++)    //从子表中第二个元素开始
            if(arr[i] < arr[i - d])     //小于子序列前一项
            {
                arr[0] = arr[i];    //暂存待插入元素
                for (j = i - d; j > 0 && arr[0] < arr[j]; j -= d)
                    arr[j + d] = arr[j];    //向后移动，为待插入元素腾出空位
                arr[j + d] = arr[0];    //插入暂存元素
            }
    }
}
希尔排序导图
希尔排序导图
快来参与讨论吧