企业官网建设流程全解析

1. 引文

排序在实际⽣活中随处可⻅，如购物软件中通过综合评分、评价、价格等排序商品⽅便筛选。再或 者⼤学综合实⼒排⾏榜，再或者华润富豪排⾏榜等等。

1.1 常见的排序算法

其中就有我们上章讲的堆排序。

1.2 排序算法的评价标准

• 复杂度：评价排序算法的第一大指标就是时间复杂度和空间复杂度，它衡量算法的时间效率和空间效率。
• 稳定性：假定在待排序的数据元中有两个元素 Ri和 Rj，他们对应的关键字为Ri和 Rj且 (Ri=Rj)，排序前 Ri 在 Rj 的前面，排序后可以保证Ri依旧在 Rj 的前面 (相对顺序不变)，则称这个排序算法是稳定的。

1.3 内部排序和外部排序

• 由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可以将排序方法分为两大类：

内部排序：待排序的记录存放在计算机随机存储器 (内存) 中进行排序的过程。内部排序关注如何让复杂度更低。

外部排序：待排序的记录数据量太大，以致内存一次不能容纳全部记录，在排序过程中需要对外存 (硬盘) 进行访问的排序过程。外部排序关注如何使读写硬盘的次数更少。

• DDR5 内存的读写速度可以达到 50-100GB/s，机械硬盘 (HDD) 的读写速度 80-200MB/s，顶级固态硬盘 (SSD) 读写速度约为 7-14GB/s，内存的速度是顶级固态硬盘 5-10 倍，所以外排序影响性能的是读写硬盘的次数。

2. 插入排序

2.1 直接插入排序

2.1.1 思想以及过程

插⼊排序类似于玩扑克牌(⽃地主)等插牌过程，每次将⼀个待排序的元素按照其关键字⼤⼩插⼊到 前⾯已排好序的序列中，按照该种⽅式将所有元素全部插⼊完成即可。

