面試官愛問的10大經(jīng)典排序算法，20+張圖來搞定

冒泡排序

簡介

冒泡排序是因為越小的元素會經(jīng)由交換以升序或降序的方式慢慢浮到數(shù)列的頂端，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名冒泡排序。

復(fù)雜度與穩(wěn)定性

思路原理

以順序為例

1. 從第一個元素開始一個一個的比較相鄰的元素，如果第一個比第二個大即a[1]>a[2]，就彼此交換。

2. 從第一對到最后一對，對每一對相鄰元素做一樣的操作。此時在最后的元素應(yīng)該會是最大的數(shù)，我們也稱呼一遍這樣的操作為一趟冒泡排序。

3. 針對所有的元素重復(fù)以上的步驟，每一趟得到的最大值已放在最后，下一次操作則不需要將此最大值納入計算。

4. 持續(xù)對每次對越來越少的元素，重復(fù)上面的步驟。

5. 直到所有的數(shù)字都比較完成符合a[i]<a[i+1]，即完成冒泡排序。

圖示過程

以數(shù)組數(shù)據(jù){ 70,50,30,20,10,70,40,60}為例：

如圖，每一次排序把一個最大的數(shù)被放在了最后，然后按照這個趨勢逐漸往前，直到按從小到大的順序依次排序。

到了第4輪的時候，整個數(shù)據(jù)已經(jīng)排序結(jié)束了，但此時程序仍然在進行。

直到第5，6，7輪程序才算真正的結(jié)束，這其實是一種浪費算力的表現(xiàn)。

主要代碼實現(xiàn)

void bubble_sort(int a[],int n) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n-i; j++) {
            if(a[j]>a[j+1]) {
                swap(a[j],a[j+1]);  //交換數(shù)據(jù)
            }
        }
    }
}

注意，由于C++的namespace std命名空間的使用，std自帶了交換函數(shù)swap(a,b)，可以直接使用，其功能是交換a與b的兩個值，當(dāng)然你可以自定義swap函數(shù)，其模板代碼為：

template<class T>        //模板類，可以讓參數(shù)為任意類型
void swap(T &a,T &b) {
    T c(a);
    a=b;
    b=c;
}

或者指定類型修改為整形，如：

void swap(int &a, int &b) { //指定類型
    int temp = a;
    a = b;
    b = temp;
}

選擇排序

簡介

選擇排序是一種簡單直觀的排序算法，它從待排序的數(shù)據(jù)元素中選出最小或最大的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小或最大元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。

復(fù)雜度與穩(wěn)定性

過程介紹（以順序為例）

1. 首先設(shè)置兩個記錄i和j，i從數(shù)組第一個元素開始，j從(i+1)個元素開始。

2. 接著j遍歷整個數(shù)組，選出整個數(shù)組最小的值，并讓這個最小的值和i的位置交換。

3. i選中下一個元素(i++)，重復(fù)進行每一趟選擇排序。

4. 持續(xù)上述步驟，使得i到達(n-1)處，即完成排序 。

圖示過程：

以數(shù)據(jù){2,10,9,4,8,1,6,5}為例

如圖所示，每次交換的數(shù)據(jù)使用紅顏色標記出，已經(jīng)排好序的數(shù)據(jù)使用藍底標注，

每一趟從待排序的數(shù)據(jù)元素中選出最小的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

我們只需要進行n-1趟排序即可，因為最后剩下的一個數(shù)據(jù)一定是整體數(shù)據(jù)中最大的數(shù)據(jù)。

代碼實現(xiàn)

void select_sort(int a[],int n){
    int temp;
    for(int i=0;i<n-1;i++){
        temp=i;      //利用一個中間變量temp來記錄需要交換元素的位置
        for(int j=i+1;j<n;j++){
            if(a[temp]>a[j]){   //選出待排數(shù)據(jù)中的最小值
                temp=j;  
            }
        }
        swap(a[i],a[temp]); //交換函數(shù)
    }
} 

相比冒泡排序的不斷交換，簡單選擇排序是等到合適的關(guān)鍵字出現(xiàn)后再進行交換，并且交換一次就可以達到一次冒泡的效果。

