漫談經典排序算法二 - 下載本文

11月熱門下載資源TOP100強力推薦! 點擊了解英特爾云計算

漫談經典排序算法:二、各種插入排序解析及性能比較

分類: Data Structures And Algorithms2011-09-17 09:55700人閱讀評論(0)收藏舉報

1、序言

這是《漫談經典排序算法系列》第二篇,解析了各種插入排序算法。主要包括:直接插入排序、折半插入排序、表插入排序、希爾插入排序。每一種算法的開頭都敘述了引出該算法的原因,然后給出代碼,最后分析算法效率及和其他插入排序相比,優劣在哪里。

各種排序算法的解析請參考如下:

《漫談經典排序算法:一、從簡單選擇排序到堆排序的深度解析》 《漫談經典排序算法:二、各種插入排序解析及性能比較》 《漫談經典排序算法:三、冒泡排序 && 快速排序》 《漫談經典排序算法:四、歸并排序》

《漫談經典排序算法:五、線性時間排序(計數、基數、桶排序)》 《漫談經典排序算法:六、各種排序算法總結》

注:為了敘述方便,本文以及源代碼中均不考慮A[0],默認下標從1開始。

2、直接插入排序

2.1 引出

給定待排序序列A[ 1.....n ],現假設A[1...i]已經有序,那么我們取出A[i+1]插入到序列A[1...i].這樣有序序列記錄數就增加了1.如此重復上述操作,不斷取出記錄插入有序序列,直到A[n]插入到有序序列,排序完成。

2.2 代碼

view plaincopy to clipboardprint?

1. //直接插入排序

2. void straightInsertSort(int *a,int n) 3. { 4. int i,j; 5. int temp;

6. //逐個記錄插入有序序列 7. for(i=2;i<=n;i++){ 8. temp=a[i];

9. //把a[i]插入有序序列

10. for(j=i-1;j>=1;j--){ 11. if(temp

16. a[j+1]=temp; 17. } 18. }

//直接插入排序void straightInsertSort(int *a{int i,j;int temp;//逐個記錄插入有序序列 2.3 效率分析 容易看出,要插入的記錄個數為n-1,其中關鍵字的比較次數和記錄移動次數是依賴于給出的待排序序列是否基本有序。在最佳情況下(待排序序列有序),比較次數和移動次數時間為o(1),所以時間復雜度為o(n).在最壞情況下(待排序序列逆序)和平均時間均為o(n^2).從上述分析中可以看出,直接插入排序適合記錄數比較少、給定序列基本有序的情況。熟悉了排序過程我們發現,直接插入排序是一種穩定的原地排序算法。 3、折半插入排序 3.1 引出 在直接插入排序過程中,我們是把一個記錄插入到有序序列中,至于要插入到有序序列中的哪個位置呢?采用的是順序查找確定插入的位置。顯然對于有序序列,折半查找的效率要高,所以在尋找插入位置時可以用折半查找。折半查找主要分為三步:1、查找要插入的位置 2、移位 3、把記錄插入相應的位置。 3.2 代碼 view plaincopy to clipboardprint? 1. //折半查找

2. int binarySearch(int *a,int low,int high,int key)

3. {

4. int mid=(low+high)/2; 5. if(low>high) 6. return low; 7. if(a[mid]==key) 8. return mid;

9. else if(key

10. return binarySearch(a,low,mid-1,key); 11. else

12. return binarySearch(a,mid+1,high,key); 13. } 14.

15. //折半插入排序

16. void binaryInsertSort(int *a,int n) 17. {

18. int i,j,site,temp; 19. for(i=2;i<=n;i++){ 20. //1.折半查找要插入的位置

21. site=binarySearch(a,1,i,a[i]); 22. temp=a[i]; 23. //2.移位

24. for(j=i;j>site;j--) 25. a[j]=a[j-1]; 26. //3.插入a[i] 27. a[site]=temp; 28. } 29. }

//折半查找int binarySearch(int *a,int low{int mid=(low+high)/2;if(low>high)return low; 3.3 效率分析 折半插入排序是對直接插入排序的一種改進,這種改進只考慮了關鍵字比較次數,并沒有減少移位次數,所以平均時間和最壞情況下(待排序序列逆序)時間復雜度o(n^2),如果記錄數量很大的話,這兩種情況下是優于直接插入排序。再來看一下最佳情況(待排序序列有序),此時關鍵字比較次數并不為o(1),時間復雜度為o(n*log2n)。(其中折半查找時間復雜度o(log2n),這個在以后寫查找的時候再分析,這里不做詳細講解。)。所以在記錄數較小、待排序序列基本有序情況下直接插入排序優于折半插入排序。此外,折半插入排序是不穩定的原地排序,實現起來也較復雜。

4、表插入排序

4.1 引出

折半插入排序相對于直接插入排序來說減少了比較次數。那么我們可不可以減少移動次數呢,答案是可以的。于是就有了表插入排序,用一個靜態鏈表來存儲待排序序列,其他操作和直接插入排序很像。主要步驟:1、初始化鏈表 2、取出要插入的記錄 3、遍歷鏈表尋找插入位置 4、記錄插入鏈表中。

4.2 代碼

view plaincopy to clipboardprint?

1. //靜態鏈表 2. typedef struct 3. {

4. int key;//關鍵字

5. int next;//指向下一個關鍵字的下標 6. }Node,*PNode; 7.

8. //表插入排序

9. void tableInsertSort(PNode list,int n) 10. {

11. int p,head; 12. int i; 13. //初始化

14. list[0].next=1; 15. list[1].next=0; 16.

17. //逐個插入

18. for(i=2;i<=n;i++){ 19. head=0;

20. p=list[0].next; 21. //遍歷鏈表,尋找插入位置

22. while(p!=0 && list[p].key<=list[i].key){ 23. head=p;

24. p=list[p].next; 25. }

26. if(p==0){//插入的值是最大值 27. list[i].next=p; 28. list[head].next=i; 29. }else{

30. list[i].next=p; 31. list[head].next=i; 32. } 33. 34. } 35. }

//靜態鏈表typedef struct{int key;//關鍵字int next;//指向下一個關鍵}Node,*PNode; 4.3 效率分析 表插入排序也是對直接插入排序的一種改進,這種改進只減少了移動次數,并沒有減少關鍵字比較次數,所以平均時間和最壞情況下(待排序序列逆序)時間復雜度o(n^2),如果記錄數量很大的話,這兩種情況下是優于直接插入排序。再來看一下最佳情況(待排序序列有序),關鍵字比較次數并為o(1),時間復雜度為o(n)。此時和直接插入排序時間復雜度一樣。此外,表插入排序改變了記錄的存儲結構,無法順序訪問,是一種穩定的排序算法,實現起來也較復雜。 5、希爾插入排序 5.1 引出 上述兩種排序都是只考慮減少關鍵字比較次數或者只考慮減少關鍵字移動次數。有沒有別的改進辦法呢?我們注意到,直接插入排序適合于記錄數較少、基本有序的情況。于是我們可以先將整個待排序序列分割成若干子序列分別進行直接插





3d走势图