08_Sort

排序 (Sorting):将一串数据依照指定方式进行排列。常用排序方式:数值顺序,字典顺序。 时间复杂度(最差、平均): 设有 n 个数据,一般来说,好的排序算法性能是 O(n log n),差的性能是 O(n2),而理想的性能是 O(n)。 空间复杂度: 算法在运行过程中临时占用存储空间的大小。 稳定排序算法:相等的数据维持原有相对次序 本章主要讲解排序算法(选择排序、插入排序、希尔排序、冒泡排序、快速排序)
展开查看详情

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

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

3.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 ) … … … …

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

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

6.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

7.7 选择 排序 C ++ 程序 // 找出最小值所在的位置 int findm in ( 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_ m in ( int * px , int n) { int idx , t; for( int k=0; k<n; k++) { idx = findm in ( px+k,n-k ); t= px [k]; px [k]= px [ k+idx ]; px [ k+idx ]=t; % 交换 } }

8.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=

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

10.10 二、插入排序 原 始序列 : 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

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

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

13.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) 留作练习

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

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

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

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

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

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

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

21.21 四、冒泡排序 8 14 16 5 20 x 5 x 4 x 3 x 2 x 1 8 14 16 20 5 8 14 20 16 5 8 20 14 16 5 20 8 14 16 5 MATLAB 演示 : sort_bubble.m

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

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

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

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

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

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

28.28 举例:第一步 6 1 3 7 5 9 2 4 8 10 4 1 3 7 5 9 2 6 8 10 新序 列: i 1 =1 i 2 =8

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