插入排序

簡介

插入排序是一種最簡單的排序方法，對于少量元素的排序，它是一個有效的算法。

復(fù)雜度與穩(wěn)定性

過程介紹

首先將一個記錄插入到已經(jīng)排好序的有序表中，從而一個新的、記錄數(shù)增1的有序表。

每一步將一個待排序的元素，按其排序碼的大小，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上去，直到元素全部插入為止。

可以選擇不同的方法在已經(jīng)排好序數(shù)據(jù)表中尋找插入位置。根據(jù)查找方法不同，有多種插入排序方法，下面要介紹的是直接插入排序。

1. 每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。

2. 第一趟比較前兩個數(shù)，然后把第二個數(shù)按大小插入到有序表中；

3. 第二趟把第三個數(shù)據(jù)與前兩個數(shù)從后向前掃描，把第三個數(shù)按大小插入到有序表中；

4. 依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。

圖示過程

以數(shù)組數(shù)據(jù){ 70,50,30,20,10,70,40,60}為例：

將紅色的數(shù)據(jù)依次插入組成一個逐漸有序的數(shù)組

代碼實現(xiàn)

void insert_sort(int a[],int n) {
    int i,j;
    //外層循環(huán)標識并決定待比較的數(shù)值
    for(i=1; i<n; i++) { //循環(huán)從第2個元素開始
        if(a[i]<a[i-1]) {
            int temp=a[i];
            //待比較數(shù)值確定其最終位置
            for(j=i-1; j>=0 && a[j]>temp; j--) {
                a[j+1]=a[j];
            }
            a[j+1]=temp;//此處就是a[j+1]=temp;
        }
    }
}

希爾排序

簡介

希爾排序又稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。

希爾排序是非穩(wěn)定排序算法，在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率極高，即可以達到線性排序的效率。

復(fù)雜度與穩(wěn)定性

過程介紹

先將整個待排序的記錄序列分組，對若干子序列分別進行直接插入排序，隨著增量逐漸減少即整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

過程如下：

1. 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列個數(shù) k，對序列進行 k 趟排序；

3. 每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。

4. 僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

圖示過程

可以看見，相比直接插入排序由于可以每趟進行分段操作，故整體效率體現(xiàn)較高。

主要代碼實現(xiàn)

void shellSort(int arr[], int n) {
    int i, j, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = 0; i < gap; i++) {
            for (j = i + gap; j < n; j += gap) {
                for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) {
                    swap(arr[k-gap], arr[k]);
                }
            }
        }
    }
}

堆排序

簡介

堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是一個近似完全二叉樹的結(jié)構(gòu)。

同時堆滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于或大于它的父節(jié)點。

復(fù)雜度與穩(wěn)定性

什么是堆？

由于堆排序比較特殊，我們先了解一下堆是什么。

堆是一種非線性的數(shù)據(jù)結(jié)構(gòu)，其實就是利用完全二叉樹的結(jié)構(gòu)來維護的一維數(shù)組，利用這種結(jié)構(gòu)可以快速訪問到需要的值，堆可以分為大頂堆和小頂堆。

• 大頂堆：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值

• 小頂堆：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值

過程介紹

首先把待排序的元素按照大小在二叉樹位置上排列，且要滿足堆的特性，如果根節(jié)點存放的是最大的數(shù)，則叫做大根堆，反之就叫做小根堆了。

根據(jù)這個特性就可以把根節(jié)點拿出來，然后再堆化下，即用父節(jié)點和他的孩子節(jié)點進行比較，取最大的孩子節(jié)點和其進行交換，再把根節(jié)點拿出來，一直循環(huán)到最后一個節(jié)點，就排序好了。

由于堆的實現(xiàn)圖解需要很長篇幅，故這里不畫圖，肖遙會單獨出一篇堆的圖解，感謝關(guān)注。其代碼實現(xiàn)如下。

主要代碼實現(xiàn)

/* Function: 交換交換根節(jié)點和數(shù)組末尾元素的值*/
void Swap(int *heap, int len) {
    int temp;
  
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}
  
