數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第9章 排序

第9章排序?qū)W(xué)問題網(wǎng)絡(luò)購物中的商品排序在淘寶網(wǎng)、京東、當(dāng)當(dāng)、亞馬遜等網(wǎng)絡(luò)商城購物時，大家常用的一項功能就是排序。如圖所示，在搜索手機(jī)時，網(wǎng)站提供按銷量排序、按上市時間排序、按價格排序以及綜合排序等選項供用戶進(jìn)行比較和挑選。試設(shè)計并編寫程序幫助找出銷量最高的五款手機(jī)中上市時間最近的（新款）手機(jī)。9.1知識學(xué)習(xí)排序的基本概念排序：設(shè)有n個記錄的序列{r0，r1，…，rn

1}，其相應(yīng)的關(guān)鍵字分別是{k0，k1，…，kn

1}，排序是將這n個記錄重新排列，使之按關(guān)鍵字大小遞增（或遞減）有序排列。9.1知識學(xué)習(xí)9.1.1排序的基本概念排序分分類

內(nèi)排序：在排序的整個過程中，待排序的所有記錄全部被放置在內(nèi)存中外排序：由于待排序的記錄個數(shù)太多，不能同時放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。9.1知識學(xué)習(xí)9.1.1排序的基本概念排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。9.1知識學(xué)習(xí)9.1.1排序的基本概念排序算法的性能指標(biāo)1.

時間開銷：⑴比較：關(guān)鍵碼之間的比較；⑵移動：記錄從一個位置移動到另一個位置。

2.

空間開銷：輔助存儲空間3.

算法的穩(wěn)定性9.1知識學(xué)習(xí)9.1.2交換類排序基本思想：兩兩比較待排序記錄的關(guān)鍵字，若反序則交換相鄰兩記錄，直到?jīng)]有反序的記錄為止。兩種交換排序方法：冒泡排序快速排序冒泡排序voidBubbleSort(intr[],intn)//數(shù)組r中的n個數(shù)據(jù)保存在0~n-1中{ inti,j,temp; for(i=1;i<n;i++) for(j=0;j<n-i;j++) if(r[j]>r[j+1]) { temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; }}交換排序的主要操作是交換主要思想是：在待排序列中選兩個記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲位置。冒泡排序的時間性能分析最好情況（正序）：比較次數(shù)：n-1移動次數(shù)：0時間復(fù)雜度為O(n)。最壞情況（反序）：54321時間復(fù)雜度為O(n2)。43215321452134512345比較次數(shù)：移動次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時間復(fù)雜度為O(n2)。冒泡排序的時間性能分析冒泡排序的性能分析在平均情況下，冒泡排序的時間復(fù)雜度與最壞情況同數(shù)量級。冒泡排序只需要一個記錄的輔助空間，用來作為記錄交換的暫存單元。冒泡排序是一種穩(wěn)定的排序方法?？焖倥判蚴紫冗x一個軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個序列有序。需解決的關(guān)鍵問題：⑴如何選擇軸值？⑵如何實現(xiàn)分割（稱一次劃分）？⑶如何處理分割得到的兩個待排序子序列？⑷如何判別快速排序的結(jié)束？問題1：如何選擇軸值？選擇軸值的方法：1.使用第一個記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個記錄、最后一個記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個記錄的位置；4.隨機(jī)選取軸值。選取不同軸值的效果：決定兩個子序列的長度，子序列的長度最好相等。13652750384955ji1338652750495513652750493855jjiiijijjj問題2：如何實現(xiàn)一次劃分？解決方法：①取第一個記錄的關(guān)鍵字值作為基準(zhǔn)，將第一個記錄暫存于temp中，設(shè)兩個變量i，j分別指示將要劃分的最左、最右記錄的位置。②將j指向的記錄關(guān)鍵字值與基準(zhǔn)值進(jìn)行比較，如果j指向的記錄關(guān)鍵字值大，則j前移一個位置；重復(fù)此過程，直到j(luò)指向的記錄關(guān)鍵字值小于基準(zhǔn)值；若i<j，則將j指向的記錄移到i所指位置。③將i指向的記錄關(guān)鍵字值與基準(zhǔn)值進(jìn)行比較，如果i指向的記錄關(guān)鍵字值小，則i后移一個位置；重復(fù)此過程，直到i指向的記錄關(guān)鍵字值大于基準(zhǔn)；若i<j，則i指向的記錄移到j(luò)所指位置。④重復(fù)②、③步，直到i=j。問題2：如何實現(xiàn)一次劃分？算法描述：intPartition(intr[],inti,intj){ inttemp=r[i]; while(i<j) { while(i<j&&r[j]>=temp)j--; if(i<j)r[i++]=r[j]; while(i<j&&r[i]<=temp)i++; if(i<j)r[j--]=r[i]; } r[i]=temp; returni;}問題2：如何實現(xiàn)一次劃分？解決方法：對分割得到的兩個子序列遞歸地執(zhí)行快速排序。13275038495565ijij問題3：如何處理分割得到的兩個待排序子序列？pivot初始調(diào)用為QuickSort(r,0,n-1)voidQuickSort(intr[],inti,intj){if(i<j){pivot=Partition(r,i,j);QuickSort(r,i,pivot-1);QuickSort(r,pivot+1,j);}}

