1、v概述概述v插入排序插入排序v快速排序快速排序v选择排序选择排序v归并排序归并排序8.1 概概 述述 n排序：排序：将一个数据元素的任意序列，重新排列成一将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。个按关键字有序的序列。n数据表数据表(datalist):它是待排序数据对象的有限集合。它是待排序数据对象的有限集合。n主关键字主关键字(key):数据对象有多个属性域数据对象有多个属性域,即多个数即多个数据成员组成据成员组成,其中有一个属性域可用来区分对象其中有一个属性域可用来区分对象,作作为排序依据，称为关键字。也称为为排序依据，称为关键字。也称为排序码排序码。n排序方法的稳定性
2、排序方法的稳定性:如果在对象序列中有两如果在对象序列中有两 个对象个对象Ri和和Rj,它们的排序码它们的排序码 Ki=Kj,且在排序之前且在排序之前,对象对象Ri排在排在Rj前面。如果在排序之后前面。如果在排序之后,对象对象Ri仍在对象仍在对象Rj的前面的前面,则称这个排序方法是则称这个排序方法是稳定稳定的的,否则称这个否则称这个排序方法是排序方法是不稳定不稳定的。的。n内排序与外排序内排序与外排序:内排序内排序是指在排序期间数据对象是指在排序期间数据对象全部存放在内存的排序；全部存放在内存的排序；外排序外排序是指在排序期间全是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据部对象个
3、数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序过程的要求，不断在内、外存之间移动的排序。n排序的时间开销排序的时间开销:排序的时间开销是排序的时间开销是衡量算法好坏的最重要的标志。排序的衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的时间开销可用算法执行中的数据比较次数据比较次数数与与数据移动次数数据移动次数来衡量。来衡量。内排序分类内排序分类n依不同原则依不同原则插入排序插入排序、交换排序交换排序、选择排序选择排序、归并归并排序排序、和计数排序等和计数排序等。n依所需工作量依所需工作量简单排序简单排序-时间复杂度时间复杂度O(n2)先进排序方
4、法先进排序方法-时间复杂度时间复杂度O(n logn)基数排序基数排序-时间复杂度时间复杂度O(d.n)8.2 插入排序插入排序(Insert Sorting)v基本思想基本思想 每步将一个待排序的对象每步将一个待排序的对象,按其排按其排序码大小序码大小,插入到前面已经排好序的一组对插入到前面已经排好序的一组对象的适当位置上象的适当位置上,直到对象全部插入为止。直到对象全部插入为止。n基本思想基本思想 当插入第当插入第i(i 1)个对象时个对象时,前面的前面的V0,V1,Vi-1已经排好序。这时已经排好序。这时,用用Vi的排序的排序码与码与Vi-1,Vi-2,的排序码顺序进行比较的排序码顺序进
5、行比较,找找到插入位置即将到插入位置即将Vi插入插入,原来位置上的对象向后原来位置上的对象向后顺移。顺移。v直接插入排序直接插入排序 (Straight Insert Sort)void InsertSort(SqList&L)/按非递减顺序对表进行排序 for(i=2;i L.length;+i)if LT(L.ri.key,L.ri-1.key)/”=2&change;-i)change=FALSE;/假定未交换 for(j=1;j aj+1)/逆序 aj aj+1;/交换 change=TRUE;/有交换 n第第i趟对待排序记录序列趟对待排序记录序列a1,a2,an-i+-i+1进行排进
6、行排序序,结果将该序列中关键字最大的记录交换到序列的结果将该序列中关键字最大的记录交换到序列的第第n-i+1个位置个位置,其它记录也都向排序的最终位置移动。其它记录也都向排序的最终位置移动。n最多做最多做n-1趟起泡就能把所有记录排好序。趟起泡就能把所有记录排好序。n在记录的初始排列已为正序时在记录的初始排列已为正序时,算法只执行一趟起算法只执行一趟起泡泡,做做n-1次关键字比较次关键字比较,不移动记录。这是不移动记录。这是最好的最好的情形情形。n最坏的情形最坏的情形是初始序列为逆序，算法执行是初始序列为逆序，算法执行n-1趟起趟起泡泡,第第i趟做趟做 n-i 次关键字比较次关键字比较,执行执
7、行 n-i 次记录交次记录交换。总的关键字比较次数换。总的关键字比较次数KCN和记录移动次数和记录移动次数RMN为：为：11111233121nininninRMNnninKCN)()()()(最坏时间复杂度为最坏时间复杂度为O(n2)n起泡排序是一个起泡排序是一个稳定稳定的排序方法的排序方法。n基本思想：基本思想：任取待排序记录序列中的某个记录任取待排序记录序列中的某个记录(例例如取第一个记录如取第一个记录)作为基准作为基准,按照该记录的关键字按照该记录的关键字大小大小,将整个记录序列划分为左右两个子序列：将整个记录序列划分为左右两个子序列：u左侧子序列中所有记录的排序码都小于或等于左侧子序
8、列中所有记录的排序码都小于或等于基准记录的排序码基准记录的排序码 u右侧子序列中所有记录的排序码都大于基准记右侧子序列中所有记录的排序码都大于基准记录的排序码录的排序码u基准记录则排在这两个子序列中间基准记录则排在这两个子序列中间(这也是该记这也是该记录最终应安放的位置录最终应安放的位置)。n分别对这两个子序列重复施行上述方法，分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。直到所有的记录都排在相应位置上为止。n基准记录也称为基准记录也称为枢轴（或支点）枢轴（或支点）(pivot)记记录。录。QuickSort(List)if(List的长度大于1)将序列List划分为
9、两个子序列 LeftList 和 Right List;QuickSort(LeftList);QuickSort(RightList);将两个子序列 LeftList 和 RightList 合并为一个序列List;快速排序的过程快速排序的过程初始关键字初始关键字pivotkey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序ijijjiijji ji完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序有序序列有序序列void QuickSort(SqList&L,int low,int high)/在序列lowhigh 中递归地进行快速排序 if
10、(low high)pivotloc=Partition(L,low,high);/划分 QuickSort(L,low,pivotloc-1);/对左序列同样处理 QuickSort(L,pivotloc+1,high);/对右序列同样处理 算法算法 10.7int Partition(SqList&L,int low,int high)L.r0=L.rlow;/子表的第一个记录作枢轴记录 pivotkey=L.rlow.key;/枢轴记录关键字 While(lowhigh)While(low=pivotkey)-high;L.rlow=L.rhigh;/小于枢轴记录的移到区间的左侧 Whi
11、le(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/大于枢轴记录的移到区间的右侧 L.rlow=L.r0;/枢轴记录到位 return low;算法 10.6(b)n算法算法Partition利用序列第一个对象作为基准，将整个序利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环列划分为左右两个子序列。算法中执行了一个循环,只要只要是排序码小于基准对象排序码的对象都移到序列左侧是排序码小于基准对象排序码的对象都移到序列左侧,最最后基准对象安放到位后基准对象安放到位,函数返回其位置。函数返回其位置。算法算法Quick
12、sort是一个递归的算法是一个递归的算法,其其递归树递归树如图所示。如图所示。算法分析算法分析n快速排序的趟数取决于递归树的高度。快速排序的趟数取决于递归树的高度。n如果每次划分对一个记录定位后如果每次划分对一个记录定位后,该记录的左侧子序列与右该记录的左侧子序列与右侧子序列的长度相同侧子序列的长度相同,则下则下 一步将是对两个长度减半的子序一步将是对两个长度减半的子序列进行排序列进行排序,这是最理想的情况。这是最理想的情况。n在在 n个元素的序列中个元素的序列中,对一个记录定位所需时间为对一个记录定位所需时间为 O(n)。若设若设 t(n)是对是对 n 个元素的序列进行排序所需的时间个元素的
13、序列进行排序所需的时间,而且而且每次对一个记录正确定位后每次对一个记录正确定位后,正好把序列划分为长度相等的正好把序列划分为长度相等的两个子序列两个子序列,此时此时,总的计算时间总的计算时间为：为：T(n)cn+2T(n/2)/c 是一个常数是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(n log2n)n可以证明可以证明,函数函数quicksort的平均计算时间也是的平均计算时间也是O(nlog2n)。实验结果表明实验结果表明:就平均计算时间而言就平均计算时间而言,快速排序是所
14、有内排快速排序是所有内排序方法中最好的一个序方法中最好的一个。n快速排序是递归的，需要有一个栈存放每层递归调用时的快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。指针和参数。n最大递归调用层次数与递归树的高度一致最大递归调用层次数与递归树的高度一致,理想情况为理想情况为 log2(n+1)。因此，要求存储开销为。因此，要求存储开销为 O(log2n)。n在最坏的情况在最坏的情况,即待排记录序列关键字有序（正序或逆序）即待排记录序列关键字有序（正序或逆序）时时,其递归树成为单支树其递归树成为单支树,每次划分只得到一个比上一次每次划分只得到一个比上一次少一个对象的子序列。总的关键字比
15、较次数将达少一个对象的子序列。总的关键字比较次数将达2121211nnninni)()(此时得到算法的最坏时间复杂度为此时得到算法的最坏时间复杂度为O(n2)n改进枢轴记录的选取：改进枢轴记录的选取：“三者取中三者取中”n快速排序是一种快速排序是一种不稳定不稳定的排序方法。的排序方法。基本思想：基本思想：每一趟在每一趟在 n-i+1(i=1,n-1)个记录中选出关键字最小的记录个记录中选出关键字最小的记录,作为有序序作为有序序列中的第列中的第 i 个记录。个记录。选准了再做记录移动简单选择排序是一种简单的排序方法简单选择排序是一种简单的排序方法,它的基本步它的基本步骤是：骤是：在一组对象在一组
16、对象 rirn-1 中选择具有最小关键字的记录；中选择具有最小关键字的记录；若它不是这组对象中的第一个对象若它不是这组对象中的第一个对象,则将它与这组对象中则将它与这组对象中的第一个对象对调的第一个对象对调;在这组对象中剔除这个具有最小排序码的对象。在剩下在这组对象中剔除这个具有最小排序码的对象。在剩下的对象的对象Vi+1Vn-1中重复执行第中重复执行第、步步,直到剩余直到剩余对象只有一个为止。对象只有一个为止。1 2 3 4 5 6最小者最小者最小者最小者最小者最小者 简单选择排序的过程简单选择排序的过程最小者最小者1 2 3 4 5 6结果结果最小者最小者各趟排序后的结果各趟排序后的结果直
17、接选择排序的算法直接选择排序的算法void SelectSort(SqList&L)for(i=1;i L.length;+i)/共n-1趟 k=i;/选择具有最小关键字的记录 for(int j=i+1;j n;j+)if(L.rj L.rk)k=j;/当前具最小关键字的记录 if(k!=i)/对换到第 i 个位置 L.ri L.rk);算法 10.9关键字比较次数关键字比较次数 KCN 与记录的初始排列无关。与记录的初始排列无关。设有 n 个记录,则第 i 趟选择具有最小关键字记录所需的比较次数总是 n-i 次。总的关键字比较次数为1121ninninKCN)()(n记录的移动次数记录的移
18、动次数RMN与记录序列的初始排列有关。与记录序列的初始排列有关。当初始序列为正序时，RMN取最小值“0”；最坏情况是每一趟都要进行交换，RMN取最大值为 3(n-1)。n总的时间复杂度为总的时间复杂度为O(n2)n简单选择排序是一种简单选择排序是一种不稳定不稳定的排序方法。的排序方法。v堆堆(Heap)的定义：的定义：设有一个关键字集合，按完全二叉树的顺序存储方式存设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从一层自左向右从 1开始连续编号。若满足开始连续编号。若满足 Ki K2i&
19、Ki K2i+1 或或 Ki K2i&Ki K2i+1,则称该关键字集合构成一个则称该关键字集合构成一个堆堆。前者称为前者称为小根（顶）堆小根（顶）堆，后者称为，后者称为大根（顶）堆大根（顶）堆。完全二叉树完全二叉树 顺序表示顺序表示Ki K2i&Ki K2i+1完全二叉树完全二叉树 顺序表示顺序表示Ki K2i&Ki K2i+1090987877878454565653131532323531717v堆排序的步骤堆排序的步骤（以小根堆为例）（以小根堆为例）1.根据初始的输入数据，形成初始堆；根据初始的输入数据，形成初始堆；2.输出堆顶元素（最小记录）；输出堆顶元素（最小记录）；3.对剩余元素
20、做调整，形成新的堆；对剩余元素做调整，形成新的堆；4.重复步骤重复步骤2,3，直到剩余元素个数为零。，直到剩余元素个数为零。123456136542堆排序过程堆排序过程(大根堆）大根堆）123456136542123456136542123456136542123456136542v两个关键问题两个关键问题：1.如何由一个无序序列建成一个堆如何由一个无序序列建成一个堆?2.如何在输出堆顶元素后，调整剩余元素成为一个如何在输出堆顶元素后，调整剩余元素成为一个新的堆？新的堆？方法方法：自顶向下地：自顶向下地“筛选筛选”38657649972713499765763849271349rc=38sjs
21、jsvoid HeapAdjust(HeapType&H,int s,int m)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，本函 /数调整H.rs的关键字，使H.rs.m成为一个大根堆(对其中记录的关键/字而言 rc=H.rs;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选 if(j0;-i)/把H.r1.H.length建成大根堆 HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)H.r1H.ri;/将堆顶记录和当前未经排序子序列H.r1.i中 /最后一个记录相互交换 HeapAdjust(H,1,
22、i-1);/将H.r1.I-1重新调整为大根堆 算法 10.11堆的建立算法堆的建立算法n堆排序的最坏时间复杂度为堆排序的最坏时间复杂度为O(nlog2n)，优，优于快速排序的最坏时间复杂度于快速排序的最坏时间复杂度O(n2)。n算法的空间复杂度为算法的空间复杂度为O(1)。n堆排序是一个堆排序是一个不稳定不稳定的排序方法。的排序方法。（为什么？）（为什么？）n归并归并 将两个或两个以上的有序表合并成一个新的有序表。将两个或两个以上的有序表合并成一个新的有序表。n2-路归并路归并(2-way merging)原始序列原始序列initList 中两个有序表中两个有序表 initListl ini
23、tListm和和initListm+1 initListn，它们，它们可归并成一个有序表可归并成一个有序表,存于另一记录序列存于另一记录序列mergedList的的 l n 中中。n设变量设变量 i 和和 j 是表是表initListl m和和initList m+1 n的当前检测指针。的当前检测指针。k 是存放指针。是存放指针。u当当 i 和和 j 都在两个表的表长内变化时都在两个表的表长内变化时,根据对应项的根据对应项的关键字的大小关键字的大小,依次把关键字小的记录排放到新表依次把关键字小的记录排放到新表 k 所指位置所指位置中；中；u当当 i 与与 j 中有一个已经超出表长时，将另一中有
24、一个已经超出表长时，将另一 个表中个表中的剩余部分照抄到新表中。的剩余部分照抄到新表中。2路归并排序算法路归并排序算法 算法思想算法思想 假设初始对象序列有假设初始对象序列有 n 个对象，首先把它看个对象，首先把它看成是成是 n 个长度为个长度为 1 的有序子序列的有序子序列(归并项归并项)，先做两两归并，得到先做两两归并，得到 n/2 个长度为个长度为 2 的的归并项归并项(如果如果 n 为奇数，则最后一个有序子为奇数，则最后一个有序子序列的长度为序列的长度为1)；再做两两归并，；再做两两归并，如此，如此重复，最后得到一个长度为重复，最后得到一个长度为 n 的有序序列的有序序列。2-路归并算
25、法路归并算法void Merge(RcdType SR,RcdType&TR,int i,int m,int n)/将有序的SRI.m和SRm+1.n归并为有序的TRi.n for(j=m+1,k=i;i=m&j=n;+k)/平移指针，一次扫描 if LQ(SRi.key,Srj.key)TRk=SRi+;else TRk=SRj+;if(j=m)TRk.n=SRi.m;/将剩余的SRi.m复制到TR if(j=n)TRk.n=SRj.n;/将剩余的SRj.n复制到TR 算法 10.12void Msort(RcdType SR,RcdType&TR1,int s,int t)/将SRs.t归
26、并排序为TRs.t if(s=t)TR1s=SRs;else m=(s+t)/2;/将SRs.t平分为SRs.m和 SRm+1.t Msort(SR,TR2,s,m);/递归地将SRs.m归并为有序的TR2s.m Msort(SR,TR2,m+1,t);/递归地将SRm+1.t归并为有序的TR2m+1.t Merge(TR2,TR1,s,m,t);/将TR2s.m和TR2m+1.t归并到TR1m.t 算法 10.13Void MergeSort(SqList&L)/对顺序表对顺序表L L作归并排序作归并排序 Msort(L.r,L.r,1,L.length);算法10.14特点：形式简洁，效率
27、很低一趟归并排序的情形一趟归并排序的情形n设设initList0到到initListn-1中中 n 个对象已经分个对象已经分为一些长度为为一些长度为 h 的归并项的归并项,将这些归并项两两归并将这些归并项两两归并,归并成长度为归并成长度为 2h 的归并项的归并项,结果放到结果放到mergedList 中。中。n如果如果n不是不是2h的整数倍的整数倍,则一趟归并到最后则一趟归并到最后,可能遇可能遇到两种情形：到两种情形：u 剩下一个长度为剩下一个长度为h的的归并项和另一个长度不足归并项和另一个长度不足len的归并项的归并项,可用可用merge算法将它们归并成一算法将它们归并成一个长度小于个长度小
28、于 2h的归并项。的归并项。u只剩下一个归并项，其长度小于或等于只剩下一个归并项，其长度小于或等于h,将它将它直接抄到直接抄到mergedList 中。中。v时间复杂度为时间复杂度为O(nlog2n)：做一趟两路归并排序,要调用n/(2*h)O(n/h)次merge；整个归并过程需进行log2n 趟,所以算法总的时间复杂度为O(nlog2n)。n空间复杂度为空间复杂度为O(n)归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。n归并排序是一个归并排序是一个稳定稳定的排序方法。的排序方法。各种排序方法的比较各种排序方法的比较 比比较较次次数数 移移动
29、动次次数数附附加加存存储储排排 序序 方方 法法最最好好最最差差最最好好最最差差稳稳定定 性性最最好好最最差差直直接接插插入入排排序序nn2 0n2 1折折半半插插入入排排序序n log2n 0n2 1起起泡泡排排序序nn2 0n2 1快快速速排排序序nlog2nn2n log2nn2 log2nn2简简单单选选择择排排序序n2 0n 1锦锦标标赛赛排排序序n log2nn log2n n堆堆排排序序n log2nn log2n 1归归并并排排序序n log2nn log2n nn作业：习题集 9.21(page 57)hash查找 习题集 10.34(page 65)-堆排序n课后阅读：DSDEMO课件中的相关排序算法
