十大常用算法

前言

最近在研究一些經常用到的東西想把它們做一個彙總，想了想用到最多的應該是排序算法，是以對排序算法做了個總結，并自己用C++實作了一下。

一、算法概述

0.1 算法分類

十種常見排序算法可以分為兩大類：

非線性時間比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破O(nlogn)，是以稱為非線性時間比較類排序。

線性時間非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以稱為線性時間非比較類排序。 

0.2 算法複雜度

0.3 相關概念

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。

不穩定：如果a原本在b的前面，而a=b，排序之後 a 可能會出現在 b 的後面。

時間複雜度：對排序資料的總的操作次數。反映當n變化時，操作次數呈現什麼規律。

空間複雜度：是指算法在計算機内執行時所需存儲空間的度量，它也是資料規模n的函數。 

二、快速排序

假設我們現在對“6  1  2 7  9  3  4  5 10  8”這個10個數進行排序。首先在這個序列中随便找一個數作為基準數（不要被這個名詞吓到了，就是一個用來參照的數，待會你就知道它用來做啥的了）。為了友善，就讓第一個數6作為基準數吧。接下來，需要将這個序列中所有比基準數大的數放在6的右邊，比基準數小的數放在6的左邊，類似下面這種排列：

3  1  2 5  4  6  9 7  10  8
           

在初始狀态下，數字6在序列的第1位。我們的目标是将6挪到序列中間的某個位置，假設這個位置是k。現在就需要尋找這個k，并且以第k位為分界點，左邊的數都小于等于6，右邊的數都大于等于6，遞歸對左右兩個區間進行同樣排序即可。想一想，你有辦法可以做到這點嗎？這就是快速排序所解決的問題。

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的政策，通常稱其為分治法(Divide-and-ConquerMethod)。它的平均時間複雜度為O(nlogn)，最壞時間複雜度為O(n^2).

首先上圖：

 從圖中我們可以看到：

left指針，right指針，base參照數。

其實思想是蠻簡單的，就是通過第一遍的周遊（讓left和right指針重合）來找到數組的切割點。

第一步：首先我們從數組的left位置取出該數（20）作為基準（base）參照物。(如果是選取随機的，則找到随機的哨兵之後，将它與第一個元素交換，開始普通的快排)

第二步：從數組的right位置向前找，一直找到比（base）小的數，如果找到，将此數賦給left位置（也就是将10賦給20），此時數組為：10，40，50，10，60， left和right指針分别為前後的10。

第三步：從數組的left位置向後找，一直找到比（base）大的數，如果找到，将此數賦給right的位置（也就是40賦給10），此時數組為：10，40，50，40，60， left和right指針分别為前後的40。

第四步：重複“第二,第三“步驟，直到left和right指針重合，最後将（base）放到40的位置， 此時數組值為： 10，20，50，40，60，至此完成一次排序。

第五步：此時20已經潛入到數組的内部，20的左側一組數都比20小，20的右側作為一組數都比20大， 以20為切入點對左右兩邊數按照"第一，第二，第三，第四"步驟進行，最終快排大功告成。

快速排序動圖示範：

算法分析：

• 最佳情況：T(n) = O(nlogn)
• 最差情況：T(n) = O(n2)
• 平均情況：T(n) = O(nlogn)

快速排序代碼：

//快速排序
void QuickSort(int *h, int left, int right){
    if(h == nullptr) return;
    if(left >= right) return;

    //防止有序隊列導緻快速排序效率降低
    srand((unsigned)time(nullptr));
    int len = right - left;
    int kindex = rand() % (len+1) + left;
    swap(h[left], h[kindex]);
    int key = h[left], i = left, j = right;
    while(i < j){
        while(h[j]>=key && i<j) --j;
        if(i<j) h[i] = h[j];
        while(h[i]< key && i<j) ++i;
        if(i<j) h[j]=h[i];
    }
    h[i]=key;

    QuickSort(h,left,i-1);
    QuickSort(h,j+1,right);
}
           

三、冒泡排序

1.原理

冒泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交換，最終，最大記錄就被“沉到”了序列的最後一個位置，第二遍掃描将第二大記錄“沉到”了倒數第二個位置，重複上述操作，直到n-1 遍掃描後，整個序列就排好序了。

