《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件6-12歸并排序2

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：丁慧歸并排序常州信息職業(yè)技術(shù)學(xué)院0207（1）基本思想：將待排序的文件R1.n看作是n個(gè)長(zhǎng)度為1的有序子文件，將這些子文件兩兩歸并，直到得到一個(gè)長(zhǎng)度為n的有序文件為止。2、 自底向上歸并排序歸并排序（2）排序方法：初始狀態(tài)：n個(gè)有序區(qū)R1，R2，Rn。第i趟排序前狀態(tài)：設(shè)第i趟排序時(shí)區(qū)間長(zhǎng)度為length，則各有序區(qū)為R1. length，Rlength+1. 2*length，R2*length+1. 3*length，。排序方法依次對(duì)長(zhǎng)度為length的兩個(gè)相鄰子文件Ri,i+length-1，Ri+length, i+2*length-1

2、進(jìn)行歸并，如果最后還剩兩個(gè)子文件，即i+length-1n，其中最后一個(gè)子文件長(zhǎng)度小于length，將這兩個(gè)子文件也歸并，如果最后只剩一個(gè)子文件，即in且i+length+1n，則該子文件輪空，無(wú)須歸并。一趟歸并結(jié)束將長(zhǎng)度值length增加到2*length。重復(fù)進(jìn)行第步，直到全部記錄都在一個(gè)文件為止。08初始關(guān)鍵字 25 57 48 37 12 92 86歸并排序第一趟歸并 25 57 37 48 12 92 86第二趟歸并 25 37 48 57 12 86 92第三趟歸并 12 25 37 48 57 86 922、 自底向上歸并排序09（3）排序算法：void BottomUpMerg

3、eSort(SeqList R) 自底向上歸并排序 int length,i; for(length=1;lengthn;length*=2) /兩兩歸并 for(i=1;i+2*length-1=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1);/歸并長(zhǎng)度為length的兩個(gè)相鄰子文件if(i+length-1n) /尚有兩個(gè)子文件，其中后一個(gè)長(zhǎng)度小于length Merge(R,i,i+length-1,n); /歸并最后兩個(gè)子文件 歸并排序2、 自底向上歸并排序10（4）算法分析：時(shí)間性能：自底向上歸并排序每進(jìn)行一次兩兩歸并即完成一趟排序，所以共進(jìn)行l(wèi)gn 趟排序，每趟歸并時(shí)間為O(n)，時(shí)間復(fù)雜度為O(nlgn)?？臻g性能：輔助空間為O(n)，