S10.1基本概念 。排序： ◆输入：n个记录R,R2,R,相应的key为K,K2,,K ◆输出：RR2,Rn,使得K,≤K2≤.≤K(或≥) Ch.10排序 稳定性：相同的k©ys经排序后相对次序不变 童内排和外排： ■分类： ①按方法分：插入，选择，交换，归井，分配 @按存贮方式分：顺序表、链表、辅助表 童就地排序：辅助空间O(1) "执用普鑫热条凳ReTypeh同前- 童以下只讨论增序 S10.2插入排序 §10.2.1直接插入排序（续） 基本思想：每次将待排序的记录，依ky大小插入到前面已 ■怎样将R叮插到有序区，使其扩充呢？ 排好序的子文件中的适当位重。 510.21直接播入排序 ①先找到正确的插入位置k(1≤k≤)：然后将 Rk.1-1]中记录后移1位，再插入 思想：待排序记录存于R1小中，排序过程中某一刻，R被 分为两子区间： ②从有序区尾向前查找插入位置，同时做后移操作 R1-1] R[L.n可 (二者交替进行)，直到找到第一个不大于 有序区 无序区（未排） R叮.key的记录为止，并将R叮插入其后。 当前无序区的第1个记录R可插入有序区R[1.i-1们中合适的位 量，使R[1变为有序区 初始时，因为R[1们自然有序，R[2.n为无序区，故只须从 R[2]开始播入 此过程类似于理牌 §10.2.1直接插入排序（续） §10.2.1直接插入排序（续） void InsertSort(SeqList R){ int i,j; 就地排序、稳定的排序 for(=2;i=n;i+)依次播入R2☒，Rn,共进行n-1脑排序 if(R可.key<R-1们key){香刚，R可在原位量上 例子略 RO]=R门：R0]既是喇兵，又起保存R可的作用 时间分析 j=i-1: dof ①最好情况：初始正序 从后向前在有序区R11]中找到第1个不大于R可.k@y的记录 每趟播入R门时，因为它都大于等于R-]的k©y,无须 Rj+1]=R[j]大于Ri】k@y的记录后移 移动，不进入内循环Cmin=n-1,Mm=0 ②最坏情况：韧始反序 while(R0.key<R[j.keyi刚兵防止魅界 ◆比较：每慧排序均需比较R[0.-1]中所有keys(f比较1 R[j+1]=R0:R叮擂入正璃位置循环线止于R[j】.key≤R0.key 次，do中比较1-1次)即比较次 Mendif C-=∑i=0
1 Ch.10 排序 2 §10.1 基本概念 排序： 输入：n个记录R1, R2, …, Rn，相应的key为K1, K2, …, Kn 输出：Ri1, Ri2, …, Rin，使得Ki1≤Ki2 ≤ …≤ Kin(或≥) 稳定性：相同的keys经排序后相对次序不变 内排和外排： 分类： ①按方法分：插入，选择，交换，归并，分配 ②按存贮方式分：顺序表、链表、辅助表 就地排序：辅助空间O(1) 存贮结构说明：设n预先有定义。设RecType同前一章 NodeType。 SeqList为n+1个单元 以下只讨论增序 3 §10.2 插入排序 基本思想：每次将待排序的记录，依key大小插入到前面已 排好序的子文件中的适当位置。 §10.2.1 直接插入排序 思想：待排序记录存于R[1..n]中，排序过程中某一刻，R被 分为两子区间： R[1..i-1] R[i..n] 有序区 无序区（未排） 当前无序区的第1个记录R[i]插入有序区R[1..i-1]中合适的位 置，使R[1..i]变为有序区 初始时，因为R[1]自然有序，R[2..n]为无序区，故只须从 R[2]开始插入 此过程类似于理牌 4 §10.2.1 直接插入排序（续） 怎样将R[i]插到有序区，使其扩充呢？ ① 先找到正确的插入位置k（1≤k ≤ i）；然后将 R[k..i-1]中记录后移1位，再插入 ② 从有序区尾向前查找插入位置，同时做后移操作 （二者交替进行），直到找到第一个不大于 R[i].key的记录为止，并将R[i]插入其后。 5 §10.2.1 直接插入排序（续） void InsertSort(SeqList R){ int i, j; for (i=2; i<=n; i++) //依次插入R[2],..R[n]，共进行n-1趟排序 if (R[i].key<R[i-1].key) {//否则，R[i]在原位置上 R[0] = R[i]; //R[0]既是哨兵，又起保存R[i]的作用 j = i-1; do{ //从后向前在有序区R[1..i-1]中找到第1个不大于R[i].key的记录 R[ j+1] = R[ j ]; //大于R[ i ].key的记录后移 j--; }while (R[0].key<R[ j ].key); //哨兵防止越界 R[ j+1] = R[0];//R[i]插入正确位置,循环终止于R[ j ].key≤R[0].key }//endif } 6 §10.2.1 直接插入排序（续） 就地排序、稳定的排序 例子略 时间分析 ① 最好情况：初始正序 每趟插入R[i]时，因为它都大于等于R[i-1]的key，无须 移动，不进入内循环Cmin=n-1，Mmin=0 ② 最坏情况：初始反序 比较：每趟排序均需比较R[0..i-1]中所有keys（if比较1 次，do中比较i-1次）即比较i次 2 max 2 ( ) n i C i On = = = ∑
§10.2.1直接插入排序（续） §10.2.2希尔排序 ◆移动：内循环中R[1.11]均后移，外加设置哨 兵和将R[叮插到最终位置共移动i-1+2=+1. 希尔排序(Shell Sort,又称缩小增量法)是一种分 M=之+=0 组插入排序方法。 1排序思想 ③平均： 若记录随机分布。比较、移动平均为n214 ①先取一个正整数d(dlength;j++) 第一热排序过程： L->R[0=L->R[jl; 产设置监视哨兵*/ k=j-d; while(k>0&<(L->R[0J.key,L->R[k].key)) L->R[k+d]=L->R[k]k=k-d;} 第二排序后：2519713118153 L->R[k+jl=L->R[0]; 第三趙排序后：125789111313 15 希尔排序过程 然后在根据增量数组dk进行希尔排序。 希尔排序可提高排序速度，原因是： void shell sort(Sqlist *L,int dk[,int t) ◆分组后n值减小，更小，而T(n=0,所以T(o) :按增量序列k0..t-1,对顺序表L进行希尔排序*/ 从总体上看是减小了： intm; ◆关键字较小的记录跳跃式前移，在进行最后一越 for (m=0;m<=t;m++) 增量为1的插入排序时，序列已基本有序。 shll pass(L,dk m]); ◆当n较大时，比较和移动次数约在n25 1.6n125之间 希尔排序的分析比较复杂，涉及一些数学上的问 增量序列取法 题，其时间是所取的“增量”序列的函数。 ◆无除1以外的公因子： 希尔排序特点 ◆最后一个增量值必须为1。 子序列的构成不是简单的“逐段分割”，而是将相隔 某个增量的记录组成一个子序列
7 §10.2.1 直接插入排序（续） 移动：内循环中R[1..i-1]均后移，外加设置哨 兵和将R[i]插到最终位置共移动i-1+2=i+1. ③ 平均： 若记录随机分布。比较、移动平均为n2/4 2 max 2 ( 1) ( ) n i M i On = = += ∑ §10.2.2 希尔排序 希尔排序(Shell Sort，又称缩小增量法)是一种分 组插入排序方法。 1 排序思想 ① 先取一个正整数d1(d1length; j++) { L->R[0]=L->R[j] ; /* 设置监视哨兵 */ k=j-d ; while (k>0&<(L->R[0].key, L->R[k].key) ) { L->R[k+d]=L->R[k] ; k=k-d ; } L->R[k+j]=L->R[0] ; } } 然后在根据增量数组dk进行希尔排序。 void shell_sort(Sqlist *L, int dk[], int t) /* 按增量序列dk[0 … t-1],对顺序表L进行希尔排序 */ { int m ; for (m=0; m<=t; m++) shll_pass(L, dk[m]) ; } 希尔排序的分析比较复杂，涉及一些数学上的问 题，其时间是所取的“增量”序列的函数。 希尔排序特点 子序列的构成不是简单的“逐段分割”，而是将相隔 某个增量的记录组成一个子序列。 希尔排序可提高排序速度，原因是： ◆ 分组后n值减小，n²更小，而T(n)=O(n²),所以T(n) 从总体上看是减小了； ◆ 关键字较小的记录跳跃式前移，在进行最后一趟 增量为1的插入排序时，序列已基本有序。 ◆ 当n较大时，比较和移动次数约在n1.25~ 1.6n1.25之间 增量序列取法 ◆ 无除1以外的公因子； ◆ 最后一个增量值必须为1
§10.3交换排序 S10.3.1冒泡排序 两两比较待排序记录的ky,发现两个记录的次序相反时即 从下向上扫推：熏气泡下沉一个位置，量轻气泡浮顶，量重气 进行交换，童到无反序的记录为止， 泡在顶时要n-1”排序 S10.3.1冒泡排序 袋结控程上泽-个位果气电沉超气 设想待排序的记录败组R[1.n垂直竖立，将每个记录R可看 作是置量为R可ky的气泡。根据轻气泡不能在重气泡之下 的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气 21 泡，就使其向上“飘浮”，如此反复，重到景后任何两气泡都 是轻者在上，重者在下为止。 21 ■从下往上和从上往下交管进行，可改善性能。 初始关赞字序列：2338224523673引154Π void Bubble Sort(Sglist *L) 第一慧排序后：232238234531154167 {int j ,k,flag; 第二热排序后：222323383115414567 for心-0：j-length;j+)片共有m-1慧排序 第三热排序后：222323311538414567 {flag=TRUE 第四排序后：222323153138414567 for(k=1:klength-j;k++)*一趟排序* 第五越#序后：222315233引38414567 if(LT(L->R[k+1].key,L->R[k].key)) 第六趙排序后：221523233引3841567 flag=FALSE;L->R[0]=L->R[k]; 第七热排序后：152223233138414567 L->R[k]=L->R[k+1]; ■泡排序过程 L->Rk+1-L->R0; } if (flag==TRUE)break 算法分析 §10.3.2快速排序 时间复杂度 划分交换排序，1962年由Hoare(1980图灵奖)提出。 ◆最好情况（正序）：比较次数：m-1;移动次数：0： 分治法：将原问题分解为若干个规模较小但结构与原问愿相 ◆最坏情况（逆序）： 似的子问题：递归地求解这些子问题，然后将这些子问题的 (a-i- 解组合为原问厘的解。 比较次数： 2 因此在用递归描述的分治算法的每一层递归上，都有如下三 32a-i-3na- 个步骤： 移动次数： isl 2 ①分解(divide):将原问题分解为若干个子问题，此步称 为划分： 故时间复杂度：T(n)=O(n) ®餐水8o港日性邮各子问圆者子问圆的e0 空间复杂度：Sn)=O(1) @组合(combine):将各子问题的解组合为原问愿的解。 美锌表乐为选日调用凝向。分帐和超合的流易取
13 §10.3 交换排序 两两比较待排序记录的key，发现两个记录的次序相反时即 进行交换，直到无反序的记录为止。 §10.3.1 冒泡排序 设想待排序的记录数组R[1..n]垂直竖立，将每个记录R[i]看 作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下 的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气 泡，就使其向上“飘浮”，如此反复，直到最后任何两气泡都 是轻者在上，重者在下为止。 从下往上和从上往下交替进行，可改善性能。 14 §10.3.1 冒泡排序 从下向上扫描：重气泡下沉一个位置，最轻气泡浮顶，最重气 泡在顶时要n-1趟排序 从上向下扫描：请气泡上浮一个位置，最重气泡沉底，最轻气 泡在底时要n-1趟排序 21 8 90 1 35 90 31 26 35 18 18 90 31 26 35 [ ] [ ] 8 21 1 35 90 [ ] [ ] 冒泡排序过程 初始关键字序列: 23 38 22 45 23 67 31 15 41 第一趟排序后: 23 22 38 23 45 31 15 41 67 第二趟排序后: 22 23 23 38 31 15 41 45 67 第三趟排序后: 22 23 23 31 15 38 41 45 67 第四趟排序后: 22 23 23 15 31 38 41 45 67 第五趟排序后: 22 23 15 23 31 38 41 45 67 第六趟排序后: 22 15 23 23 31 38 41 45 67 第七趟排序后: 15 22 23 23 31 38 41 45 67 void Bubble_Sort(Sqlist *L) { int j ,k , flag ; for (j=0; jlength; j++) /* 共有n-1趟排序 */ { flag=TRUE ; for (k=1; klength-j; k++) /* 一趟排序 */ if (LT(L->R[k+1].key, L->R[k].key ) ) { flag=FALSE ; L->R[0]=L->R[k] ; L->R[k]=L->R[k+1] ; L->R[k+1]=L->R[0] ; } if (flag==TRUE) break ; } } 故时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1) 算法分析 时间复杂度 ◆ 最好情况(正序)：比较次数：n-1；移动次数：0； ◆ 最坏情况(逆序)： 比较次数： ∑(n-i)= n-1 i=1 n(n-1) 2 移动次数： 3∑(n-i)= n-1 i=1 3n(n-1) 2 18 §10.3.2 快速排序 划分交换排序，1962年由Hoare(1980图灵奖)提出。 分治法：将原问题分解为若干个规模较小但结构与原问题相 似的子问题；递归地求解这些子问题，然后将这些子问题的 解组合为原问题的解。 因此在用递归描述的分治算法的每一层递归上，都有如下三 个步骤： ① 分解（divide）：将原问题分解为若干个子问题，此步称 为划分； ② 求解（conquer）：递归地解各子问题，若子问题的size 足够小，则直接求解； ③ 组合（combine）：将各子问题的解组合为原问题的解。 第2步最易，表示为递归调用语句，分解和组合的难易取 决于应用
§10.3.2快速排序（续） §10.3.2快速排序（续） 快速排序的思想：设待排序的无序区为R[low.high void QuickSort(SegList R,int low,int high){ ①裂新弯直前的无序区蓬一记录作为准以生准 对Rlow.high时快速排序 int pivotpos; Rflow..pivotpos-1].keysR[pivotpos].key f(low<high){/当区间长度大于1时须排序 ≤[pivotpos+1.high].k@ys(⑧.1式 pivotpos=Partition(R,low,high);对Rlow.high划分 显然盖准记录已在正确位置上，其余两子区间排序方法与 QuickSort(R,low,pivotpos-1;对左区间递归排序 原问题相同 QuickSort(R,pivotpos+-1,high对右区间递归排序 ①求解：通过递归调用快速排序对左、右子区间排序，当 子区间长度小于等于时无须排。 ②组合：当step②中两个递归调用结束时，其左右子区间 内已有序，敏R[low.high时自然有序，即组合绿作为空 为排序整个文件，只须调用QuickSort(R,1,n)即可完 操作。 成对R[1.n的排序。 §10.3.2快速排序（续） §10.3.2快速排序（续） 如何划分 初始 [4938659776132749 设两个指针i,j,初始时i=low,j=high 取排序区间第1个记录作基准：pivot=R0(即R[low) 令j从后往前扫描，直至找到第1个key小于pivot..key的记 录R门将风]移至所指的位具（相当 于R和R交 向前 [4938659776132749] 换，注意交换前R们pvOt,交换后善准记录相当学在 R[j]中，++) 国令指针从前住后扫描，真到找到第1个关德字大于 pivot.key的记录R叮，将R叮移到j所指位量（相当于交换 第1次交换后+ [2738659776134949 R叮和基准R[j],交换后R可中又相当于存放了pvot, ®热惑亮.处皮早找， 向后 [2738659776134949 22 §10.3.2快速排序（续） §10.3.2快速排序（续） 2nd交换后j [2738499776136549 int Partition(SeqList R,inti,int调用时=low,户high Rectype pivot=-R门：∥区间第1个记录为蓝灌 whie(心s【从区间商端交警肉中间扫捕至判为止 while(i&RIj].kayP=R门.kay)pivot相当于在R可 向前扫描 [2738139776496549] 位置不变交换后+ H业从后往前扫指，找第1个k©y小于善准关铺字的记录R们 计（豪示找到风j】 Ri+=R风[j]:∥相当于交换R可和R,变换后加1，pivot在R风j] 向后扫描 [2738134976976549 while (i<j &R[i].key<=R[].key) 位置不变交换后引 'j +;Ⅲ从前柱后扫描，找第1个k©y大于盖准关抛字的记录R风可 计s)豪示到R风门 j向前，完成 [2738134976976549 R[H门=R0:湘当于交换R门和R0,交换后减1，pwot回到R回 " )所时蜂止 R门=pivot;落准记录已被量后定位 return i;
19 §10.3.2 快速排序（续） 快速排序的思想：设待排序的无序区为R[low..high] ① 分解：在当前的无序区选一记录作为基准，以此基准将 其划分为： R[low..pivotpos-1].keys≤R[pivotpos].key ≤R[pivotpos+1..high].keys (9.1式) 显然基准记录已在正确位置上，其余两子区间排序方法与 原问题相同 ① 求解：通过递归调用快速排序对左、右子区间排序，当 子区间长度小于等于1时无须排。 ② 组合：当step②中两个递归调用结束时，其左右子区间 内已有序，故R[low..high]自然有序，即组合操作为空 操作。 20 §10.3.2 快速排序（续） void QuickSort(SeqList R, int low, int high){ //对R[low..high]快速排序 int pivotpos; if (low= R[i].key) //pivot相当于在R[i] j--; //从后往前扫描，找第1个key小于基准关键字的记录R[ j ] if (i<j) //表示找到R[ j ] R[i++] = R[ j ]; //相当于交换R[i]和R[j]，交换后i加1，pivot在R[ j ] while (i<j && R[i].key<=R[j].key) i++; //从前往后扫描，找第1个key大于基准关键字的记录R[ i] if (i<j) //表示找到R[ i] R[ j--] = R[i]; //相当于交换R[i]和R[j]，交换后j减1，pivot回到R[i] } //i=j时终止 R[i] = pivot; //基准记录已被最后定位 return i; }
§10.3.2快速排序（续） §10.3.2快速排序（续） 时间分析：主要耗费在partition.上。对长度为k的区 ②量好情况：每次划分所取的基准是当前区间中的 间划分，需比较keys共k-1次 “中值记录，划分后左、右子区间大数相等 ④最坏情况：每次划分都是基准恰为当前区间中关 设Cn)表示对长度为n的文件进行快速排序所需比 键字最小（或最大）的记录 较次数 划分结果是左子区间（或右子区间）为空，而另 显然C(n)≤n-1+2C(n/2) 一子区间长度仅比原区间小了1 /设n=2%,n-1是划分R1.n可的比较次数 这时须微-1次划分，第次划分开始时区间长度 C(n)≤n+2C(n/2) 为n-+1,需比较的次数为n-i ≤n+2n/2+2C(n/22)】=2n+4C(n/22)≤. c-2a-n=ma-/2=0时） <kn+2kC(n/2k)=nlgn+nC(1) 显然，当文件状态递增（减）有序时，正是如 =O(nlgn)//k=lgn 此。 §10.3.2快速排序（续） §10.4选择排序 ③平均情况：Tavg(n)≈1.39nlgn+O(n 尽管它的最坏情况0()，但就平均时间而言最快 竞示莞持装笔品秀韩学装 童改进 §10.4.1直接选择排序（简单选择） 为使划分较均匀，避免取当前区间最大最小元做基准 ·基本思想： 三者取中法：然后将它与当前区间第1个元素交换，仍可 第1慧，无序区为R[1.n),选量小者放在R[1],无序区变 使用上述Partition算法 为[2.nJ. ◆景好方法是产生一个j】之间的随机数 第越， 有序区为R[1.i-1],无序区为R.n可 K=random,j:lk∈[] 显然R[1.i-1].keys≤R.n.keys 交换R叮和R[K],然后使用Partition 选无序区中量小者R内，交换R和R的后使R[1.keys ≤R+1n].keys厂有序区长度加1，无序区长度减1 ■不稳定：请检查反例2,2,1] 。第n-1越之后，R[1.n-1.keys≤Rn.keys,结束 ■递归：要使用栈，平均深度0(lgn) §10.4.1直接选择排序（简单选择） §10.4.1直接选择排序（简单选择） ■算法 ■时间 void SelectSort(SeqList R){ ◆比较： int i,j,k; for(i=1;iKn;i++K/第魅排序，1≤i≤n-1 无论文件状态为何，第热排序中需比较n-i次（内循 k=i好 环次数) for (j=i+1;j<=n;j++) (2)ICm=Cmin 在当前无序区Rn中选key最小的记录R冈 ◆移动： if (R[].key<R[k].key)k=j; 状态正序：Mmin=0 f(k=iR可一Rk:∥可用RO做交换单元 0n) 状态逆序：每超交换1次，Mmax=3(n-1) 较少 ◆就地，不稳定，检验反例2,2,1]
25 §10.3.2 快速排序（续） 时间分析：主要耗费在partition上。对长度为k的区 间划分，需比较keys共k-1次 ① 最坏情况：每次划分都是基准恰为当前区间中关 键字最小（或最大）的记录 划分结果是左子区间（或右子区间）为空，而另 一子区间长度仅比原区间小了1 这时须做n-1次划分，第i次划分开始时区间长度 为n-i+1，需比较的次数为n-i 显然，当文件状态递增（减）有序时，正是如 此。 1 2 max 1 ( ) ( 1) / 2 ( ) n i C n i nn On − = = −= − = ∑ 26 §10.3.2 快速排序（续） ② 最好情况：每次划分所取的基准是当前区间中的 “中值”记录，划分后左、右子区间大致相等。 设C(n)表示对长度为n的文件进行快速排序所需比 较次数 显然C(n) ≤n-1+2C(n/2) //设n=2k，n-1是划分R[1..n]的比较次数 C(n) ≤n+2C(n/2) ≤n+2[n/2+2C(n/22)] = 2n+4C(n/22) ≤… ≤kn+2kC(n/2k) = nlgn+nC(1) = O(nlgn) //k=lgn 27 §10.3.2 快速排序（续） ③ 平均情况：Tavg(n) ≈1.39nlgn+O(n) 尽管它的最坏情况O(n2)，但就平均时间而言最快 改进 为使划分较均匀，避免取当前区间最大最小元做基准 三者取中法：然后将它与当前区间第1个元素交换，仍可 使用上述Partition算法 最好方法是产生一个R[i..j]之间的随机数 K=random(i,j); //k∈ [i,j] 交换R[i]和R[k]，然后使用Partition 不稳定：请检查反例[2, 2, 1] 递归： 要使用栈，平均深度O(lgn) 28 §10.4 选择排序 基本思想：每一趟从待排序的记录中选出最小key的 记录（简称最小元），放在已排好序的子区间最后 §10.4.1 直接选择排序（简单选择） 基本思想： 第1趟，无序区为R[1..n]，选最小者放在R[1]，无序区变 为[2..n]. 第i趟，有序区为R[1..i-1]，无序区为R[i..n] 显然R[1..i-1].keys≤R[i..n].keys 选无序区中最小者R[k]，交换R[i]和R[k]后使R[1..i].keys ≤R[i+1..n].keys //有序区长度加1，无序区长度减1 第n-1趟之后，R[1..n-1].keys ≤R[n].keys，结束 29 § 10.4.1 直接选择排序（简单选择） 算法 void SelectSort(SeqList R){ int i, j, k; for (i=1; i<n; i++){ //第i趟排序，1≤i ≤n-1 k = i; for (j=i+1; j<=n; j++) //在当前无序区R[i..n]中选key最小的记录R[k] if (R[j].key<R[k].key) k=j; if (k!=i) R[i]↔R[k]; //可用R[0]做交换单元 } } 30 § 10.4.1 直接选择排序（简单选择） 时间 比较： 无论文件状态为何，第i趟排序中需比较n-i次（内循 环次数） //Cmax=Cmin 移动： 状态正序：Mmin=0 状态逆序：每趟交换1次，Mmax=3(n-1) 就地，不稳定，检验反例[2, 2, 1] 1 2 1 ( ) ( 1) / 2 ( ) n i n i nn On − = ∑ −= − = }O(n), 较少