数据结构 —— 八大排序（超详细图解 & 函数实现）_数据结构排序

系列文章目录

数据结构 —— 顺序表
数据结构 —— 单链表
数据结构 —— 双向链表
数据结构 —— 队列
数据结构 —— 栈
数据结构 —— 堆
数据结构 —— 二叉树
数据结构 —— 八大排序

---

---

前言

排序算法主要分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、计数排序等。本文将针对上述八大排序算法进行图解剖析。

---

一、排序分类

二、排序算法

● 插入排序

1.思想

直接插入排序: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想。

2.图解

3.代码

// 插入排序
void InsertSort(int *arr, int size) {
    for (int i = 1; i < size; i++) {
        int num = arr[i];
        int end = i - 1;
        for (; end >= 0; end--) {
            if (arr[end] > num) {
                arr[end + 1] = arr[end];
            } else {
                break;
            }
        }
        arr[end + 1] = num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.特性

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

● 希尔排序

1.思想

希尔排序（缩小增量排序）: 先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

2.图解

3.代码

// 希尔排序
void ShellSort(int *arr, int size) {
    int gap = size;
    while (gap > 1) {   // 降gap
        gap = gap / 3 + 1;
        for (int cur = gap; cur < size; cur++) {    // 排序
            int num = arr[cur];
            int end = cur - gap;
            for (; end >= 0; end -= gap) {
                if (arr[end] > num) {
                    arr[end + gap] = arr[end];
                } else {
                    break;
                }
            }
            arr[end + gap] = num;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.特性

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。因为gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，于是时间复杂度我们就取用：O(N^1.3) ~ O(N²)

● 选择排序

1.思想

直接选择排序: 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.图解

• 在元素集合array[ i ] ~ array[ n - 1 ]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
• 在剩余的array[ i ] ~ array[ n - 2 ] (array[ i + 1 ] ~ array[ n - 1 ]) 集合中，重复上述步骤，直到集合剩余1个元素

3.代码

// 算法 数值交换
void Swap(void *A, void *B, int size) {
    while (size--) {
        char tmp = *(char *)A;
        *(char *)A = *(char *)B;
        *(char *)B = tmp;
        A = (char *)A + 1;
        B = (char *)B + 1;
    }
}

// 最坏最好都是(n ^ 2)
void SelectSort(int *a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        // 选出最小的放begin位置
        // 选出最大的放end位置
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i) {
            if (a[i] > a[maxi]) {
                maxi = i;
            }

            if (a[i] < a[mini]) {
                mini = i;
            }
        }

        Swap(&a[begin], &a[mini], sizeof(int));
        // 修正一下maxi
        if (maxi == begin) {
            maxi = mini;
        }
        Swap(&a[end], &a[maxi], sizeof(int));
        ++begin;
        --end;
    }
}
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

4.特性

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

● 堆排序

1.思想

堆排序(Heapsort): 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

2.图解

3.代码

#define BIGHEAP >       // 大堆
#define SMAHEAP <       // 小堆
#define CMP BIGHEAP

typedef int DataType;

// 算法 数值交换
void Swap(void *A, void *B, int size) {
    while (size--) {
        char tmp = *(char *)A;
        *(char *)A = *(char *)B;
        *(char *)B = tmp;
        A = (char *)A + 1;
        B = (char *)B + 1;
    }
}

// 算法 向下调整
void AdjustDown(DataType *array, int size, int parent) {
    int child = parent * 2 + 1;
    while (child < size) {
        // 找出最小的孩子
        if (child + 1< size && array[child + 1] CMP array[child]) {
            child++;
        }
        // 判断下调
        if (array[child] CMP array[parent]) {
            Swap(&array[child], &array[parent], sizeof(DataType));
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 堆排序
void HeapSort(int *array, int size) {
    for (int i = (size - 2) / 2; i >= 0; i--) {     //O(N)
        AdjustDown(array, size, i);
    }
    for (int i = 1; i < size; i++) {                //O(N * logN)
        Swap(&array[0], &array[size - i], sizeof(int));
        AdjustDown(array, size - i, 0);
    }
}

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

4.特性

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N * log₂N)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

● 冒泡排序

1.思想

冒泡排序: ：冒泡排序即交换排序，所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.图解

3.代码

// 算法 数值交换
void Swap(void *A, void *B, int size) {
    while (size--) {
        char tmp = *(char *)A;
        *(char *)A = *(char *)B;
        *(char *)B = tmp;
        A = (char *)A + 1;
        B = (char *)B + 1;
    }
}

// 最坏O(N ^ 2)
// 最好O(N)
void BubbleSort(int *arr, int size) {
    for (int i = size; i > 0; i--) {
        int exchange = 0;
        for (int j = 1; j < i; j++) {
            if (arr[j - 1] > arr[j]) {
                exchange = 1;
                Swap(&arr[j - 1], &arr[j], sizeof(int));
            }
        }
        if (exchange == 0) {
            break;
        }
    }
}
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

4.特性

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

● 快速排序

1.思想

快速排序: 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.图解

• hoare版本
  

• 挖坑法

• 双指针法
  

3.代码

• hoare版本

// 插入排序
void InsertSort(int *arr, int size) {
    for (int i = 1; i < size; i++) {
        int num = arr[i];
        int end = i - 1;
        for (; end >= 0; end--) {
            if (arr[end] > num) {
                arr[end + 1] = arr[end];
            } else {
                break;
            }
        }
        arr[end + 1] = num;
    }
}

// 算法 数值交换
void Swap(void *A, void *B, int size) {
    while (size--) {
        char tmp = *(char *)A;
        *(char *)A = *(char *)B;
        *(char *)B = tmp;
        A = (char *)A + 1;
        B = (char *)B + 1;
    }
}

// 取中间值
int GetMidIndex(int *arr, int left, int right) {
    int mid = left + (right - left) / 2;    // 防止相加溢出
    if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) || (arr[mid] >= arr[left] && arr[left] >= arr[right])) {
        return left;
    } else if ((arr[mid] <= arr[right] && arr[right] <= arr[left]) || (arr[mid] >= arr[right] && arr[right] >= arr[left])) {
        return right;
    } else {
        return mid;
    }
}

// 单趟排序
int PartSort(int *arr, int left, int right) {
    int mid = GetMidIndex(arr, left, right);
    Swap(&arr[left], &arr[mid], sizeof(int));

    int keyi = left;
    while (left < right) {
        // R找小
        while (left < right && arr[right] >= arr[keyi]) {
            right--;
        }
        // L找大
        while (left < right && arr[left] <= arr[keyi]) {
            left++;
        }
        if (left < right) {
            Swap(&arr[left], &arr[right], sizeof(int));
        }
    }
    Swap(&arr[keyi], &arr[left], sizeof(int));
    return left;
}

// 快速排序
void QuickSort(int *arr, int begin, int end) {
    if (begin >= end) {
        return;
    }
    if (end - begin <= 8) {
        InsertSort(arr + begin, end - begin + 1);
    } else {
        int keyi = PartSort(arr, begin, end);   // 算出枢轴值
        QuickSort(arr, begin, keyi - 1);            // 对低子表递归排序
        QuickSort(arr, keyi + 1, end);            // 对高子表递归排序
    }
}

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

• 挖坑法

// 插入排序
void InsertSort(int *arr, int size) {
    for (int i = 1; i < size; i++) {
        int num = arr[i];
        int end = i - 1;
        for (; end >= 0; end--) {
            if (arr[end] > num) {
                arr[end + 1] = arr[end];
            } else {
                break;
            }
        }
        arr[end + 1] = num;
    }
}

// 算法 数值交换
void Swap(void *A, void *B, int size) {
    while (size--) {
        char tmp = *(char *)A;
        *(char *)A = *(char *)B;
        *(char *)B = tmp;
        A = (char *)A + 1;
        B = (char *)B + 1;
    }
}

// 取中间值
int GetMidIndex(int *arr, int left, int right) {
    int mid = left + (right - left) / 2;    // 防止相加溢出
    if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) || (arr[mid] >= arr[left] && arr[left] >= arr[right])) {
        return left;
    } else if ((arr[mid] <= arr[right] && arr[right] <= arr[left]) || (arr[mid] >= arr[right] && arr[right] >= arr[left])) {
        return right;
    } else {
        return mid;
    }
}

// 单趟排序
int PartSort(int *arr, int left, int right) {
    // 三数取中
    int mid = GetMidIndex(arr, left, right);
    Swap(&arr[left], &arr[mid], sizeof(int));

    int hole = left;                                    // 记录坑hole
    int key = arr[left];                                // 记录key
    while (left < right) {                              // 左右相遇
        while (left < right && key <= arr[right]) {     // 找右边比坑小的位置
            right--;
        }
        arr[hole] = arr[right];                         // 填坑
        hole = right;                                   // 新坑位

        while (left < right && key >= arr[left]) {      // 找左边比坑大的位置
            left++;
        }
        arr[hole] = arr[left];                          // 填坑
        hole = left;                                    // 新坑位
    }
    arr[hole] = key;                                    // key填入坑
    return hole;
}

// 快速排序
void QuickSort(int *arr, int begin, int end) {
    if (begin >= end) {
        return;
    }
    if (end - begin <= 8) {
        InsertSort(arr + begin, end - begin + 1);
    } else {
        int keyi = PartSort(arr, begin, end);   // 算出枢轴值
        QuickSort(arr, begin, keyi - 1);            // 对低子表递归排序
        QuickSort(arr, keyi + 1, end);            // 对高子表递归排序
    }
}
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

• 双指针法

// 插入排序
void InsertSort(int *arr, int size) {
    for (int i = 1; i < size; i++) {
        int num = arr[i];
        int end = i - 1;
        for (; end >= 0; end--) {
            if (arr[end] > num) {
                arr[end + 1] = arr[end];
            } else {
                break;
            }
        }
        arr[end + 1] = num;
    }
}

// 算法 数值交换
void Swap(void *A, void *B, int size) {
    while (size--) {
        char tmp = *(char *)A;
        *(char *)A = *(char *)B;
        *(char *)B = tmp;
        A = (char *)A + 1;
        B = (char *)B + 1;
    }
}

// 取中间值
int GetMidIndex(int *arr, int left, int right) {
    int mid = left + (right - left) / 2;    // 防止相加溢出
    if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) || (arr[mid] >= arr[left] && arr[left] >= arr[right])) {
        return left;
    } else if ((arr[mid] <= arr[right] && arr[right] <= arr[left]) || (arr[mid] >= arr[right] && arr[right] >= arr[left])) {
        return right;
    } else {
        return mid;
    }
}

