数据结构-C语言版：DS09-排序

1、第 章 排 序 第第9 9章章 排序排序第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 08 08 08085 5 08 16 21 25 2508 16 21 25 25* *4949 第 章 排 序 void lnsertSort(SeqList R) int i,j; for (i=2;in;i+) R0Ri; /* R0为工作单元为工作单元 */ ji-1; while (R0.keyRj.key) Rj+1Rj- -; /* 后移后移 */ Rj+1R0; /* 插入插入Ri */ 第 章

2、 排 序 第 章 排 序 nininOnninOnni2222)(2/ )4)(1()21()(2/ ) 1)(2(移动次数的最大值比较次数的最大值第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 2525 16 - 16 - 2525* * - 49 - 49 2 2 08 16 21 25 08 16 21 25* *25 4925 493 08 16 21 253 08 16 21 25* *25 49 25 49 1 1 08 16 21 25 08 16 21 25* *25 4925 49第 章 排 序 void ShellPass(SeqList R，int d)

3、/*希尔排序中的一趟排序，希尔排序中的一趟排序，d为当前增量为当前增量*/ for(i=d+1；i=n；i+) if(Ri.key0&R0.key0*/ do increment=increment/3+1； / /* *求下一增量，注意增量的取法并不唯一求下一增量，注意增量的取法并不唯一* */ / ShellPass(R，increment)； while(increment1)；第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 25 2525 25* * 49 49第 章 排 序 void BubbleSort (SeqList R)

4、 /*R是待排序文件，用自后向前扫描，对是待排序文件，用自后向前扫描，对R做冒泡排序做冒泡排序*/ int i，j，exchange；/ /* *exchangexchang为交换标志为交换标志* */ / for(i=1;i=i；j-) / /* *对当前无序的对当前无序的Ri.nRi.n自下向上扫描自下向上扫描* */ / if(Rj+1.keyRj.key) / /* *交换记录交换记录* */ / R0=Rj+1； Rj+1=Rj； Rj=R0； exchange=1；/ /* *发生了交换，故将交换标志置为真发生了交换，故将交换标志置为真* */ / if(!exchange) /

5、/* *本趟排序未发生交换，提前终止算法本趟排序未发生交换，提前终止算法* */ / return；数组数组R R的的0 0元素只是用来元素只是用来做为元素交换时的桥梁做为元素交换时的桥梁你也可以从前向后冒泡第 章 排 序 112112)(2/ ) 1(3)(3)(2/ ) 1()(nininOnninnOnnin移动次数的最大值比较次数的最大值第 章 排 序 分割分割成独立的两部分成独立的两部分前一部分记录的键值均前一部分记录的键值均轴轴值值后一部分记录的键值均后一部分记录的键值均大于或等于大于或等于轴值轴值第 章 排 序 jijjiiijijjj3838枢轴枢轴如何实现一次划分示意图如何实

6、现一次划分示意图第 章 排 序 4949383865659797767613132727 4949 383865659797767613132727 4949272738386565979776761313 494927273838 9797767613136565 494927273838131397977676 6565 4949272738381313 767697976565 4949272738381313 49 49 7676 97 97 6565 49494949temptemp原文件原文件枢轴枢轴实现一次划实现一次划分示意图分示意图第 章 排 序 void QuickSort(

7、SeqList R，int low，int high) /*对对Rlow.high快速排序快速排序*/ int pivotpos；/*划分后的基准记录的位置划分后的基准记录的位置*/ if(lowhigh) /*仅当区间长度大于仅当区间长度大于1时才需排序时才需排序*/ pivotpos=Partition(R，low，high)；/*对对Rlow.high做划分做划分*/ QuickSort(R，low，pivotpos-1)； /*对左区间递归排序对左区间递归排序*/ QuickSort(R，pivotpos+1，high)； /*对右区间递归排序对右区间递归排序*/ 第 章 排 序 in

8、t Partition(SeqList R，int i，int j)/*对对Ri.j做划分，并返回基准记录的位置做划分，并返回基准记录的位置*/ ReceType pivot=Ri；/ /* *用区间的第用区间的第1 1个记录作为基准个记录作为基准* */ / while(ij) / /* *从区间两端交替向中间扫描，直至从区间两端交替向中间扫描，直至i=ji=j为止为止* */ / while(i=pivot.key) / /* *pivotpivot相当于在位置相当于在位置i i上上* */ / j- -；/ /* *从右向左扫描，查找第从右向左扫描，查找第1 1个关键字小于个关键字小于p

9、ivot.keypivot.key的记录的记录RjRj* */ / if(ij) / /* *表示找到的表示找到的RjRj的关键字的关键字pivot.keypivot.key* */ / Ri+=Rj；/ /* *相当于交换相当于交换RiRi和和RjRj，交换后，交换后i i指针加指针加1 1* */ / while(ij&Ri.key=pivot.key) / /* *pivotpivot相当于在位置相当于在位置j j上上* */ / i+；/ /* *从左向右扫描，查找第从左向右扫描，查找第1 1个关键字大于个关键字大于pivot.keypivot.key的记录的记录RiRi* *

10、/ / if(ipivot.keyRi.keypivot.key* */ / Rj- -=Ri; / /* *相当于交换相当于交换RiRi和和RjRj，交换后，交换后j j指针减指针减1 1* */ / Ri=pivot；/ /* *基准记录已被最后定位基准记录已被最后定位* */ / return i； 第 章 排 序 112)(2/ ) 1()(ninOnnin比较次数的最大值第 章 排 序 快速排序的记录移动次数不会大快速排序的记录移动次数不会大于比较次数，所以，快速排序的于比较次数，所以，快速排序的最坏时间最坏时间复杂度为复杂度为O(nO(n2 2) )；最好时间复杂度为最好时间复杂度

11、为O(nlogO(nlog2 2n)n)。 快速排序的平均时间复杂度也是快速排序的平均时间复杂度也是(nlog(nlog2 2n)n)，空间复杂度为，空间复杂度为O(logO(log2 2n)n)。 快速排序是不稳定的排序方法。快速排序是不稳定的排序方法。 第 章 排 序 第 章 排 序 第 章 排 序 4949383865659797767613132727 49491313383865659797767649492727 49491313272765659797767649493838 49491313272738389797767649496565 4949131327273838494

12、9767697976565 49491313272738384949 4949 9797656576761313272738384949 4949 6565979776761313272738384949 4949 656576769797第 章 排 序 void SelectSort(SeqList R) int i，j，k； for(i=1;in;i+) k=i； for(j=i+1;j=n;j+) if(Rj.keyRk.key) k=j; /*k记下目前找到的最小键值的记录所在的位置记下目前找到的最小键值的记录所在的位置*/ if(k!=i) /*交换交换Ri和和Rk*/ R0=Ri；

13、Ri=Rk；Rk=R0；/*R0作暂存单元作暂存单元*/ 第 章 排 序 112)(2/ ) 1()(ninOnnin第 章 排 序 第 章 排 序 第 章 排 序 122iiiiKKKK和)2/(1 (nlowi 第 章 排 序 1010151556562525303070701010 1515 5656 2525 3030 7070第 章 排 序 7070565630302525151510107070 5656 3030 2525 1515 1010第 章 排 序 )2/(1 (nlowi 第 章 排 序 第 章 排 序 第 章 排 序 4242131391912323242416160

14、505888842421313919123232424161605058888第 章 排 序 4242131391918888242416160505232342421313919188882424161605052323第 章 排 序 4242131391918888242416160505232342421313919188882424161605052323第 章 排 序 4242888891912323242416160505131342428888919123232424161605051313第 章 排 序 9191888842422323242416160505131391918

15、888424223232424161605051313第 章 排 序 void Heapify(SeqList R,int k,int m)/ /* *调整调整R Rk,使整个序列使整个序列R Rk.m满足大根堆的性质满足大根堆的性质* */ / t=rk； / /* *暂存暂存“根根”记录记录RkRk* */ / x=rk.key； / /* *当前当前“根根”的键值送入的键值送入x x中中* */ / i=k；j=2*i； / /* *j j结点是结点是i i的左孩子的左孩子* */ / while(j=m) / /* *RjRj是是RiRi的左孩子，的左孩子，i i结点的左孩子结点的左孩

16、子j j存在存在* */ / if(jm & Rj.key Rj+1.key )j+; / /* *若存在右子树，且右子树根的关键字大，则沿右分支若存在右子树，且右子树根的关键字大，则沿右分支“筛选筛选”* */ / if(x=1; i-) Heapify (R, i, n) 第 章 排 序 。第 章 排 序 9191888842422323242416160505131391918888424223232424161605051313（a a）初始堆）初始堆R1R1到到R8R8第 章 排 序 1313888842422323242416160505919113138888424223

17、232424161605059191（b b）第一趟排序之后）第一趟排序之后第 章 排 序 （c c）重建的堆）重建的堆R1R1到到R7R78888242442422323131316160505919188882424424223231313161605059191第 章 排 序 0505242442422323131316168888919105052424424223231313161688889191（d d）第二趟排序之后）第二趟排序之后第 章 排 序 （e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914242242416

18、1623231313050588889191第 章 排 序 （f f）第三趟排序之后）第三趟排序之后0505242416162323131342428888919105052424161623231313424288889191第 章 排 序 （g g）重建的堆）重建的堆R1R1到到R5R52424232316160505131342428888919124242323161605051313424288889191第 章 排 序 （h h）第四趟排序之后）第四趟排序之后13132323161605052424424288889191131323231616050524244242888891

19、91第 章 排 序 （i i）重建的堆）重建的堆R1R1到到R4R42323131316160505242442428888919123231313161605052424424288889191第 章 排 序 （j j）第五趟排序之后）第五趟排序之后0505131316162323242442428888919105051313161623232424424288889191第 章 排 序 （k k）重建的堆重建的堆R1R1到到R3R31616131305052323242442428888919116161313050523232424424288889191第 章 排 序 （l l）第六

20、趟排序之后）第六趟排序之后0505131316162323242442428888919105051313161623232424424288889191第 章 排 序 （m m）重建的堆）重建的堆R1R1到到R2R21313050516162323242442428888919113130505161623232424424288889191第 章 排 序 （n n）第七趟排序之后）第七趟排序之后0505131316162323242442428888919105051313161623232424424288889191第 章 排 序 void HeapSort(SeqList R)/ /

21、* *对对R1.nR1.n进行堆排序，不妨用进行堆排序，不妨用R0R0做暂存单元做暂存单元* */ / int i； BuildHeap(R)；/ /* *将将R1.nR1.n建成初始堆建成初始堆* */ / for(i=n；i1；i-) R0=R1；R1=Ri；Ri=R0; Heapify(R，1，i-1)； 第 章 排 序 第 章 排 序 堆排序堆排序适合于待排序的记录个适合于待排序的记录个数较多的情况数较多的情况,因其运行时间主因其运行时间主要耗在建初始堆和调整新堆时要耗在建初始堆和调整新堆时进行的反复筛选上，进行的反复筛选上，对深度为对深度为K的堆的堆,筛选法中进行的关键字筛选法中进行

22、的关键字比较次数至多为比较次数至多为2(K-1)次次第 章 排 序 因为因为在每个结点中的两个孩子在每个结点中的两个孩子选一个较小的时要比较一次选一个较小的时要比较一次, 选选出比较小的孩子与其父结点比出比较小的孩子与其父结点比较一次较一次。在建含在建含n个结点深度为个结点深度为h的堆时的堆时,总共需要的关键字比较次数不总共需要的关键字比较次数不超过超过4n第 章 排 序 这因为：这因为：由于第由于第i层上的结点数至多为层上的结点数至多为2i-1,以以它们为根的二叉树的深度为它们为根的二叉树的深度为h-(i-1),建堆时在建堆时在第第i层的每个结点及其子树建成堆时层的每个结点及其子树建成堆时,

23、需需2 (h-(i-1)-1)=2(h-i)次比较，故第次比较，故第i层中的层中的2i-1棵子棵子树共需树共需2i-12(h-i)次比较，便可得到次比较，便可得到2i-1堆。所堆。所以在建堆时，对深度为以在建堆时，对深度为h的完全二叉树，先的完全二叉树，先从从h-1层开始直到第一层，共最多需层开始直到第一层，共最多需 2i-12(h-i)=2i (h-i)= 2h-jj2nj /2 j4n1 1i=h-1i=h-11 1i=h-1i=h-1h-1h-1j=1j=1j=1j=1h-1h-1第 章 排 序 (因为：因为：2i(h-i) =2h-1(h-(h-1)+ 2h-2 (h-(h-2)+21

24、(h-1) =2h-1 (1)+ 2h-2 (2)+21(h-1) =2h-jj而而2h-1是第是第h层的结点个数（最多），当然要小于层的结点个数（最多），当然要小于树中的总结点个数树中的总结点个数n,又又2h-j=2h2-j=2h/2j,而而h是树的是树的深度，所以深度，所以2h2n（n是树中结点个数）。是树中结点个数）。 所以：所以：2h-jj=2h/2jj2nj/2j4n)i=h-1i=h-11 1j=1j=1h-1h-1h-1h-1h-1h-1j=1j=1j=1j=1j=1j=1h-1h-1第 章 排 序 又因为又因为n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n

25、+1，则调建新堆时调用，则调建新堆时调用Heapify( ) 函数函数n-1次总共需要的比较次数不超过下次总共需要的比较次数不超过下式之值。式之值。2( log2(n-1) + log2(n-2) + log2(n-3) + log2(2) ) 2n( log2n )第 章 排 序 这是因为这是因为对对n个结点的完全二叉树在建堆个结点的完全二叉树在建堆时要调用时要调用Heapify( )函数函数n-1次，每次调用次，每次调用 Heapify( )，最多要做最多要做2.log2n次比较，次比较，因此，因此，堆排序在最坏的情况下，其时间复堆排序在最坏的情况下，其时间复杂度也为杂度也为O（nlog2

26、n）。 相对于快速排序来说，这是堆排序的相对于快速排序来说，这是堆排序的最大优点，此外，堆排序仅需一个记录大最大优点，此外，堆排序仅需一个记录大小供交换用的辅助存储空间，所以它的空小供交换用的辅助存储空间，所以它的空间复杂度为间复杂度为O（1）第 章 排 序 第 章 排 序 l l第 章 排 序 21343644567880582331353766012345678910111213第第1 1个归并段个归并段 第第2 2个归并段个归并段归并段归并段1 1、2 2已不减有序，归并后的新表已不减有序，归并后的新表C C也是不减有序也是不减有序。通过工作指针通过工作指针i,j,pi,j,p协调工作来

27、完成归并过程协调工作来完成归并过程C C5821 23 31ijp34第 章 排 序 2525 5757 4848 37 37 9292 1212 8686 25 57 37 48 12 25 57 37 48 12 92 8692 86 25 37 48 57 12 25 37 48 57 12 86 92 86 92 12 25 37 48 57 12 25 37 48 57 86 9286 92第 章 排 序 void Merge(SeqList R，int low，int m，int high)/只是将相邻的两个子文件只是将相邻的两个子文件Rlow.m和和Rm+1.high归并为一个子

28、文件归并为一个子文件Rlow. high int i=low，j=m+1，p=0； RecType *R1； R1=(RecType*)malloc(high-low+1)*sizeof(RecType)； /申请一个辅助存储空间申请一个辅助存储空间R1,用于存放归并后的文件内容用于存放归并后的文件内容 if(! R1) /如果申请不成功如果申请不成功,则退出则退出 error(Insufficient memory available!)； 第 章 排 序 while(i=m&j=high) R1p+=(Ri.key=Rj.key)?Ri+:Rj+)； while(i=m) R1p+

29、=Ri+； while(j=high) R1p+=Rj+； for(p=0，i=low；i=high；p+，i+) Ri=R1p；第 章 排 序 第 章 排 序 void MergePass(SeqList R，int length) int i； for(i=1;i+2*length-1=n;i=i+2*length) Merge(R，i，i+length-1，i+2*length-1)； if(i+length-1n) 说明尚有两个子文件未合并，且后一个子文件的长度小于说明尚有两个子文件未合并，且后一个子文件的长度小于length Merge(R，i，i+length-1，n)； i i+

30、length-1 i+2*length-1第 章 排 序 void MergeSort(SeqList R) int length； for(1ength=1；lengthn；length*=2) MergePass(R，length)；length*=2第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 第 章 排 序 假定记录假定记录R R1 1、R R2 2、R Rn n的关键字由的关键字由d d元元组组（k k0 0k k11k kd-1d-1）组成，即每个关键字组成，即每个关键字k k0k9990k999第 章 排 序 现研

31、究以现研究以1010为基数的分类方法为基数的分类方法 假定记录假定记录R R1 1、R R2 2、R Rn n的关键字由的关键字由d d元组元组（k k0 0k k11k kd-1d-1）组成）组成。k ki i把记录把记录分配分配到到1010个队列中，然后再个队列中，然后再根据根据 而而收集收集起来，使得所有关键字满足：起来，使得所有关键字满足：(k(k0 01 1k k1 11 1k kd-1d-11 1) )(k(k0 02 2k k1 12 2k kd-1d-12 2) )k k0 0n nk k11k kd-1d-1n n) ) 第 章 排 序 例：例：现给定现给定1010个链接在一

32、起的记录个链接在一起的记录 R R1 1、R R2 2、R R1010，其关键字为：，其关键字为：179,208,306,093,859,984,055,009,271,0179,208,306,093,859,984,055,009,271,03333它是它是10 10 进制数，数的范围为进制数，数的范围为000000，999999，基数为基数为1010，每个关键字有，每个关键字有3 3位有效数字，即位有效数字，即d=3d=3。对这组记录的基数分类过程如下对这组记录的基数分类过程如下 ：第 章 排 序 179179208208306306939385985998498455559 92712

33、713333B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 2712719393333398498455553063062082081791798598599 9队头指针队头指针队尾指针第一遍按关键字最低位将关键字值分配到相应队列第一遍按关键字最低

34、位将关键字值分配到相应队列记录的初始状态记录的初始状态第 章 排 序 2712719393333398498455553063062082081791798598599 9B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 33339849843063

35、062082089 955558598592712711791799393第二遍按关键字第二位将关键字值分配到相应队列第二遍按关键字第二位将关键字值分配到相应队列第一遍收集后的结果第一遍收集后的结果第 章 排 序 3063062082089 9333355558598592712711791799849849393B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 1791793063069849848598599 93333555593932082082712719 9333355559393179179208208271271306306859859984984第二遍收集后的结果第二遍收集后的结果第三遍按关键字第三位将关键字值分配到相应队列第三遍按关键字第三位将关键字值分配到相应队列第三遍收集后的结果第三遍收集后