排序算法排序 (Sorting): 将一串数据依照指定方式进行排列常用排序方式 : 数值顺序, 字典顺序时间复杂度 ( 最差平均 ): 设有 n 个数据, 一般来说, 好的排序算法性能是 O(n log n), 差的性能是 O(n 2 ), 而理想的性能是 O(n) 空间复杂度 : 算法在运

Size: px

Start display at page:

Download "排序算法排序 (Sorting): 将一串数据依照指定方式进行排列常用排序方式 : 数值顺序, 字典顺序时间复杂度 ( 最差平均 ): 设有 n 个数据, 一般来说, 好的排序算法性能是 O(n log n), 差的性能是 O(n 2 ), 而理想的性能是 O(n) 空间复杂度 : 算法在运"

役士从
5 years ago
Views:

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

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

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

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

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

6 一选择排序原始序列 : 第 1 轮排序 : 第 2 轮排序 : 第 3 轮排序 : 第 4 轮排序 : 第 5 轮排序 : 第 6 轮排序 : 第 7 轮排序 : 第 8 轮排序 : 第 9 轮排序 : MATLAB 演示 :sort_min.m 6

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; % 交换 } } 7

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; } sort_min.cpp sort_min cpp 8

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

10 二插入排序原始序列 : 第 1 轮排序 : 第 2 轮排序 : 第 3 轮排序 : 第 4 轮排序 : 第 5 轮排序 : 第 6 轮排序 : 第 7 轮排序 : 第 8 轮排序 : 第 9 轮排序 : MATLAB 演示 :sort_insert.m 10

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

12 插入排序 C++ 程序以第 4 轮为例比较方向操作对象 x[k] 先比较 2 后移位

13 插入排序 C++ 程序 // 插入排序 ( 部分代码 ) 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) 留作练习 13

14 三希尔排序又称为缩小增量排序 (Diminishing Increment Sort), 由 D. Shell 于 1959 年提出, 是对插入排序的改进 14

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

16 三希尔排序第一轮 :gap=10/2= 第一轮排序后

17 三希尔排序第二轮 :gap=gap/2= 第二轮排序后

18 三希尔排序第三轮 :gap=gap/2= 第三轮排序后在最坏的情况下, 插入排序需要 O(n 2 ) 次移位操作, 而希尔排序只需 O(n 1.5 ) 次移位操作例 : 以 n=8 为例, 统计最坏情况下插入排序与希尔排序的移位操作次数 MATLAB 演示 :sort_shell.m 18

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

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

21 四冒泡排序 x x x x x MATLAB 演示 :sort_bubble.m 21

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

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

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

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

26 快速排序原始序列 : 第一步的具体实现方法 :( 假定基准数的原始位置是 i 1 =1) 1) 先从原序列的最右边开始, 往左找出第一个小于 6 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 2 2) 从 i 1 右边的位置开始, 往右找出第一个大于 6 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 3 3) 从 i 2 左边的位置开始, 往左找出第一个小于 6 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 4 4) 从 i 3 右边的位置开始, 往右找出第一个大于 6 的数, 然后将该数与基准数交换位置, 设基准数新位置为 i 5 5) 不断重复以上过程, 遍历整个序列 26

27 快速排序举例原始序列 : 第一步 : 我们选第一个元素为基准数, 即将 6 作为基准数我们的目标是得到一个新序列, 使得在这个新序列中, 排在 6 前面的数字都小于 6, 而排在 6 后面的数字都不小于 6 搜索基准数 i 1 =1 需交换位置的数搜索起始位置 27

28 举例 : 第一步新序列 : i 1 =1 i 2 =8 28

29 举例 : 第一步新序列 : 搜索 i 1 =1 需交换位置的数基准数 i 2 =8 新序列 : i 3 =4 25

30 举例 : 第一步 i 3 =4 i 2 = i 4 = 第一步结束! i 5 =6 30

31 举例 : 第二步第二步 : 对基准数所在位置前面的子序列和后面的子序列, 分别重复第一步的过程

不断重复 : 递归 2 1 3 4 5 6 8 7 9 10 1 2 3 4 5 6 7 8 9 10

32 不断重复 : 递归排序结束! MATLAB 演示 :sort_quick.m 32

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

34 上机作业 (1) 编写插入排序的 C++ 程序, 程序取名 hw08_01.cpp 排序函数名 :void sort_insert(int* px, int n) (2) 编写 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) 34

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,