// 单趟排序
int PartSort(int *arr, int left, int right) {
    // 三数取中
    int mid = GetMidIndex(arr, left, right);
    Swap(&arr[left], &arr[mid], sizeof(int));

    int keyi = left;
    int prev = left;
    int curr = prev + 1;

    while (curr <= right) {
        // 找小
        if (arr[curr] < arr[keyi] && ++prev != curr) {
            Swap(&arr[curr], &arr[prev], sizeof(int));
        }
        curr++;
    }

    Swap(&arr[keyi], &arr[prev], sizeof(int));

    return prev;
}

// 快速排序
void QuickSort(int *arr, int begin, int end) {
    if (begin >= end) {
        return;
    }
    if (end - begin <= 8) {
        InsertSort(arr + begin, end - begin + 1);
    } else {
        int keyi = PartSort(arr, begin, end);   // 算出枢轴值
        QuickSort(arr, begin, keyi - 1);            // 对低子表递归排序
        QuickSort(arr, keyi + 1, end);            // 对高子表递归排序
    }
}
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

4.特性

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N * log₂N)
3. 空间复杂度：O(log₂N)
4. 稳定性：不稳定

● 归并排序

1.思想

归并排序: 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.图解

3.代码

void _MergeSort(int *arr, int left, int right, int *mat) {
    // 停止条件
    if (left >= right) {
        return;
    }

    // 递归到最深处
    int mid = (left + right) >> 1;      //除2
    _MergeSort(arr, left, mid, mat);
    _MergeSort(arr, mid + 1, right, mat);

    // 创建临时变量
    int begin1 = left, end1 = mid;          // 左半部分
    int begin2 = mid + 1, end2 = right;     // 右半部分

    // 谁小拷贝进新数组
    int i = left;
    while (begin1 <= end1 && begin2 <= end2) {
        mat[i++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];
    }

    // 将剩余部分拷贝进新数组
    while (begin1 <= end1) {
        mat[i++] = arr[begin1++];
    }
    while (begin2 <= end2) {
        mat[i++] = arr[begin2++];
    }

    // 归并完成后拷贝回原数组
    for (int j = left; j <= right; j++) {
        arr[j] = mat[j];
    }
}

void MergeSort(int *arr, int n) {
    int *mat = (int *)malloc(n * sizeof(int));
    if (mat == NULL) {
        perror("mat malloc fail:");
    }
    // 调用递归
    _MergeSort(arr, 0, n - 1, mat);

    free(mat);
}
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

4.特性

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N * log₂N)
3. 空间复杂度：O(N)
4. 稳定性：稳定

● 计数排序

1.思想

计数排序: 计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

2.图解

3.代码

void CountSort(int *arr, int n) {
    // 选取最大的最小值
    int max = arr[0], min = arr[0];
    for (int i = 0; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    // 计算范围
    int range = max - min + 1;
    // 开辟空间
    int *count = (int *)malloc(range * sizeof(int));
    memset(count, 0, range * sizeof(int));
    // 统计数字个数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    // 按顺序放入
    int i = 0;
    for (int j = 0; j < range; j++) {
        // 按数字个数放入
        while (count[j]--) {
            arr[i++] = j + min;
        }
    }
}
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

4.特性

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

三、排序算法比较

---

四、总结

排序算法是解决实际问题时极其常用的算法，是非常重要的解决问题的方式。排序算法函数的复现，有利于更好的学习排序的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。