/* Function: 構(gòu)建大頂堆 */
void BuildMaxHeap(int *heap, int len) {
    int i,temp;
    for (i = len/2-1; i >= 0; i--) {
        if ((2*i+1) < len && heap[i] < heap[2*i+1]) {  /* 根節(jié)點大于左子樹 */
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 檢查交換后的左子樹是否滿足大頂堆性質(zhì) 如果不滿足 則重新調(diào)整子樹結(jié)構(gòu) */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2]) {  /* 根節(jié)點大于右子樹 */
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 檢查交換后的右子樹是否滿足大頂堆性質(zhì) 如果不滿足 則重新調(diào)整子樹結(jié)構(gòu) */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
    }
}

歸并排序

簡介

歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法的一個非常典型的應(yīng)用，其核心思想是將兩個有序的數(shù)列合并成一個大的有序的序列。

復(fù)雜度與穩(wěn)定性

注：歸并排序需要創(chuàng)建一個與原數(shù)組相同長度的數(shù)組來輔助排序

過程介紹

首先將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。

過程如下：

1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列

2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置

3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4. 重復(fù)步驟c直到某一指針超出序列尾

5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

圖示過程

第一次排序?qū)?shù)據(jù)分為“兩個”一組，組內(nèi)順序，其次再逐個的將各組進行整合，最終完成歸并排序

主要代碼實現(xiàn)

void merge(int arr[],int l,int mid,int r) {
    int aux[r-l+1];//開辟一個新的數(shù)組，將原數(shù)組映射進去
    for(int m=l; m<=r; m++) {
        aux[m-l]=arr[m];
    }
  
    int i=l,j=mid+1;//i和j分別指向兩個子數(shù)組開頭部分
  
    for(int k=l; k<=r; k++) {
        if(i>mid) {
            arr[k]=aux[j-l];
            j++;
        } else if(j>r) {
            arr[k]=aux[i-l];
            i++;
        } else if(aux[i-l]<aux[j-l]) {
            arr[k]=aux[i-l];
            i++;
        } else {
            arr[k]=aux[j-l];
            j++;
        }
    }
}
  
void merge_sort(int arr[],int n) {
    for(int sz=1; sz<=n; sz+=sz) {
        for(int i=0; i+sz<n; i+=sz+sz) { //i+sz防止越界
            //對局部：arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進行排序
            merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));    //min函數(shù)防止越界
        }
    }
  
}
  

快速排序

簡介

快速排序在1960年提出，是考察次數(shù)最多的排序，無論是在大學(xué)專業(yè)課的期末考試，還是在公司的面試測試題目中，快速排序都極大的被使用，在實際中快速排序也極大的被使用。

復(fù)雜度與穩(wěn)定性

過程介紹

通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

1. 在數(shù)組中選擇一個基準點

2. 分別從數(shù)組的兩端掃描數(shù)組，設(shè)兩個指示標志

3. 從后半部分開始，如果發(fā)現(xiàn)有元素比該基準點的值小，就交換位置

4. 然后從前半部分開始掃描，發(fā)現(xiàn)有元素大于基準點的值，繼續(xù)交換位置

5. 如此往復(fù)循環(huán)，然后把基準點的值放到high這個位置,排序完成

以后采用遞歸的方式分別對前半部分和后半部分排序，當(dāng)前半部分和后半部分均有序時該數(shù)組就自然有序了。

圖示過程

可以看出，在第四趟時已經(jīng)達到順序，但是仍然還是會繼續(xù)計算幾趟直到完成全部運算

主要代碼實現(xiàn)

void qucik_sort(int a[],int low,int high) {
  int i,j,temp;
  i=low;
  j=high;
  if(low<high) {
    temp=a[low];    //設(shè)置樞軸
    while(i!=j) {
      while(j>i&&a[j]>=temp) {
        --j;
      }
      if(i<j) {
        a[i]=a[j];
        ++i;
      }

      while(i<j&&a[i]<temp) {
        ++i;
      }
      if(i<j) {
        a[j]=a[i];
        --j;
      }
    }
    a[i]=temp;
    qucik_sort(a,low,i-1);
    qucik_sort(a,i+1,high);
  }
}