冒泡排序動圖示範:

算法分析

• 最佳情況：T(n) = O(n)

當輸入的資料已經是正序時（都已經是正序了，為毛何必還排序呢....）

• 最差情況：T(n) = O(n2)

當輸入的資料是反序時(卧槽，我直接反序不就完了....)

• 平均情況：T(n) = O(n2)

2.算法實作

//冒泡排序
void BubbleSort(int *h, size_t len){
    if(h == nullptr) return;
    if(len <= 1) return;

    for(int i = 0; i < len; ++i){
        for(int j = 0; j < len-i-1; ++j){
            if(h[j] > h[j+1]){
                int temp = h[j];
                h[j] = h[j+1];
                h[j+1] = temp;
            }
        }
    }
}
           

四、選擇排序

選擇排序也是一種簡單直覺的排序算法。它的工作原理很容易了解：初始時在序列中找到最小（大）元素，放到序列的起始位置作為已排序序列；然後，再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

注意選擇排序與冒泡排序的差別：冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，進而将目前最小（大）元素放到合适的位置；而選擇排序每周遊一次都記住了目前最小（大）元素的位置，最後僅需一次交換操作即可将其放到合适的位置。

選擇排序動圖示範：

算法分析:

• 最佳情況：T(n) = O(n2)
• 最差情況：T(n) = O(n2)
• 平均情況：T(n) = O(n2)

算法實作：

//選擇排序
void SelectionSort(int *h, size_t len){
    if(h == nullptr) return;
    if(len <= 1) return;

    for(int i = 0; i < len; ++i){
        int index = i;
        for(int j = i+1; j < len; ++j){
            if(h[index] > h[j])
                index = j;
        }
        if(index != i){
            int temp = h[i];
            h[i] = h[index];
            h[index] = temp;
        }
    }
}
           

五、插入排序

直接插入排序（straight insertion sort），有時也簡稱為插入排序（insertion sort），是減治法的一種典型應用。其基本思想如下：

• 對于一個數組A[0,n]的排序問題，假設認為數組在A[0,n-1]排序的問題已經解決了。
• 考慮A[n]的值，從右向左掃描有序數組A[0,n-1]，直到第一個小于等于A[n]的元素，将A[n]插在這個元素的後面。

　　很顯然，基于增量法的思想在解決這個問題上擁有更高的效率。

直接插入排序對于最壞情況（嚴格遞減的數組），需要比較和移位的次數為n(n-1)/2；對于最好的情況（嚴格遞增的數組），需要比較的次數是n-1，需要移位的次數是0。當然，對于最好和最壞的研究其實沒有太大的意義，因為實際情況下，一般不會出現如此極端的情況。然而，直接插入排序對于基本有序的數組，會展現出良好的性能，這一特性，也給了它進一步優化的可能性。（希爾排序）。直接插入排序的時間複雜度是O(n^2)，空間複雜度是O(1)，同時也是穩定排序。

下面用一個具體的場景，直覺地體會一下直接插入排序的過程：

場景：

現有一個無序數組，共7個數：89 45 54 29 90 34 68。

使用直接插入排序法，對這個數組進行升序排序。

插入排序動圖示範:

算法分析:

• 最佳情況：輸入數組按升序排列。T(n) = O(n)
• 最壞情況：輸入數組按降序排列。T(n) = O(n2)
• 平均情況：T(n) = O(n2)

算法實作：

//插入排序
void InsertSort(int *h, size_t len){
    if(h == nullptr) return;
    if(len <= 1) return;

    for(int i = 1; i < len; ++i){
        for(int j = i; j > 0; --j){
            if(h[j] < h[j-1]){
                int temp = h[j];
                h[j] = h[j-1];
                h[j-1] = temp; 
            }else break;
        }
    }
}
           

六、歸并排序

基本思想

　　歸并排序（MERGE-SORT）是利用歸并的思想實作的排序方法，該算法采用經典的分治（divide-and-conquer）政策（分治法将問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則将分的階段得到的各答案"修補"在一起，即分而治之)。