解決方法：若待排序列中只有一個記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別對分割所得的兩個子序列進(jìn)行快速排序（即遞歸處理）。問題4：如何判別快速排序的結(jié)束？voidQuickSort(intr[],inti,intj){if(i<j)

{pivot=Partition(r,i,j);

QuickSort(r,i,pivot-1);

QuickSort(r,pivot+1,j);

}}最壞情況：每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為O(n2)。最好情況：每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。平均情況：為O(nlog2n)。)()1(21211nOnninni=-=-?-=）（快速排序的時間性能分析快速排序的性能分析快速排序是一種不穩(wěn)定的排序方法。請舉例說明。2119.1知識學(xué)習(xí)9.1.2插入類排序基本思想：將待排序表看做是左、右兩部分，其中左邊為有序區(qū)，右邊為無序區(qū)，整個排序過程就是將右邊無序區(qū)中的記錄依次按關(guān)鍵字大小逐個插入到左邊有序區(qū)中，以構(gòu)成新的有序區(qū)，直到全部記錄都排好序。兩三種插入排序方法：直接插入排序折半插入排序希爾排序直接插入排序基本思想①將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始時有序區(qū)為待排序記錄序列中的第一個記錄，無序區(qū)包括所有剩余其他記錄；②將無序區(qū)的第一個記錄插入到有序區(qū)的合適位置中，從而使無序區(qū)減少一個記錄，有序區(qū)增加一個記錄；③重復(fù)執(zhí)行2），直到無序區(qū)中沒有記錄為止。以初始序列講解：[12]15092006362810.3.1直接插入排序voidInsertSort(intr[],intn){ inti,j,temp; for(i=1;i<n;i++) { temp=r[i]; for(j=i-1;j>=0&&temp<r[j];j--) r[j+1]=r[j]; r[j+1]=temp; }}外層循環(huán)控制排序趟數(shù)，執(zhí)行n-1次查找待插入位置內(nèi)層循環(huán)的執(zhí)行次數(shù)取決于在第i個記錄前有多少個記錄的關(guān)鍵字值大于第i個記錄的關(guān)鍵字值最好情況下（正序）：比較次數(shù)：n-1移動次數(shù)：2(n-1)最壞情況下（逆序或反序）：時間復(fù)雜度為O(n2)。54321453213452123451123454321比較次數(shù)：移動次數(shù)：2)1)(2(2-+=?=nnini2)1)(4(1-+=+?nnin2=i）（時間復(fù)雜度為O(n)。直接插入排序的時間性能分析平均情況下（隨機(jī)排列）：時間復(fù)雜度為O(n2)。比較次數(shù)：移動次數(shù)：4)1)(4(-+=?nnn2=i4)1)(2(2-+=?=nnnii2（21+i）直接插入排序的時間性能分析直接插入排序的性能分析空間性能：需要一個記錄的輔助空間。直接插入排序算法是一種穩(wěn)定的排序算法。直接插入排序算法簡單、容易實現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時。當(dāng)待排序的記錄個數(shù)較多時，大量的比較和移動操作使直接插入排序算法的效率降低。如何改進(jìn)直接插入排序？折半插入排序voidInsertSort(intr[],intn){ inti,j,temp; for(i=1;i<n;i++) { temp=r[i]; for(j=i-1;j>=0&&temp<r[j];j--) r[j+1]=r[j]; r[j+1]=temp; }}查找待插入位置改進(jìn)1：增加監(jiān)視哨for(i=1;i<n;i++)//把r[i]插入有序子文件if(r[i]<r[i-1]){r[0]=r[i];//r[0]為監(jiān)視哨，將r[i]暫時放在r[0]中j=i-1;while(r[0]<r[j])//找適當(dāng)?shù)牟迦胛恢?{r[j+1]=r[j];//移動記錄，騰出空位置 j--; }r[j+1]=r[0];//插入適當(dāng)位置}{temp=r[i],low=0;high=i-1;while(low<=high){mid=(low+high)/2if(temp<r[mid])high=mid-1;elselow=mid+1;}for(j=i-1;j>=low;j--)r[j+1]=r[j];r[low]=temp;}改進(jìn)2：折半查找折半插入排序采用折半插入排序法，可減少關(guān)鍵字的比較次數(shù)。每插入一個元素，需要比較的次數(shù)最多為折半查找判定樹的深度如插入第i個元素時，則需進(jìn)行l(wèi)og2i次比較，因此插入n

1個元素的平均比較次數(shù)為O(nlog2n)。折半插入排序法與直接插入排序法相比較，雖然改善了算法中比較次數(shù)的數(shù)量級為O(nlog2n)，但其并未改變移動元素的時間耗費(fèi)，所以折半插入排序總的時間復(fù)雜度仍然是O(n2)。希爾排序?qū)χ苯硬迦肱判蜻M(jìn)行改進(jìn)改進(jìn)的著眼點：（1）若待排序記錄按關(guān)鍵碼基本有序時，直接插入排序的效率可以大大提高；（2）由于直接插入排序算法簡單，則在待排序記錄數(shù)量n較小時效率也很高。希爾排序基本思想：先將待排序列劃分為若干小序列，在這些小序列中進(jìn)行插入排序；然后逐步擴(kuò)大小序列的長度，減少小序列的個數(shù)，這樣使待排序列逐漸處于更有序的狀態(tài)；最后對全體序列進(jìn)行一次直接插入排序，從而完成排序。希爾排序需解決的關(guān)鍵問題?（1）應(yīng)如何分割待排序記錄，才能保證整個序列逐步向基本有序發(fā)展？（2）子序列內(nèi)如何進(jìn)行直接插入排序？希爾排序分割待排序記錄的目的?1.減少待排序記錄個數(shù)；2.使整個序列向基本有序發(fā)展。

基本有序：例如{1,2,8,4,5,6,7,3,9}；

局部有序：例如{6,7,8,9,1,2,3,4,5}。

局部有序不能提高直接插入排序算法的時間性能。啟示?子序列的構(gòu)成不能是簡單地“逐段分割”，而是將相距某個“增量”的記錄組成一個子序列。0123456784021254925*16初始序列300813d=44021254925*16300813252125*300849131640d=21325210825*16304940252125*300813164049d=10825211325*16304049082513162125*403049希爾插入排序過程示例算法描述：for(d=n/2;d>=1;d=d/2){以d為增量，進(jìn)行組內(nèi)直接插入排序；}解決方法：將相隔某個“增量”的記錄組成一個子序列。增量應(yīng)如何取？希爾最早提出的方法是d1=n/2，di+1=di/2。問題1：應(yīng)如何分割待排序記錄？解決方法：在插入記錄r[i]時，自r[i-d]起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r[0]只是暫存單元，不是哨兵。當(dāng)搜索位置＜0，表示插入位置已找到。在搜索過程中，記錄后移也是跳躍d個位置。在整個序列中，前d個記錄分別是d個子序列中的第一個記錄，所以從第d+1個記錄開始進(jìn)行插入。問題2：子序列內(nèi)如何進(jìn)行直接插入排序？算法描述：voidShellSort(intr[],intn){for(d=n/2;d>=1;d=d/2)//以增量d進(jìn)行直接插入排序

{for(i=d;i<n;i++){temp=r[i];//暫存被插入記錄

for(j=i-d;j>=0&&temp<r[j];j=j-d)r[j+d]=r[j];//記錄后移d個位置

r[j+d]=temp;}}}

問題2：子序列內(nèi)如何進(jìn)行直接插入排序？希爾排序開始時增量較大，每個子序列中的記錄個數(shù)較少，從而排序速度較快；當(dāng)增量較小時，雖然每個子序列中記錄個數(shù)較多，但整個序列已基本有序，排序速度也較快。希爾排序算法的時間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。研究表明，希爾排序的時間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個特定范圍內(nèi)，希爾排序所需的比較次數(shù)和記錄的移動次數(shù)約為O(n1.3)。希爾排序算法的時間性能9.1.4選擇類排序選擇排序的主要操作是選擇主要思想：第i趟在n-i+1（i=1,2,…,n-1）個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個記錄。由于選擇排序方法每一趟總是從無序區(qū)中選出全局最?。ɑ蜃畲螅┑年P(guān)鍵字記錄，所以適合于從大量的記錄中選擇一部分排序記錄的問題。介紹兩種選擇類排序：簡單選擇排序和堆排序。9.1知識學(xué)習(xí)需解決的關(guān)鍵問題?⑴如何在待排序序列中選出關(guān)鍵碼最小的記錄？⑵如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？簡單選擇排序簡單選擇排序示例0821i=1最小者08交換21,08最小者16交換25,16最小者21交換49,212128i=02516490808i=22108284921284916251625i=3最小者25交換25,28i=4最小者28不交換492108281625254921081628252849210816282528無序區(qū)只有一個記錄簡單選擇排序示例212825164908kkk08問題1：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？解決方法：設(shè)置一個整型變量k，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。問題1：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？解決方法：設(shè)置一個整型變量k，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。算法描述：k=i; for(j=i+1;j<n;j++)

if(r[j]<r[k])k=j;問題2：如何確定最小記錄的最終位置？解決方法：第i趟簡單選擇排序的待排序區(qū)間是r[i]~r[n]，則r[i]是無序區(qū)第一個記錄，所以，將index所記載的關(guān)鍵碼最小的記錄與r[i]交換。算法描述：if(k!=i)r[i]←→r[k];voidSelectSort(intr[],intn){for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(r[j]<r[k])k=j;if(k!=i){temp=r[i];r[i]=r[k];r[k]=temp;}}}