計數(shù)排序

簡介

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

計數(shù)排序算法不是基于元素比較，而是利用數(shù)組下標來確定元素的正確位置。

它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時，它的復(fù)雜度為Ο(n+k)，快于任何比較排序算法。

當(dāng)然這是一種犧牲空間換取時間的做法，而且當(dāng)O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序。

復(fù)雜度與穩(wěn)定性

過程介紹

1. 找出待排序的數(shù)組中最大和最小的元素

2. 統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項

3. 對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）

4. 反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

圖示過程

如下圖，A為待排序的數(shù)組，C記錄A中各個值的數(shù)目。

將C[i]轉(zhuǎn)換為值小于等于i的元素個數(shù)。

為數(shù)組A從后向前的每個元素找到對應(yīng)的B中的位置，每次從A中復(fù)制一個元素到B中，C中相應(yīng)的計數(shù)減一。

當(dāng)A中的元素都復(fù)制到B中后，B就是排序好的結(jié)果，如圖所示。

代碼實現(xiàn)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void CountSort(int *arr, int len){
    if(arr == NULL) return;
    int max = arr[0], min = arr[0];
    for(int i = 1; i < len; i++){
        if(arr[i] > max)    max = arr[i];
        if(arr[i] < min)    min = arr[i];
    }
    int size = max - min + 1;
    int *count =(int*)malloc(sizeof(int)*size);
    memset(count, 0, sizeof(int)*size);

    for(int i = 0; i < len; i++)
        count[arr[i] - min]++;//包含了自己！
    for(int i = 1; i < size; i++)
        count[i] += count[i - 1];

    int* psort =(int*)malloc(sizeof(int)*len);
    memset(psort, 0, sizeof(int)*len);

    for(int i = len - 1; i >= 0; i--){
        count[arr[i] - min]--;//要先把自己減去
        psort[count[arr[i] - min]] = arr[i];
    }

    for(int i = 0; i < len; i++){
        arr[i] = psort[i];
    }

    free(count);
    free(psort);
    count = NULL;
    psort = NULL;
}


void print_array(int *arr, int len)
{
    for(int i=0; i<len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main()
{
    int arr[8] = {2, 5, 3, 0, 2, 3, 0, 3};
    CountSort(arr, 8);
    print_array(arr, 8);

    return 0;
}

桶式排序

簡介

桶排序也稱箱排序，原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。

桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。

復(fù)雜度與穩(wěn)定性

過程介紹

1. 根據(jù)待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請的桶個數(shù)；

2. 遍歷待排序集合，將每一個元素移動到對應(yīng)的桶中；

3. 對每一個桶中元素進行排序，并移動到已排序集合中。

圖示過程

元素分布在桶中：

然后，元素在每個桶中排序：

代碼實現(xiàn)

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;

struct ListNode{
    explicit ListNode(int i=0):mData(i),mNext(NULL){}
    ListNode* mNext;
    int mData;
};

ListNode* insert(ListNode* head,int val){
    ListNode dummyNode;
    ListNode *newNode = new ListNode(val);
    ListNode *pre,*curr;
    dummyNode.mNext = head;
    pre = &dummyNode;
    curr = head;
    while(NULL!=curr && curr->mData<=val){
            pre = curr;
            curr = curr->mNext;
    }
    newNode->mNext = curr;
    pre->mNext = newNode;
    return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
    ListNode dummyNode;
    ListNode *dummy = &dummyNode;
    while(NULL!=head1 && NULL!=head2){
            if(head1->mData <= head2->mData){
                    dummy->mNext = head1;
                    head1 = head1->mNext;
            }else{
                    dummy->mNext = head2;
                    head2 = head2->mNext;
            }
            dummy = dummy->mNext;
    }
    if(NULL!=head1) dummy->mNext = head1;
    if(NULL!=head2) dummy->mNext = head2;

    return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
    vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
    for(int i=0;i<n;++i){
            int index = arr[i]/BUCKET_NUM;
            ListNode *head = buckets.at(index);
            buckets.at(index) = insert(head,arr[i]);
    }
    ListNode *head = buckets.at(0);
    for(int i=1;i<BUCKET_NUM;++i){
            head = Merge(head,buckets.at(i));
    }
    for(int i=0;i<n;++i){
            arr[i] = head->mData;
            head = head->mNext;
    }
}

基數(shù)排序

簡介

基數(shù)排序是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，在某些時候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

復(fù)雜度與穩(wěn)定性

圖示過程

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

過程介紹

任何一個阿拉伯?dāng)?shù)，它的各個位數(shù)上的基數(shù)都是以0~9來表示的。所以我們不妨把0~9視為10個桶。