void InsertSort(int* a, int n) { for (int i = 0; i < n-1; i++) { int end = i; //单趟 int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } }

2.1.2 复杂度和稳定性

• 直接插入排序最好情况为正序，如：要排升序，序列本身为升序，则每次不需要挪动数据，数据间比较 n-1 次，则时间复杂度为 (O(n))
• 直接插入排序最坏情况为逆序，如：要排升序，序列本身为降序，则挪动数据的次数是一个 1 至 n-1 等差数列，则时间复杂度为 (O(n^2))
• 直接插入排序只需要常数个辅助变量，空间复杂度为 (O(1))
• 从上述结论可见直接插入排序比较挑序列的原始顺序，当序列顺序有序或接近顺序有序时，效率较高。
• 直接插入排序只要 end+1 位置的值插入到[0,end]序列比较时，相等则插入到相等值的后面位置则可以保持稳定性。

2.2 希尔排序

• 希尔排序是直接插入排序的一种改进，又称缩小增量排序，是 1959 年由 Donald Shell 提出来的。
• 直接插入排序在逆序的情况下，每次单趟插入都需要大量挪动数据。希尔排序是将待排序序列下标按照增量 d 分为若干组，对每组数据分别进行直接插入排序。然后再不断缩小增量 d，当 d>1 时，可以认为上述过程为预排序，它会让待排序序列接近正序，当 d==1 时，上述过程就是直接插入排序，保证数据有序。这样最后一趟 d==1 时效率就很高。（d>1 称为预排序只是我们方便理解定义的名词，并不是官方叫法）
• 总结一下希尔排序的本质是先通过预排序 (d>1) 让待排序序列接近有序，最后再通过直接插入排序 (d==1) 快速让序列有序。

2.2.1 代码实现

• Shell 提出的缩小增量方案为d = d/2;
• Knuth 提出的缩小增量方案为d = d/3+1;
• Knuth 的方案高效简洁，应用非常广泛，在很多算法教科书和实际工程代码中都能见到它的身影。

//希尔排序 void ShellSort(int* a, int n) { int d = n; while (d > 1) { d = d / 3 + 1;//缩小增量 //d组并行 for (int i = 0; i < n - d; i++) { int end = i; int tmp = a[end + d]; while (end >= 0) { if (tmp < a[end]) { a[end + d] = a[end]; end -= d; } else { break; } } a[end + d] = tmp; } } }

2.2.2 复杂度和稳定性

• 希尔排序的时间复杂度和稳定性，相比于直接插入排序，要复杂得多。因为它依赖于 “增量序列” 的选择，并且涉及一些尚未完全解决的数学问题 (希尔排序涉及多轮插入排序，前一轮排序的结果会影响后一轮的初始状态（即 “预排序” 效果）。分析这种多轮交互对逆序数的具体减少量在数学上非常困难)。直到今天，对于一些增量序列，其精确的时间复杂度仍然是一个开放的研究问题。
• Shell 提出的缩小增量方案为 d = d/2，如果数组恰好在奇数位置均是很小的数，偶数位置均是很大的数，且增量序列有公因子（如 8,4,2,1），那么前几轮预排序几乎没起到什么作用，直到最后一轮 d=1 时，数据几乎还是乱的，导致插入排序近乎满负荷运行，从而退化成平方级复杂度，最坏情况下复杂度经过证明为 \(O(n^2)\)，平均情况时间复杂度经过证明为 \(O(n^2)\)。
• Knuth 提出的缩小增量方案为 d = d/3+1，最坏情况时间复杂度经过严格证明为 \(O(n^{1.5})\)；而平均情况时间复杂度为 \(O(n^{1.25})\)，至今尚未得到严格的数学证明，但是包括 Knuth 本人在内的多位科学家通过复杂的数学分析，给出了非常接近这个结论的论证，大量试验数据也和这个结论吻合。
• 希尔排序⽆法保持稳定性，相同的值预排时可能分到不同的组，不同组排序，则相对顺序就乱了

2.2.3 练习

用希尔排序方法对一个数据序列进行排序时，若第 1 趟排序结果为 9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是_B__

A. 2 B. 3 C. 4 D. 5

对初始数据序列（8,3,9,11,2,1,4,7,5,10,6）进行希尔排序。若第一趟排序结果为 (1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为 (1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量（间隔）依次是__D__

A. 3,1 B. 3,2 C. 5,2 D. 5,3

3. 选择排序

3.1 简单选择排序

3.1.1 思想及过程

每一趟选出最大或者最小的元素，作为有序列序列的第i个元素，每一趟排一个元素，排n-1趟之后就是有序了。

//简单选择排序 void SelectSort(int* a, int n) { //每次选出最小的或者选出最大的 for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n ; j++) { if (a[min] > a[j]) { min = j; } } if (min != i) { Swap(&a[min], &a[i]); } } }

3.1.2 复杂度和稳定性

• 无论待排序序列为正序、逆序、乱序，每趟都需要去比较选出最小数据，累积比较次数为 1 至 n-1 的等差数列，所以简单选择排序时间复杂度为 (O(n^2))
• 简单选择排序只需要常数个辅助变量，空间复杂度为 (O(1))
• 简单选择排序无法保持稳定性，如 {5,6,5,0,2,0,3} 我们可以遍历一遍选出第一个 0 交换到最左边的位置，保持 0 的相对顺序，但是在交换过程中 5 的相对顺序就被破坏了，所以简单选择排序无法保持稳定性。

3.2 堆排序

堆排序也是⼀种选择排序，简单选择排序每次使⽤暴⼒遍历来选出最⼩或者最⼤的数，⽽堆排序则 数组逻辑上看做完全⼆叉树，建堆/调堆后来选出最⼤或最⼤的数实现排序，堆排序思想及实现细 节在树和⼆叉树章节已经讲过了，你们可以去上一文看看。

4. 交换排序

4.1 冒泡排序

思想：假设排升序，⼀趟冒泡结束后，会将最⼤元素放在区间最后，即最⼤元素已经排列好。 下⼀趟冒泡可以对除最⼤元素外的⼦序列从前往后继续冒泡，结束后次⼤元素就可以排列好。以此 类推，共趟冒泡后序列就排好了。注意最后⼀趟区间中只有⼀个元素，本趟冒泡可以不需 要，因此是n-1趟冒泡过程。

//冒泡排序 void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { //单趟冒泡排序 int flag = 0; for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); flag = 1; } } if (flag == 0) { break; } } }

4.1.1 复杂度和稳定性

• 最坏情况下，序列逆序，累积比较次数为 1 至 n-1 的等差数列，所以冒泡排序时间复杂度为 (O(n^2))
• 最好情况下，序列正序，比较 n-1 次，没有发生交换，时间复杂度为 (O(n))。
• 冒泡排序只需要常数个辅助变量，空间复杂度为 (O(1))
• 冒泡排序比较时，前一个元素等于后一个元素时不交换，则可以保持稳定性。

4.2 快速排序

4.2.1 思想及实现

• 快速排序由 C.A.R.Hoare 在 1960 年提出的，是基于分治思想。它是在待排序区间中任取一个元素作为枢轴 (pivot，或称基准值，通常选取区间首元素)，然后按照基准值大小将区间中元素分割成左右两部分，左侧区间中元素小于等于基准值，右侧区间中元素大于等于基准值 (升序是这样，降序就是反过来)，即基准值已经放在最终该放的位置上，该过程称为一次单趟划分。划分结束后再对基准值左右两段子区间重复执行上述过程的过程 (一般使用递归)，直到子区间只有一个值或者不存在。

4.2.2 挖坑法

挖坑法的过程：

1. 假设用最左边的值做枢轴基准值，把最左边的 23 保存到 pivotkey，左边就形成了第一个坑
2. right 找比基准值 pivotkey 小的，找到后放到 left 指向的坑，那么 right 位置就成为新的坑
3. left 找比基准值 pivotkey 大的，找到后放到 right 指向的坑，那么 left 位置就成为新的坑
4. 不断重复 2 和 3 的步骤，直到 left 和 right 相遇，left 和 right 相遇一定是在坑，最后把 pivotkey 放到这个位置就完成了单趟划分

//挖空法 int PartitionDigHole(int* a, int left, int right) { int pivotkeyi = a[left]; while (left < right) { //从左边找小的，来填右边的位置（pivotkeyi） while (left < right && a[right] >= pivotkeyi) { right--; } //找到了,替换位置 a[left] = a[right]; //从右边找大的，来填左边的位置 while (left < right && a[left] <= pivotkeyi) { left++; } //找到了，替换位置 a[right] = a[left]; } //将基准值放到相遇的位置 a[left] = pivotkeyi; //返回相遇的位置的坐标 return left; } void QuickSort(int* a, int left, int right) { if (left >= right) { return -1; } //找基准值，确定基准值的位置 int pivotkeyi = PartitionLomuto(a, left, right); //int pivotkeyi = PartitionDigHole(a, left, right); //递归 //左区间 QuickSort(a, left, pivotkeyi - 1); //右区间 QuickSort(a, pivotkeyi + 1, right); }

4.2.3 Lomuto法

Lomuto 法的过程：

1. 假设用最右边的值做枢轴基准值，最左边也是可以的，处理细节微调即可
2. 最开始 prev 和 cur 一前一后指向区间开始位置
3. cur 找到比 pivotkey 小 (或等) 的值，跟 ++prev 位置的值交换，++prev 一定是比 pivotkey 大的值，所以这里相当于把小于 (或等) pivotkey 换到的前面，把大于 pivotkey 的值换到的后面
4. 不断重复 3 步骤，直到 cur 走到右边界 pivotkey 位置结束，交换 prev+1 和 pivotkey 位置的值，这边就把 pivotkey 换到了中间，pivotkey 左边区间小于等于 pivotkey，右边区间大于 pivotkey

//Lumoto的单趟划分 int PartitionLomuto(int* a, int left, int right) { int pivotkeyi = a[right]; int cur = left; int prev = left - 1; while (cur < right) { if (a[cur] <= pivotkeyi) { prev++; Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev + 1], &a[right]); return prev + 1; }

5. 计数排序

5.1 思想及过程

计数排序是⼀种⾮⽐较型的整数排序算法。它的核⼼思想不是通过“⽐较”元素的⼤⼩来决定顺序， ⽽是通过统计每个元素出现的次数，直接计算出该元素在最终有序数组中的位置。

思想：遍历 a 数组，a [i] 值映射到 count 计数数组对应位置计数，数组中的值是多少就对 count 对应位置 ++，count [a [i]]++，这样 a 数组遍历完以后，count 数组就统计除了 a 数组中值出现了几次。

//计数排序 void CountSort(int* a, int n) { //遍历一遍选出最大和最小的值 int min = a[0]; int max = a[0]; for (int i = 0; i < n; i++) { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } int range = max - min + 1; //开辟数组空间来计数 int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { perror("calloc::count()"); return; } //统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //count[i]记录<=映射值x的个数 for (int i = 1; i < range; i++) { //当前位置等于前面次数的累加和 count[i] += count[i - 1]; } //开辟空间来存放数据，然后将这个数组拷贝回原数组即可 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc()::tmp()"); return; } //存放数据，从后往前处理，确保稳定性 for (int i = n - 1; i >= 0; i--) { tmp[count[a[i] - min] - 1] = a[i]; count[a[i] - min]--; } //拷贝 memcpy(a, tmp, sizeof(int) * n); //释放 free(count); free(tmp); } void TestCountSort() { //int a[] = { 14,19,13,10,19,14,19,18 }; int a[] = { 6,1,2,9,4,2,4,1,4,-5,-5,-3,6 }; PrintArray(a, sizeof(a) / sizeof(int)); CountSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); }

5.2 复杂度和稳定性

• 假设 n 是数据个数，range 为数据范围，则时间复杂度为 (O(n+range))，若 range 接近于 n，则时间复杂度 (O(n))，明显优于 (O(nlogn)) 级别的快排 / 堆排等，说明计数排序适合范围比较集中的整数进行排序，可以得到超乎想象的效率。
• 空间复杂度也是 (O(n+range))。
• 计数排序只要计算元素位置时，从后往前处理可以保证稳定性。

6. GitHub

完整代码已经上传GitHub，欢迎Star

GitHub - PeterYuanCoder/ds-c-programs: 记录我学习C和数据结构的学习过程 · GitHub