第八讲 排序算法 —— C++ 实现

排序算法 排序 (Sorting)：将一串数据依照指定方式进行排列。 常用排序方式：数值顺序，字典顺序。 时间复杂度（最差、平均）： 设有 n 个数据，一般来说，好的排序算法性能是 O(n log n)，差的性能是 O(n2)，而理想的性能是 O(n)。 空间复杂度： 算法在运行过程中临时占用存储空间的大小。 稳定排序算法：相等的数据维持原有相对次序

常见排序算法 O(n log n) O(n1.5) O(n · k) O(n + k) O(n + D) 算法 平均时间复杂度 选择排序 归并排序 O(n log n) 插入排序 堆排序 希尔排序 O(n1.5) 图书馆排序 冒泡排序 基数排序 O(n · k) 快速排序 桶排序 O(n + k) 计数排序 鸽巢排序 O(n + D) … … … …

主要内容 选择排序 插入排序 希尔排序 冒泡排序 快速排序 本讲中假定是对数据进行从小到大排序

一、选择排序 —— 有时也称为最小排序 找出最小值，将其与第一个位置的元素进行交换， 然后对剩余的序列重复以上过程，直至排序结束。

一、选择排序 原始序列： 2 8 3 12 5 20 7 14 5 16 第1轮排序：2 8 3 12 5 20 7 14 5 16 第2轮排序：2 3 8 12 5 20 7 14 5 16 第3轮排序：2 3 5 12 8 20 7 14 5 16 第4轮排序：2 3 5 5 8 20 7 14 12 16 第5轮排序：2 3 5 5 7 20 8 14 12 16 第6轮排序：2 3 5 5 7 8 20 14 12 16 第7轮排序：2 3 5 5 7 8 12 14 20 16 第8轮排序：2 3 5 5 7 8 12 14 20 16 第9轮排序：2 3 5 5 7 8 12 14 16 20 MATLAB 演示：sort_min.m

选择排序 C++程序 // 找出最小值所在的位置 int findmin(int *px, int n) { int idx=0, xmin=*px; for (int i=1; i<n; i++) if (*(px+i)<xmin) { xmin=*(px+i); idx=i; } return idx; } // 选择排序(最小排序) void sort_min(int *px, int n) { int idx, t; for(int k=0; k<n; k++) { idx=findmin(px+k,n-k); t=px[k]; px[k]=px[k+idx]; px[k+idx]=t; % 交换 }