1. 我們先根據(jù)序列的個位數(shù)的數(shù)字來進行分類，將其分到指定的桶中。

2. 分類后，我們在從各個桶中，將這些數(shù)按照從編號0到編號9的順序依次將所有數(shù)取出來。

3. 得到的序列就是個位數(shù)上呈遞增趨勢的序列。

4. 按照上圖個位數(shù)排序：{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

5. 接下來對十位數(shù)、百位數(shù)也按照這種方法進行排序，最后就能得到排序完成的序列。

主要代碼實現(xiàn)

public class RadixSort {
    // 獲取x這個數(shù)的d位數(shù)上的數(shù)字
    // 比如獲取123的1位數(shù)，結(jié)果返回3
    public int getDigit(int x, int d) {
        int a[] = {1, 1, 10, 100}; // 本實例中的最大數(shù)是百位數(shù)，所以只要到100就可以了
        return ((x / a[d]) % 10);
    }

  public void radixSort(int[] list, int begin, int end, int digit) {
      final int radix = 10; // 基數(shù)
      int i = 0, j = 0;
      int[] count = new int[radix]; // 存放各個桶的數(shù)據(jù)統(tǒng)計個數(shù)
      int[] bucket = new int[end - begin + 1];
      // 按照從低位到高位的順序執(zhí)行排序過程
      for (int d = 1; d <= digit; d++) {
          // 置空各個桶的數(shù)據(jù)統(tǒng)計
          for (i = 0; i < radix; i++) {
              count[i] = 0;
          }
          // 統(tǒng)計各個桶將要裝入的數(shù)據(jù)個數(shù)
          for (i = begin; i <= end; i++) {
              j = getDigit(list[i], d);
              count[j]++;
          }
          // count[i]表示第i個桶的右邊界索引
          for (i = 1; i < radix; i++) {
              count[i] = count[i] + count[i - 1];
          }
          // 將數(shù)據(jù)依次裝入桶中
          // 這里要從右向左掃描，保證排序穩(wěn)定性
          for (i = end; i >= begin; i--) {
              j = getDigit(list[i], d);
              // 求出關(guān)鍵碼的第k位的數(shù)字， 例如：576的第3位是5
              bucket[count[j] - 1] = list[i];
              // 放入對應(yīng)的桶中，count[j]-1是第j個桶的右邊界索引
              count[j]--; // 對應(yīng)桶的裝入數(shù)據(jù)索引減一
          }
          // 將已分配好的桶中數(shù)據(jù)再倒出來，此時已是對應(yīng)當(dāng)前位數(shù)有序的表
          for (i = begin, j = 0; i <= end; i++, j++) {
              list[i] = bucket[j];
          }
      }
  }

  public int[] sort(int[] list) {
      radixSort(list, 0, list.length - 1, 3);
      return list;
  }

  // 打印完整序列
  public void printAll(int[] list) {
      for (int value : list) {
          System.out.print(value + "\t");
      }
      System.out.println();
  }

  public static void main(String[] args) {
      int[] array = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100};
      RadixSort radix = new RadixSort();
      System.out.print("排序前:\t\t");
      radix.printAll(array);
      radix.sort(array);
      System.out.print("排序后:\t\t");
      radix.printAll(array);
  }
}

總結(jié)

10種排序算法對比，我們了解到了各種排序的原理及優(yōu)缺點，記住任何一種排序都不是十全十美的，因此在我們實際應(yīng)用中，最好的方式就是揚長避短。

今天排序基礎(chǔ)就講到這里，下一期，我們再見！