华东师范大学：《C++ 语言程序设计》课程教学资源（课件讲稿）第八讲 排序算法

排序算法 排序(Sorting):将一串数据依照指定方式进行排列。 常用排序方式：数值顺序，字典顺序。 算法评价重要指标 时间复杂度（最差、平均) 设有n个数据，一般来说，好的排序算法性能是O(n log n),差的性能是 O(n2),而理想的性能是On)。 空问复杂度 算法在运行过程中临时占用存储空间的大小。 稳定排序算法：相同的数据，排序后仍维持原有相对次序。 http://math.ecnu.edu.cn/~jypan 2

http://math.ecnu.edu.cn/~jypan 2 排序算法 排序 (Sorting)：将一串数据依照指定方式进行排列。 常用排序方式：数值顺序，字典顺序。 时间复杂度（最差、平均） 设有 n 个数据，一般来说，好的排序算法性能是 O(n log n)，差的性能是 O(n2)，而理想的性能是 O(n)。 空间复杂度 算法在运行过程中临时占用存储空间的大小。 算法评价重要指标 稳定排序算法：相同的数据，排序后仍维持原有相对次序

常见排序算法 算法 平均时间复杂度 算法 平均时间复杂度 选择排序 0n2) 归并排序 O(n log n) 插入排序 O(n2) 堆排序 O(n log n) 希尔排序 O(n log2 n) 图书馆排序 O(n log n) 冒泡排序 0n2) 基数排序 O(n·) 快速排序 O(n log n) 桶排序 O(n+k) 计数排序 O(n+k) 鸽巢排序 O(n+D) http://math.ecnu.edu.cn/~jypan 3

http://math.ecnu.edu.cn/~jypan 3 常见排序算法 算法 平均时间复杂度 算法 平均时间复杂度 选择排序 O(n2) 归并排序 O(n log n) 插入排序 O(n2) 堆排序 O(n log n) 希尔排序 O(n log2 n) 图书馆排序 O(n log n) 冒泡排序 O(n2) 基数排序 O(n · k) 快速排序 O(n log n) 桶排序 O(n + k) 计数排序 O(n + k) 鸽巢排序 O(n + D) … … … …

华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents 1 选择排序 4 冒泡排序 2 插入排序 5 快速排序 希尔排序 本讲假定是对数据进行从小到大排序 http://math.ecnu.edu.cn/~jypan

http://math.ecnu.edu.cn/~jypan 目录页 Contents 1 2 选择排序 插入排序 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU 3 希尔排序 本讲假定是对数据进行从小到大排序 4 5 冒泡排序 快速排序

1 选择排序 也称最小排序 基本思想 ·先找出最小值，将其与第一个位置的元素进行交换 ·对剩余的数据重复以上过程，直至排序结束 http://math.ecnu.edu.cn/~jypan

http://math.ecnu.edu.cn/~jypan 1 选择排序 —— 也称 最小排序 基本思想 ► 先找出最小值，将其与第一个位置的元素进行交换 ► 对剩余的数据重复以上过程，直至排序结束

选择排序：示例 原始序列：283 12 5 20 7 145 16 第1轮排序：28 3 12 5 20 14 5 16 第2轮排序：2 3812 20 7 14 5 16 第3轮排序：235 12 8 20 14 5 16 第4轮排序：235 5 14 12 16 第5轮排序：23 5 5 7 20 14 12 16 第6轮排序：2355 7 8 20 14 12 16 第7轮排序：23557 8 12 14 20 16 第8轮排序：2355 7 8 12 14 20 16 第9轮排序：235 578121416 20 MATLAB演示：sort_min.m http://math.ecnu.edu.cn/~jypan 6

http://math.ecnu.edu.cn/~jypan 6 选择排序：示例 原始序列： 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 http://math.ecnu.edu.cn/-jypan

http://math.ecnu.edu.cn/~jypan 7 选择排序：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++程序 Example:sort_selection.cpp Example:sort_selection100000.cpp int main() int×[]={2,8,3,12,5,28,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"/输出排序后结果 for(i=0ji<n;i++)cout <setw(3)<<x[i]; return 0; http://math.ecnu.edu.cn/~jypan 8

http://math.ecnu.edu.cn/~jypan 8 选择排序：C++程序 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"; // 输出排序后结果 for(i=0;i<n;i++) cout << setw(3) << x[i]; return 0; } Example：sort_selection.cpp Example：sort_selection100000.cpp

2 插人排序 基本思想 ·假设前面k个元素已经按顺序排好了，在排第k+1 个元素时，将其插入到前面已排好的k个元素中，使 得插入后得到的k+1个元素组成的序列仍按值有序。 ·然后采用同样的方法排第k+2个元素。 以此类推，直到排完序列的所有元素为止。 http://math.ecnu.edu.cn/~jypan

http://math.ecnu.edu.cn/~jypan 2 插入排序 基本思想 ► 假设前面 k 个元素已经按顺序排好了，在排第 k+1 个元素时，将其插入到前面已排好的 k 个元素中，使 得插入后得到的 k+1 个元素组成的序列仍按值有序。 ► 然后采用同样的方法排第 k+2 个元素。 ► 以此类推，直到排完序列的所有元素为止

示例 有序 待排序 2 8 312520714516 8 312520714516 3125 20 14516 马 3 12 12 5 20 14 516 5 201 14 516 MATLAB演示：sort insert..m http://math.ecnu.edu.cn/~jypan

http://math.ecnu.edu.cn/~jypan 10 示例 2 8 3 12 5 20 7 14 5 16 2 8 8 3 12 5 20 7 14 5 16 有序 待排序 2 3 8 3 12 5 20 7 14 5 16 2 3 8 12 12 5 20 7 14 5 16 2 3 5 8 12 5 20 7 14 5 16 ... ... MATLAB 演示：sort_insert.m

插入排序的实现 关键点：如何将第+1个元素插入到前面的有序序列中？ 假定序列为x1,X2,,x和X1… 策略：将Xk1依次与x和xI,.进行比较， 直至遇见第一个不大于x+1的元素为止。 优化：可以将比较与移位同时进行。 http://math.ecnu.edu.cn/~jypan 11

http://math.ecnu.edu.cn/~jypan 11 插入排序的实现 关键点：如何将第 k+1 个元素插入到前面的有序序列中? 假定序列为 x1, x2, …, xk, xk+1, … 策略：将 xk+1 依次与 xk, xk-1, … 进行比较， 直至遇见第一个不大于 xk+1 的元素为止。 优化：可以将比较与移位同时进行