簡單選擇排序算法最壞情況：3(n-1)次簡單選擇排序算法的性能分析移動次數(shù)：最好情況（正序）：0次空間性能：需一個輔助空間。穩(wěn)定性：是一種穩(wěn)定的排序算法。45231152341253412354123451234比較次數(shù)：)()1(21211nOnninni=-=-?-=）（簡單選擇排序的時間復(fù)雜度為O(n2)。簡單選擇排序的改進(jìn)改進(jìn)的著眼點：如何減少關(guān)鍵碼間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個排序過程的效率。堆排序堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（稱為小根堆），或每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（稱為大根堆）。182032364525385040281.小根堆的根結(jié)點是所有結(jié)點的最小者。2.較小結(jié)點靠近根結(jié)點，但不絕對。503845402836322018281.大根堆的根結(jié)點是所有結(jié)點的最大者。2.較大結(jié)點靠近根結(jié)點，但不絕對。堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（稱為小根堆），或每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（稱為大根堆）。堆和序列的關(guān)系將堆用順序存儲結(jié)構(gòu)來存儲，則堆對應(yīng)一組序列。503845402836322018285038453236402820182812345678910采用順序存儲基本思想：首先將待排序的記錄序列構(gòu)造成一個堆，此時，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。需解決的關(guān)鍵問題?（1）如何由一個無序序列建成一個堆（即初始建堆）？（2）當(dāng)堆頂記錄移走后，如何調(diào)整剩余記錄，使之成為一個新的堆（即重建堆）？堆排序堆調(diào)整在一棵完全二叉樹中，根結(jié)點的左右子樹均是堆，如何調(diào)整根結(jié)點，使整個完全二叉樹成為一個堆？283520121832201218323528201218323528voidsift(intr[],intk,intm)//假設(shè)n個記錄存放在數(shù)組r[1]~r[n]中{//要篩選結(jié)點的編號為k，堆中最后一個結(jié)點的編號為mi=k;j=2*i;//將篩選記錄暫存

while(j<=m)//篩選還沒有進(jìn)行到葉子{

if(j<m&&r[j]<r[j+1])j++;//左右孩子中取較大者if(r[i]>r[j])break;else{r[i]←→r[j];//將篩選記錄移到正確位置i=j;j=2*i;}}}堆調(diào)整——算法描述：問題1：如何由一個無序序列建成一個堆？282516321836163216282518362532162818362528323628161825算法描述：for(i=n/2;i>=1;i--)

sift(r,i,n);

最后一個結(jié)點（葉子）的序號是n，則最后一個分支結(jié)點即為結(jié)點n的雙親，其序號是n/2。問題1：如何由一個無序序列建成一個堆？問題2：去掉堆頂后，如何調(diào)整（重新建堆）？323628161825362832251816123456對應(yīng)162832251836123456對應(yīng)321628361825第i次處理堆頂是將堆頂記錄r[1]與序列中第n-i+1個記錄r[n-i+1]交換。r[1]←→r[n-i+1];28163236251816321628362518321628362518問題2：去掉堆頂后，如何調(diào)整（重新建堆）？解決方法：第

i次調(diào)整剩余記錄，此時，剩余記錄有n-i個，調(diào)整根結(jié)點至第n-i個記錄。算法描述：sift(r,1,n-i);堆排序算法voidHeapSort(intr[],intn){for(i=n/2;i>=1;i--)//初建堆

sift(r,i,n);for(i=1;i>n;i++){

r[1]←→r[n-i+1];//移走堆頂sift(r,1,n-i);//重建堆}}堆排序算法的性能分析第1個for循環(huán)是初始建堆，需要O(n)時間；第2個for循環(huán)是輸出堆頂重建堆，共需要取n-1次堆頂記錄，第i次取堆頂記錄重建堆需要O(log2i)時間，需要O(nlog2n)時間；因此整個時間復(fù)雜度為O(nlog2n)，這是堆排序的最好、最壞和平均的時間代價。10.5歸并排序主要思想：將若干有序序列逐步歸并，最終得到一個有序序列。歸并排序的主要操作是歸并歸并：將兩個或兩個以上的有序序列合并成一個有序序列的過程。

9.1知識學(xué)習(xí)9.1.5歸并排序具體過程：將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個長度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個長度為4的有序序列，……，直至得到一個長度為n的有序序列為止。需解決的關(guān)鍵問題?⑴如何將兩個有序序列合成一個有序序列？⑵怎樣完成一趟歸并？⑶如何控制二路歸并的結(jié)束？問題1：如何將兩個有序序列合成一個有序序列？voidMerge(intr[],intr1[],ints,intm,intt)//一次歸并{

inti,j,k;

i=s;j=m+1;k=s;

while(i<=m&&j<=t)

if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中較小者放入rl[k]elser1[k++]=r[j++];if(i<=m)while(i<=m)r1[k++]=r[i++];elsewhile(j<=t)r1[k++]=r[j++];}歸并可以就地進(jìn)行嗎?問題2：怎樣完成一趟歸并？在一趟歸并中，除最后一個有序序列外，其他有序序列中記錄的個數(shù)(稱為序列長度)相同，用h表示?，F(xiàn)在的任務(wù)是把若干個相鄰的長度為h的有序序列和最后一個長度有可能小于h的有序序列進(jìn)行兩兩歸并，把結(jié)果存放到r1[1]~r1[n]中。為此，設(shè)參數(shù)i，指向待歸并序列的第一個記錄，初始時i=1，顯然歸并的步長應(yīng)是2h。問題2：怎樣完成一趟歸并？

while(i<=n-2*h+1)

{Merge(r,r1,i,i+h-1,i+2*h-1);i=i+2*h;

}elsefor(k=i;k<=n;k++)r1[k]=r[k];}voidMergePass(intr[],intr1[],intn,inth){

inti,k;

i=1;if(i<n-h+1)Merge(r,r1,i,i+h-1,n);問題3：如何控制二路歸并的結(jié)束？解決方法：開始時，有序序列的長度h=1，結(jié)束時，有序序列的長度h=n，用有序序列的長度來控制排序的結(jié)束。voidMergeSort(intr[],intr1[],intn){h=1;while(h<n){MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;}}

二路歸并排序算法的性能分析時間性能：一趟歸并操作是將r[1]~r[n]中相鄰的長度為h的有序序列進(jìn)行兩兩歸并，并把結(jié)果存放到r1[1]~r1[n]中，這需要O(n)時間。整個歸并排序需要進(jìn)行l(wèi)og2n趟，因此，總的時間代價是O(nlog2n)。這是歸并排序算法的最好、最壞、平均的時間性能?？臻g性能：算法在執(zhí)行時，需要占用與原始記錄序列同樣數(shù)量的存儲空間，因此空間復(fù)雜度為O(n)。各種排序方法的比較對排序算法應(yīng)該從以下幾個方面綜合考慮：⑴時間復(fù)雜性；⑵空間復(fù)雜性；⑶穩(wěn)定性；⑷算法簡單性；⑸待排序記錄個數(shù)n的大?。虎视涗洷旧硇畔⒘康拇笮。虎岁P(guān)鍵碼的分布情況。各種排序方法的時間復(fù)雜度比較排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n)O(n2)希爾排序O(nlog2n)O(n1.3)O(n2)冒泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)簡單選擇排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)排序方法輔助空間直接插入排序O(1)希爾排序O(1)冒泡排序O(1)快速排序O(log2n)~O(n)簡單選擇排序O(1)堆排序O(1)歸并排序O(n)各種排序方法的空間復(fù)雜度比較穩(wěn)定性比較所有排序方法可分為兩類，（1）一類是穩(wěn)定的，包括直接插入排序、冒泡排序、直接選擇排序和歸并排序；（2）另一類是不穩(wěn)定的，包括希爾排序、快速排序和堆排序。算法簡單性比較從算法簡單性看，（1）一類是簡單算法，包括直接插入排序、直接選擇排序和冒泡排序，（2）另一類是改進(jìn)后的算法，包括希爾排序、堆排序、快速排序和歸并排序，這些算法都很復(fù)雜。待排序的記錄個數(shù)比較從待排序的記錄個數(shù)n的大小看，n越小，采用簡單排序方法越合適，n越大，采用改進(jìn)的排序方法越合適。因為n越小，O(n2)同O(nlog2n)的差距越小，并且輸入和調(diào)試簡單算法比輸入和調(diào)試改進(jìn)算法要少用許多時間。記錄本身信息量比較記錄本身信息量越大，移動記錄所花費(fèi)的時間就越多，所以對記錄的移動次數(shù)較多的算法不利。排序方法最好情況最壞情況平均情況直接插入排序O(n)O(n2)O(n2)冒泡排序0O(n2)O(n2)直接選擇排序0O(n)O(n)關(guān)鍵碼的分布情況比較當(dāng)待排序記錄按關(guān)鍵碼有序時，插入排序和冒泡排序能達(dá)到O(n)的時間復(fù)雜度；對于快速排序而言，這是最壞的情況，此時的時間性能褪化為O(n2)；選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。9.2知識應(yīng)用假設(shè)采用數(shù)據(jù)文件存儲手機(jī)信息，每條記錄包括：貨號、手機(jī)名稱、價格、銷售量、上市時間。程序?qū)崿F(xiàn)時，從數(shù)據(jù)文件中讀出數(shù)據(jù)，并從下標(biāo)為1的位置開始，存放到一個順序表中。為了后序求最新上市的手機(jī)，每條記錄增加了一個時間差字段interval，該字段記錄手機(jī)上市時間與用戶查詢當(dāng)時相差的秒數(shù)，該值越小，代表上市時間最新。導(dǎo)學(xué)問題可轉(zhuǎn)換為兩個子問題：按銷售量遞減排序后得出前五名；求銷售量前五名中，時間差最小值的所對應(yīng)的手機(jī)品牌（即：記錄時間差最小值對應(yīng)的存儲位置即可）。9.3知識拓展9.3.1冒泡排序的改進(jìn)改進(jìn)的著眼點：在冒泡排序中，記錄的比較和移動是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個單元，因而總的比較次數(shù)和移動次數(shù)較多。減少總的比較次數(shù)和移動次數(shù)增大記錄的比較和移動距離較大記錄從前面直接移動到后面較小記錄從后面直接移動到前面問題1：傳統(tǒng)的冒泡排序算法存在的問題？

