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

冒泡排序

簡(jiǎn)介

冒泡排序是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換以升序或降序的方式慢慢浮到數(shù)列的頂端，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名冒泡排序。

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

思路原理

以順序?yàn)槔?/span>

1. 從第一個(gè)元素開始一個(gè)一個(gè)的比較相鄰的元素，如果第一個(gè)比第二個(gè)大即a[1]>a[2]，就彼此交換。
2. 從第一對(duì)到最后一對(duì)，對(duì)每一對(duì)相鄰元素做一樣的操作。此時(shí)在最后的元素應(yīng)該會(huì)是最大的數(shù)，我們也稱呼一遍這樣的操作為一趟冒泡排序。
3. 針對(duì)所有的元素重復(fù)以上的步驟，每一趟得到的最大值已放在最后，下一次操作則不需要將此最大值納入計(jì)算。
4. 持續(xù)對(duì)每次對(duì)越來越少的元素，重復(fù)上面的步驟。
5. 直到所有的數(shù)字都比較完成符合a[i]，即完成冒泡排序。

圖示過程

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

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

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

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

主要代碼實(shí)現(xiàn)

void?bubble_sort(int?a[],int?n)?{
????for(int?i=0;?i????????for(int?j=0;?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的兩個(gè)值，當(dāng)然你可以自定義swap函數(shù)，其模板代碼為：

template????????//模板類，可以讓參數(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;
}

選擇排序

簡(jiǎn)介

選擇排序是一種簡(jiǎn)單直觀的排序算法，它從待排序的數(shù)據(jù)元素中選出最小或最大的一個(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚』蜃畲笤兀缓蠓诺揭雅判虻男蛄械哪┪?。以此類推，直到全部待排序的?shù)據(jù)元素的個(gè)數(shù)為零。

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

過程介紹（以順序?yàn)槔?/span>

1. 首先設(shè)置兩個(gè)記錄i和j，i從數(shù)組第一個(gè)元素開始，j從(i+1)個(gè)元素開始。
2. 接著j遍歷整個(gè)數(shù)組，選出整個(gè)數(shù)組最小的值，并讓這個(gè)最小的值和i的位置交換。
3. i選中下一個(gè)元素(i++)，重復(fù)進(jìn)行每一趟選擇排序。
4. 持續(xù)上述步驟，使得i到達(dá)(n-1)處，即完成排序 。

圖示過程：

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

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

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

我們只需要進(jìn)行n-1趟排序即可，因?yàn)樽詈笫Ｏ碌囊粋€(gè)數(shù)據(jù)一定是整體數(shù)據(jù)中最大的數(shù)據(jù)。

代碼實(shí)現(xiàn)

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

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

插入排序

簡(jiǎn)介

插入排序是一種最簡(jiǎn)單的排序方法，對(duì)于少量元素的排序，它是一個(gè)有效的算法。

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

過程介紹

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

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

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

1. 每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。
2. 第一趟比較前兩個(gè)數(shù)，然后把第二個(gè)數(shù)按大小插入到有序表中；
3. 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描，把第三個(gè)數(shù)按大小插入到有序表中；
4. 依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程。

圖示過程

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

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

代碼實(shí)現(xiàn)

void?insert_sort(int?a[],int?n)?{
????int?i,j;
????//外層循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值
????for(i=1;?i????????if(a[i]????????????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;
????????}
????}
}

希爾排序

簡(jiǎn)介

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

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

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

過程介紹

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

過程如下：

1. 選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；
3. 每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。
4. 僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

圖示過程

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

主要代碼實(shí)現(xiàn)

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

堆排序

簡(jiǎn)介

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

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

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

什么是堆？

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

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

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

過程介紹

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

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

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

主要代碼實(shí)現(xiàn)