选择排序 C++程序 sort_min.cpp sort_min100000.cpp int main() { int x[]={2, 8, 3, 12, 5, 20, 7, 14, 5, 16}; int n, i; // 获取数据个数 n = sizeof(x)/sizeof(x[0]); cout << "x=\n"; // 输出原始数据 for(i=0;i<n;i++) cout << setw(3) << x[i]; cout << endl; sort_min(x, n); // 排序 cout << "排序后：\n"; // 输出排序后结果 return 0; } sort_min.cpp sort_min100000.cpp

二、插入排序 基本思想描述如下： 假设前面 k 个元素已经按顺序排好了，在排第 k+1 个 元素时，将其插入到前面已排好的 k 个元素中，使得 插入后得到的 k+1 个元素组成的序列仍按值有序。 然后采用同样的方法排第 k+2 个元素。 以此类推，直到排完序列的所有元素为止。

二、插入排序 原始序列： 2 8 3 12 5 20 7 14 5 16 第1轮排序：2 8 3 12 5 20 7 14 5 16 第2轮排序：2 3 8 12 5 20 7 14 5 16 第3轮排序：2 3 8 12 5 20 7 14 5 16 第4轮排序：2 3 5 8 12 20 7 14 5 16 第5轮排序：2 3 5 8 12 20 7 14 5 16 第6轮排序：2 3 5 7 8 12 20 14 5 16 第7轮排序：2 3 5 7 8 12 14 20 5 16 第8轮排序：2 3 5 5 7 8 12 14 20 16 第9轮排序：2 3 5 5 7 8 12 14 16 20 MATLAB 演示：sort_insert.m

插入排序 C++ 程序 关键点：如何将第 k+1 个元素插入到前面的有序序列中 假定序列为 x1, x2, …, xk, xk+1, … 策略：将 xk+1 依次与 xk, xk-1, … 进行比较，直至遇见第一个 不大于 xk+1 的元素为止。 优化：可以将比较与移位同时进行。

插入排序 C++ 程序 以第 4 轮为例 操作对象 x[k] 比较方向 2 3 8 12 5 20 7 14 5 16 ①先比较 ②后移位

插入排序 C++ 程序 void sort_insert(int * px, int n) 留作练习 // 插入排序（部分代码） ... ... for(k=1; k<n; k++) { key = x[k]; for (i=k-1; x[i]>key && i>=0; i--) x[i+1] = x[i]; } x[i+1] = key; void sort_insert(int * px, int n) 留作练习

三、希尔排序 又称为“缩小增量排序”（Diminishing Increment Sort），由 D. Shell 于1959年提出，是对插入排序的改进。

三、希尔排序 基本过程描述如下： 把序列按照某个增量（gap）分成几个子序列，对这几个 子序列进行插入排序。 不断缩小增量，扩大每个子序列的元素数量，并对每个 子序列进行插入排序。 当增量为 1 时，子序列就是整个序列，而此时序列已经 基本有序了，因此只需做少量的比较和移动就可以完成 对整个序列的排序。 出发点：插入排序在元素基本有序的情况下，效率很高 gap：初始值设为 n/2，然后不断减半。

三、希尔排序 2 8 3 12 5 20 7 14 5 16 第一轮：gap=10/2=5 2 8 3 12 5 20 7 14 16 第一轮排序后 2 7 3 5 20 8 14 12 16

三、希尔排序 2 7 3 5 5 20 8 14 12 16 第二轮：gap=gap/2=2 2 7 3 5 20 8 14 12 16 第二轮排序后 2 5 3 7 14 8 16 12 20

三、希尔排序 2 5 3 7 5 14 8 16 12 20 第三轮：gap=gap/2=1 第三轮排序后 2 3 5 5 7 8 12 在最坏的情况下，插入排序需要 O(n2)次移位操作，而希尔排序只需 O(n log n) 次移位操作。 例：以 n=8 为例，统计最坏情况下插入排序与希尔排序的移位操作次数 MATLAB 演示：sort_shell.m

希尔排序 C++程序 void sort_shell(int * px, int n) 留作练习

四、冒泡排序 基本过程描述如下： 走访需要排序的序列，比较相邻的两个元素，如果他们 的顺序错误就把他们交换过来。 不断重复上述过程，直到没有元素需要交换，排序结束。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮” 到数列的顶端。

四、冒泡排序 x5 x4 x3 x2 x1 8 14 16 5 20 8 14 16 20 5 8 14 20 16 5 8 20 14 16 5 20 8 14 16 5 MATLAB 演示：sort_bubble.m

四、冒泡排序 具体过程可以描述为： 将第 1 个和第 2 个元素进行比较，如果前者大于后者，则交 换两者的位置，否则位置不变；然后将第 2 个元素与第 3 个 元素进行比较，如果前者大于后者，则交换两者的位置，否 则位置不变；依此类推，直到最后两个元素比较完毕为止。 这就是第一轮冒泡过程，这个过程结束后，最大的元素就 “浮”到了最后一个位置上。 对前面 n-1 个元素进行第二轮冒泡排序，结束后，这 n-1 个 元素中的最大值就被安放在了第 n-1个位置上。 对前面的 n-2个元素进行第三轮冒泡排序。 以此类推，当执行完第 n-1 轮冒泡过程后，排序结束。

冒泡排序 C++ 程序 冒泡排序的优化：如果在某轮冒泡过程中没有发生元素交换，这说明整个序列已经排好序了，这时就不用再进行后面的冒泡过程，可以直接结束程序。 冒泡排序的进一步优化：如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一轮冒泡过程后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。 void sort_bubble(int * px, int n) 留作练习

五、快速排序 —— 是目前最常用的排序算法之一 快速排序采用的是分而治之思想：将原问题分解为若干个 规模更小但结构与原问题相似的子问题，然后递归求解这 些子问题，最后将这些子问题的解组合为原问题的解。

五、快速排序 具体过程可以描述为： 随机选定其中一个元素作为基准数（pivot）（通常采用 第一个元素），然后通过循环和比较运算，将原序列分割成 两部分，使得新序列中在该基准数前面的元素都小于等于这 个元素，而其后面的元素都大于等于这个元素。（这时基准 数已经归位） 依此类推，再对这两个分割好的子序列进行上述过程， 直到排序结束。（递归思想，分而治之）

快速排序 原始序列： 6 1 3 7 5 9 2 4 8 10 第一步的具体实现方法：（假定基准数的原始位置是 i1=1） 从 i1 右边的位置开始，往右找出第一个大于 6 的数，然后 将该数与基准数交换位置，设基准数新位置为 i3 从 i2 左边的位置开始，往左找出第一个小于 6 的数，然后 将该数与基准数交换位置，设基准数新位置为 i4 从 i3 右边的位置开始，往右找出第一个大于 6 的数，然后 将该数与基准数交换位置，设基准数新位置为 i5 不断重复以上过程，遍历整个序列

快速排序举例 原始序列： 6 1 3 7 5 9 2 4 8 10 第一步： 我们选第一个元素为基准数，即将 6 作为基准数。我们的目标是得到一个新序列，使得在这个新序列中，排在 6 前面的数字都小于 6，而排在 6 后面的数字都不小于 6。 6 1 3 7 5 9 2 4 8 10 基准数 需交换位置的数 搜索 i1=1 搜索起始位置

举例：第一步 6 1 3 7 5 9 2 4 8 10 新序列： 4 1 3 7 5 9 2 6 8 10 i1=1 i2=8

举例：第一步 新序列： 4 1 3 7 5 9 2 6 8 10 搜索 4 1 3 7 5 9 2 6 8 10 i1=1 需交换位置的数 基准数 i2=8 新序列： 4 1 3 6 5 9 2 7 8 10 i3=4 25

举例：第一步 第一步结束！ i3=4 i2=8 i4=7 i5=6 4 1 3 6 5 9 2 7 8 10 4 1 3 2 5 9 6 7

举例：第二步 第二步： 对基准数所在位置前面的子序列和后面的子序列，分别重复第一步的过程。 4 1 3 2 5 6 9 7 8 10 2 1

不断重复：递归 2 1 3 4 5 6 8 7 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 排序结束！ MATLAB 演示：sort_quick.m

快速排序 C++ 程序 事实上，在快速排序每一步执行过程中，可以不用交换，而是直接覆盖即可，如何实现？ 快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用其它的方法排序以减小递归深度等等。有兴趣的同学可以深入研究。 void sort_quick(int* px, int left, int right) 留作练习

上机作业 编写插入排序的 C++ 程序，程序取名 hw08_01.cpp 排序函数名：void sort_insert(int* px, int n) 编写 Shell 排序的 C++ 程序，程序取名 hw08_02.cpp 排序函数名： sort_shell(int* px, int n) (3) 编写冒泡排序的 C++ 程序，程序取名 hw08_03.cpp 排序函数名： sort_bubble(int* px, int n) (4) (选作题) 编写快速排序的 C++ 程序， 程序取名 hw08_04.cpp sort_quick(int* px, int left, int right)