分而治之

 　　可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實作（也可采用疊代的方式去實作）。分階段可以了解為就是遞歸拆分子序列的過程，遞歸深度為log2n。

合并相鄰有序子序列

　　再來看看治階段，我們需要将兩個已經有序的子序列合并成一個有序序列，比如上圖中的最後一次合并，要将[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實作步驟。

歸并排序動圖示範:

算法分析：

• 最佳情況：T(n) = O(n)
• 最差情況：T(n) = O(nlogn)
• 平均情況：T(n) = O(nlogn)

算法實作：

1. //歸并排序

2. void MergeArray(int* arr, size_t left, size_t mid, size_t right, int* temp)

3. {

4. if(arr==NULL) return;

5. size_t i=left,j=mid+1,k=0;

6. while(i<=mid && j<=right)

7. {

8. if(arr[i]<=arr[j])

9. {

10. temp[k++]=arr[i++];

11. continue;

12. }

13. temp[k++]=arr[j++];

14. }

15. while(i<=mid)

16. temp[k++]=arr[i++];

17. while(j<=right)

18. temp[k++]=arr[j++];

19. memcpy(&arr[left],temp,k*sizeof(int));

20. return;

21. }

22. void MMergeSort(int* arr, size_t left, size_t right, int* temp)

23. {

24. if(left<right)

25. {

26. size_t mid=(left+right)/2;

27. MMergeSort(arr, left, mid, temp);

28. MMergeSort(arr, mid+1,right, temp);

29. MergeArray(arr,left, mid, right, temp);

30. }

31. }

32. void MergeSort(int* h, size_t len)

33. {

34. if(h==NULL) return;

35. if(len<=1) return;

36. int* temp=(int*)calloc(len,sizeof(int));

37. MMergeSort(h, 0, len-1, temp);

38. memcpy(h,temp,sizeof(int)*len);

39. free(temp);

40. return;

41. }

七、希爾排序

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。本文會以圖解的方式詳細介紹希爾排序的基本思想及其代碼實作。

基本思想

　　希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

　　簡單插入排序很循規蹈矩，不管數組分布是怎麼樣的，依然一步一步的對元素進行比較，移動，插入，比如[5,4,3,2,1,0]這種倒序序列，數組末端的0要回到首位置很是費勁，比較和移動元素均需n-1次。而希爾排序在數組中采用跳躍式分組的政策，通過某個增量将數組元素劃分為若幹組，然後分組進行插入排序，随後逐漸縮小增量，繼續按組進行插入排序操作，直至增量為1。希爾排序通過這種政策使得整個數組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在後。然後縮小增量，到增量為1時，其實多數情況下隻需微調即可，不會涉及過多的資料移動。

　　我們來看下希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2...1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。此處我們做示例使用希爾增量。

算法實作：

//希爾排序
void ShellSort(int *h, size_t len){
    if(h == nullptr) return;
    if(len <= 1) return;

    for(int div = len/2; div >= 1; div/=2){
        for(int i = 0; i < div; ++i){
            for(int j = div+i; j < len; j+=div){
                for(int k = j; k > i; k-=div){
                    if(h[k] < h[k-div]){
                        int temp = h[k-div];
                        h[k-div] = h[k];
                        h[k] = temp;
                    }else break;
                }
            }
        }
    }
}
           

八、堆排序

堆排序實際上是利用堆的性質來進行排序的，要知道堆排序的原理我們首先一定要知道什麼是堆。 

堆的定義： 

堆實際上是一棵完全二叉樹。 

堆滿足兩個性質: 

1、堆的每一個父節點都大于（或小于）其子節點； 

2、堆的每個左子樹和右子樹也是一個堆。 

堆的分類： 

堆分為兩類： 

1、最大堆（大頂堆）：堆的每個父節點都大于其孩子節點； 

2、最小堆（小頂堆）：堆的每個父節點都小于其孩子節點； 

堆的存儲： 

一般都用數組來表示堆，i結點的父結點下标就為(i – 1) / 2。它的左右子結點下标分别為2 * i + 1和2 * i + 2。如下圖所示： 

堆排序： 

由上面的介紹我們可以看出堆的第一個元素要麼是最大值（大頂堆），要麼是最小值（小頂堆），這樣在排序的時候（假設共n個節點），直接将第一個元素和最後一個元素進行交換，然後從第一個元素開始進行向下調整至第n-1個元素。是以，如果需要升序，就建一個大堆，需要降序，就建一個小堆。 

堆排序的步驟分為三步: 

1、建堆（升序建大堆，降序建小堆）； 

2、交換資料； 

3、向下調整。 

假設我們現在要對數組arr[]={8,5,0,3,7,1,2}進行排序（降序）： 

首先要先建小堆： 

堆建好了下來就要開始排序了： 

現在這個數組就已經

是有序的了。 

堆排序動圖示範：

算法分析：

• 最佳情況：T(n) = O(nlogn)
• 最差情況：T(n) = O(nlogn)
• 平均情況：T(n) = O(nlogn)

算法實作：

1. //堆排序

3. //====調整=====

4. void AdjustHeap(int* h, int node, int len) //----node為需要調整的結點編号，從0開始編号;len為堆長度

5. {

6. int index=node;

7. int child=2*index+1; //左孩子，第一個節點編号為0

8. while(child<len)

9. {

10. //右子樹

11. if(child+1<len && h[child]<h[child+1])

12. {

13. child++;

14. }

15. if(h[index]>=h[child]) break;

16. Swap(h[index],h[child]);

17. index=child;

18. child=2*index+1;

19. }

20. }

21. //====建堆=====

22. void MakeHeap(int* h, int len)

23. {

24. for(int i=len/2;i>=0;--i)

25. {

26. AdjustHeap(h, i, len);

27. }

28. }

29. //====排序=====

30. void HeapSort(int* h, int len)

31. {

32. MakeHeap(h, len);

33. for(int i=len-1;i>=0;--i)

34. {

35. Swap(h[i],h[0]);

36. AdjustHeap(h, 0, i);

37. }

38. }

九、基數排序

基數排序與本系列前面講解的七種排序方法都不同，它不需要比較關鍵字的大小。

它是根據關鍵字中各位的值，通過對排序的N個元素進行若幹趟“配置設定”與“收集”來實作排序的。 

1.LSD(低位到高位的排序)

不妨通過一個具體的執行個體來展示一下，基數排序是如何進行的。 

設有一個初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我們知道，任何一個阿拉伯數，它的各個位數上的基數都是以0~9來表示的。

是以我們不妨把0~9視為10個桶。 

我們先根據序列的個位數的數字來進行分類，将其分到指定的桶中。例如：R[0] = 50，個位數上是0，将這個數存入編号為0的桶中。

分類後，我們在從各個桶中，将這些數按照從編号0到編号9的順序依次将所有數取出來。

這時，得到的序列就是個位數上呈遞增趨勢的序列。 

按照個位數排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下來，可以對十位數、百位數也按照這種方法進行排序，最後就能得到排序完成的序列。

LSD 算法實作：

1. int GetMaxDight(int* h, int len)

2. {

3. if(h==NULL) return 0;

4. if(len<1) return 0;

5. int max=h[0];

6. for(int i=1;i<len;++i)

7. {

8. if(h[i]>max) max=h[i];

9. }

10. int digit=1;

11. while(max/10!=0)

12. {

13. max/=10;

14. ++digit;

15. }

16. return digit;

17. }

18. int GetReminder(int value,int digit)

19. {

20. int div=1;

21. for(int i=1;i<digit;++i)

22. div*=10;

23. return value/div%10;

24. }

25. void RadixSort_LSD(int* h, int len)

26. {

27. if(h==NULL) return;

28. if(len<=1) return;

29. int digit=GetMaxDight(h,len);

30. //printf("MaxDigit:%d\n", digit);

31. int count[10]={0};

32. int *tmp=(int*)calloc(len,sizeof(int));

33. for(int d=1;d<=digit;++d)

34. {

35. memset(count,0,sizeof(count));

36. for(int i=0;i<len;++i)

37. {

38. count[GetReminder(h[i],d)]++;

39. }

40. //求右邊界

41. for(int i=1;i<10;++i)

42. {

43. count[i]+=count[i-1];

44. }

45. for(int i=len-1;i>=0;--i)

46. {

47. int r=GetReminder(h[i],d);

48. int index=count[r];

49. tmp[index-1]=h[i];

50. count[r]--;

51. }

52. memcpy(h,tmp,len*sizeof(int));

53. }

54. free(tmp);

55. }

56. void RadixSort_LSD_Reverse(int* h, int len)

57. {

58. if(h==NULL) return;

59. if(len<=1) return;

60. int digit=GetMaxDight(h,len);

61. //printf("MaxDigit:%d\n", digit);

62. int count[10]={0};

63. int *tmp=(int*)calloc(len,sizeof(int));

64. for(int d=1;d<=digit;++d)

65. {

66. memset(count,0,sizeof(count));

67. for(int i=0;i<len;++i)

68. {

69. count[GetReminder(h[i],d)]++;

70. }

71. //printf("haha\n");

72. //求右邊界

73. for(int i=8;i>=0;--i)

74. {

75. count[i]+=count[i+1];

76. }

77. for(int i=len-1;i>=0;--i)

78. {

79. int r=GetReminder(h[i],d);

80. int index=count[r];

81. tmp[index-1]=h[i];

82. count[r]--;

83. }

84. memcpy(h,tmp,len*sizeof(int));

85. }

86. free(tmp);

87. }

2.MSD(高位到低位排序)

下面我們直接來介紹MSD基數排序的步驟。

MSD基數排序是從最高位開始對序列進行分組，到最低位為止。但是其實作過程是和LSD基數排序不同的，排序過程中需要用到遞歸函數。

待排序序列

170, 45, 75, 90, 2, 24, 802, 66

我們看到，這裡面的最大的數是3位數。是以說我們開始從百位對這些數進行分組

0: 045, 075, 090,002, 024, 066

1: 170

2-7: 空

8: 802

9: 空

從這裡開始就和LSD基數排序有差别了。在LSD基數排序中，每次分好組以後開始對桶中的資料進行收集。然後根據下一位，對收集後的序列進行分組。而對于MSD，在這裡不會對桶中的資料進行收集。我們要做的是檢測每個桶中的資料。當桶中的元素個數多于1個的時候，要對這個桶遞歸進行下一位的分組。

在這個例子中，我們要對0桶中的所有元素根據十位上的數字進行分組

0: 002

1: 空

2: 024

3: 空

4: 045

5: 空

6: 066

7: 075

8: 空

9: 090

按照上面所說，我們應該再遞歸的對每個桶中的元素根據個位上的數進行分組。但是我們發現，現在在每個桶中的元素的個數都是小于等于1的。是以，到這一步我們就開始回退了。也就是說我們開始收集桶中的資料。收集完成以後，回退到上一層。此時按照百位進行分組的桶變成了如下的形式

0: 002, 024, 045,066, 075, 090

1: 170

2-7: 空

8: 802

9: 空

然後我們在對這個桶中的資料進行收集。收集起來以後序列如下

2, 24, 45, 66, 75, 90, 170, 802

整個MSD基數排序就是按照上面的過程進行的。

在我對MSD基數排序步驟進行叙述的時候，中間遞歸函數的過程可能叙述的不夠清楚。我個人建議對遞歸函數不了解的可以先了解一下遞歸函數的原理，然後再回來看這個過程可能對MSD基數排序過程更容易了解。

算法實作：

1. int GetMaxDight(int* h, int len)

2. {

3. if(h==NULL) return 0;

4. if(len<1) return 0;

5. int max=h[0];

6. for(int i=1;i<len;++i)

7. {

8. if(h[i]>max) max=h[i];

9. }

10. int digit=1;

11. while(max/10!=0)

12. {

13. max/=10;

14. ++digit;

15. }

16. return digit;

17. }

18. int GetReminder(int value,int digit)

19. {

20. int div=1;

21. for(int i=1;i<digit;++i)

22. div*=10;

23. return value/div%10;

24. }

25. void RRadixSort_MSD(int* h, int begin, int end, int digit)

26. {

27. if(h==NULL) return;

28. if(begin>=end) return;

29. if(digit<1) return;

30. int start[10];

31. int count[10]={0};

32. int *tmp=(int*)calloc(end-begin+1,sizeof(int));

33. for(int i=begin;i<=end;++i)

34. {

35. count[GetReminder(h[i],digit)]++;

36. }

37. memcpy(start,count,sizeof(start));

38. //求右邊界

39. for(int i=1;i<10;++i)

40. {

41. start[i]+=start[i-1];

42. }

43. for(int i=end;i>=begin;--i)

44. {

45. int r=GetReminder(h[i],digit);

46. int index=start[r];

47. tmp[index-1]=h[i];

48. start[r]--;

49. }

51. memcpy(&h[begin],tmp,(end-begin+1)*sizeof(int));

52. for(int i=0;i<10;++i)

53. {

54. if(count[i]>1)

55. {

56. RRadixSort_MSD(h, start[i], start[i]+count[i]-1, digit-1);

57. }

58. }

59. }

60. void RadixSort_MSD(int* h, int len)

61. {

62. if(h==NULL) return;

63. if(len<=1) return;

64. int digit=GetMaxDight(h,len);

65. //printf("MaxDigit:%d\n",digit);

66. RRadixSort_MSD(h, 0, len-1, digit);

67. }

68. void RRadixSort_MSD_Reverse(int* h, int begin, int end, int digit)

69. {

70. if(h==NULL) return;

71. if(begin>=end) return;

72. if(digit<1) return;

73. int start[10];

74. int count[10]={0};

75. int *tmp=(int*)calloc(end-begin+1,sizeof(int));

76. for(int i=begin;i<=end;++i)

77. {

78. count[GetReminder(h[i],digit)]++;

79. }

80. memcpy(start,count,sizeof(start));

81. //求右邊界

82. for(int i=8;i>=0;--i)

83. {

84. start[i]+=start[i+1];

85. }

86. for(int i=end;i>=begin;--i)

87. {

88. int r=GetReminder(h[i],digit);

89. int index=start[r];

90. tmp[index-1]=h[i];

91. start[r]--;

92. }

94. memcpy(&h[begin],tmp,(end-begin+1)*sizeof(int));

95. for(int i=0;i<10;++i)

96. {

97. if(count[i]>1)

98. {

99. RRadixSort_MSD_Reverse(h, start[i], start[i]+count[i]-1, digit-1);

100. }

101. }

102. }

103. void RadixSort_MSD_Reverse(int* h, int len)

104. {

105. if(h==NULL) return;

106. if(len<=1) return;

107. int digit=GetMaxDight(h,len);

108. //printf("MaxDigit:%d\n",digit);

109. RRadixSort_MSD_Reverse(h, 0, len-1, digit);

110. }

十、主函數

1. void Swap(int& a, int& b)

2. {

3. int t=a;

4. a=b;

5. b=t;

6. return;

7. }

8. int main()

9. {

10. int A[10]={0};

11. srand((unsigned)time(NULL));

12. printf("before:\n");

13. for(int i=0;i<10;++i)

14. {

15. A[i]=rand()%100;

16. printf("%d ",A[i]);

17. }

18. printf("\n");

19. printf("after:\n");

20. //QuickSort(A,0,9);

21. //BubbleSort(A,sizeof(A)/sizeof(int));

22. //SelectionSort(A,sizeof(A)/sizeof(int));

23. //InsertSort(A,sizeof(A)/sizeof(int));

24. //MergeSort(A,sizeof(A)/sizeof(int));

25. //ShellSort(A,sizeof(A)/sizeof(int));

26. //HeapSort(A,sizeof(A)/sizeof(int));

27. //RadixSort_LSD(A,sizeof(A)/sizeof(int));

28. //RadixSort_MSD(A,sizeof(A)/sizeof(int));

29. //RadixSort_LSD_Reverse(A,sizeof(A)/sizeof(int));

30. RadixSort_MSD_Reverse(A,sizeof(A)/sizeof(int));

31. for(int i=0;i<sizeof(A)/sizeof(int);++i)

32. {

33. printf("%d ",A[i]);

34. }

35. printf("\n");

36. return 0;

37. }