如何判別冒泡排序的結(jié)束？不論正序、逆序，都需要進(jìn)行n-1趟掃描。改進(jìn)一：增設(shè)一個變量exchange來記錄是否發(fā)生交換，如果未發(fā)生交換即終止循環(huán)繼續(xù)。算法描述：boolexchange=true;inti=1;while(exchange){exchange=false;for(j=0;j<n-i;j++)

if(r[j]>r[j+1]) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;

exchange=true;}i++;}問題2：對于2,1,3,4,5,6,7,8,9,10，要進(jìn)行多少次比較？如何確定冒泡排序的范圍？仍要進(jìn)行9+8=17次比較改進(jìn)二：前一改進(jìn)中，變量exchange用于標(biāo)記是否發(fā)生了交換，實際上我們還可以考慮用其記錄發(fā)生交換的位置，以進(jìn)一步提高算法的處理效率。處理1：exchange記載這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。算法描述：if（r[j]>r[j+1]）{

r[j]←→r[j+1]；

exchange=j；}改進(jìn)二：處理2：設(shè)bound位置的記錄是無序區(qū)的最后一個記錄，則每趟冒泡排序的范圍是r[1]~r[bound]。在一趟排序后，從exchange位置之后的記錄一定是有序的，所以bound=exchange。算法描述：bound=exchange;for(j=0;j<bound;j++) if（r[j]>r[j+1]）{r[j]←→r[j+1]；exchange=j；}voidBubbleSort2(intr[],intn){