/*?Function:?交換交換根節(jié)點(diǎn)和數(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)?????????????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?????????????????BuildMaxHeap(heap,?len);
????????????}
????????}
????????if?((2*i+2)?????????????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?????????????????BuildMaxHeap(heap,?len);
????????????}
????????}
????}
}

歸并排序

簡(jiǎn)介

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

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

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

過程介紹

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

過程如下：

1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4. 重復(fù)步驟c直到某一指針超出序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

圖示過程

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

主要代碼實(shí)現(xiàn)

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

快速排序

簡(jiǎn)介

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

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

過程介紹

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

1. 在數(shù)組中選擇一個(gè)基準(zhǔn)點(diǎn)
2. 分別從數(shù)組的兩端掃描數(shù)組，設(shè)兩個(gè)指示標(biāo)志
3. 從后半部分開始，如果發(fā)現(xiàn)有元素比該基準(zhǔn)點(diǎn)的值小，就交換位置
4. 然后從前半部分開始掃描，發(fā)現(xiàn)有元素大于基準(zhǔn)點(diǎn)的值，繼續(xù)交換位置
5. 如此往復(fù)循環(huán)，然后把基準(zhǔn)點(diǎn)的值放到high這個(gè)位置,排序完成

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

圖示過程

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

主要代碼實(shí)現(xiàn)

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

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

計(jì)數(shù)排序

簡(jiǎn)介

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

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

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

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

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

過程介紹

1. 找出待排序的數(shù)組中最大和最小的元素
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

圖示過程

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

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

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

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

代碼實(shí)現(xiàn)

#include
#include
#include

void?CountSort(int?*arr,?int?len){
????if(arr?==?NULL)?return;
????int?max?=?arr[0],?min?=?arr[0];
????for(int?i?=?1;?i?????????if(arr[i]?>?max)????max?=?arr[i];
????????if(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???????? count[arr[i]?- min]++;//包含了自己！
????for(int?i?=?1;?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?????????arr[i]?=?psort[i];
????}

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


void?print_array(int?*arr,?int?len)
{
????for(int?i=0;?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;
}

桶式排序

簡(jiǎn)介

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

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

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

過程介紹

1. 根據(jù)待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請(qǐng)的桶個(gè)數(shù)；
2. 遍歷待排序集合，將每一個(gè)元素移動(dòng)到對(duì)應(yīng)的桶中；
3. 對(duì)每一個(gè)桶中元素進(jìn)行排序，并移動(dòng)到已排序集合中。

圖示過程

元素分布在桶中：

然后，元素在每個(gè)桶中排序：

代碼實(shí)現(xiàn)

#include
#include
#include
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?buckets(BUCKET_NUM,(ListNode*)(0));
????for(int?i=0;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????????????head?=?Merge(head,buckets.at(i));
????}
????for(int?i=0;i????????????arr[i]?=?head->mData;
????????????head?=?head->mNext;
????}
}

基數(shù)排序

簡(jiǎn)介

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

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

圖示過程

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

過程介紹

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

1. 我們先根據(jù)序列的個(gè)位數(shù)的數(shù)字來進(jìn)行分類，將其分到指定的桶中。
2. 分類后，我們?cè)趶母鱾€(gè)桶中，將這些數(shù)按照從編號(hào)0到編號(hào)9的順序依次將所有數(shù)取出來。
3. 得到的序列就是個(gè)位數(shù)上呈遞增趨勢(shì)的序列。
4. 按照上圖個(gè)位數(shù)排序：{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
5. 接下來對(duì)十位數(shù)、百位數(shù)也按照這種方法進(jìn)行排序，最后就能得到排序完成的序列。

主要代碼實(shí)現(xiàn)

public?class?RadixSort?{
????//?獲取x這個(gè)數(shù)的d位數(shù)上的數(shù)字
????//?比如獲取123的1位數(shù)，結(jié)果返回3
????public?int?getDigit(int?x,?int?d)?{
????????int?a[]?=?{1,?1,?10,?100};?//?本實(shí)例中的最大數(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];?//?存放各個(gè)桶的數(shù)據(jù)統(tǒng)計(jì)個(gè)數(shù)
??????int[]?bucket?=?new?int[end?-?begin?+?1];
??????//?按照從低位到高位的順序執(zhí)行排序過程
??????for?(int?d?=?1;?d?<=?digit;?d++)?{
??????????//?置空各個(gè)桶的數(shù)據(jù)統(tǒng)計(jì)
??????????for?(i?=?0;?i???????????????count[i]?=?0;
??????????}
??????????//?統(tǒng)計(jì)各個(gè)桶將要裝入的數(shù)據(jù)個(gè)數(shù)
??????????for?(i?=?begin;?i?<=?end;?i++)?{
??????????????j?=?getDigit(list[i],?d);
??????????????count[j]++;
??????????}
??????????//?count[i]表示第i個(gè)桶的右邊界索引
??????????for?(i?=?1;?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];
??????????????//?放入對(duì)應(yīng)的桶中，count[j]-1是第j個(gè)桶的右邊界索引
??????????????count[j]--;?//?對(duì)應(yīng)桶的裝入數(shù)據(jù)索引減一
??????????}
??????????//?將已分配好的桶中數(shù)據(jù)再倒出來，此時(shí)已是對(duì)應(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種排序算法對(duì)比，我們了解到了各種排序的原理及優(yōu)缺點(diǎn)，記住任何一種排序都不是十全十美的，因此在我們實(shí)際應(yīng)用中，最好的方式就是揚(yáng)長(zhǎng)避短。

有道無(wú)術(shù)，術(shù)可成；有術(shù)無(wú)道，止于術(shù)

歡迎大家關(guān)注Java之道公眾號(hào)

好文章，我在看??