原文：http://blog.csdn.net/t12x3456/article/details/7430700

各種排序算法：冒擇路(入)兮(稀)快歸堆，桶式排序，基數(shù)排序

冒泡排序，選擇排序，插入排序，稀爾排序，快速排序，歸并排序，堆排序，桶式排序，基數(shù)排序

一、冒泡排序(BubbleSort)
1. 基本思想：
　　兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。
2. 排序過(guò)程：
　　設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。
【示例】：
49 13 13 13 13 13 13 13?
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

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

/**?? *?冒泡排序：執(zhí)行完一次內(nèi)for循環(huán)后，最小的一個(gè)數(shù)放到了數(shù)組的最前面（跟那一個(gè)排序算法*?不一樣）。相鄰位置之間交換?? */????public?class?BubbleSort?{???????/**????*?排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序????*?@param?array?待排序的數(shù)組????*?@param?from?從哪里開始排序????*?@param?end?排到哪里????*?@param?c?比較器????*/??????public?void?bubble(Integer[]?array,?int?from,?int?end)?{???????//需array.length?-?1輪比較???????for?(int?k?=?1;?k?<?end?-?from?+?1;?k++)?{???????//每輪循環(huán)中從最后一個(gè)元素開始向前起泡，直到i=k止，即i等于輪次止???????for?(int?i?=?end?-?from;?i?>=?k;?i--)?{???????//按照一種規(guī)則（后面元素不能小于前面元素）排序???????if?((array[i].compareTo(array[i?-?1]))?<?0)?{???????//如果后面元素小于了（當(dāng)然是大于還是小于要看比較器實(shí)現(xiàn)了）前面的元素，則前后交換???????swap(array,?i,?i?-?1);???????}???????}???????}???????}???????/**????*?交換數(shù)組中的兩個(gè)元素的位置????*?@param?array?待交換的數(shù)組????*?@param?i?第一個(gè)元素????*?@param?j?第二個(gè)元素????*/??????public?void?swap(Integer[]?array,?int?i,?int?j)?{???????if?(i?!=?j)?{//只有不是同一位置時(shí)才需交換???????Integer?tmp?=?array[i];???????array[i]?=?array[j];???????array[j]?=?tmp;???????}???????}???????/**?????*?測(cè)試?????*?@param?args?????*/??????public?static?void?main(String[]?args)?{???????Integer[]?intgArr?=?{?7,?2,?4,?3,?12,?1,?9,?6,?8,?5,?11,?10?};???????BubbleSort?bubblesort?=?new?BubbleSort();???????bubblesort.bubble(intgArr,0,intgArr.length-1);????for(Integer?intObj:intgArr){????System.out.print(intObj?+?"?");????}????}??????? }

另外一種實(shí)現(xiàn)方式：

/**? 冒泡排序：執(zhí)行完一次內(nèi)for循環(huán)后，最大的一個(gè)數(shù)放到了數(shù)組的最后面。相鄰位置之間交換? */?? public?class?BubbleSort2{??public?static?void?main(String[]?args){??int[]?a?=?{3,5,9,4,7,8,6,1,2};??BubbleSort2?bubble?=?new?BubbleSort2();??bubble.bubble(a);??for(int?num:a){??System.out.print(num?+?"?");??}??}??public?void?bubble(int[]?a){??for(int?i=a.length-1;i>0;i--){??for(int?j=0;j<i;j++){??if(new?Integer(a[j]).compareTo(new?Integer(a[j+1]))>0){??swap(a,j,j+1);??}??}??}??}??public?void?swap(int[]?a,int?x,int?y){??int?temp;??temp=a[x];??a[x]=a[y];??a[y]=temp;??}?? }

?

二、選擇排序
1. 基本思想：
　　每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
2. 排序過(guò)程：
【示例】：
? 初始關(guān)鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序結(jié)果 13 27 38 49 49 76 76 97

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

/**?? *?簡(jiǎn)單選擇排序：執(zhí)行完一次內(nèi)for循環(huán)后最小的一個(gè)數(shù)放在了數(shù)組的最前面。?? */???? public?class?SelectSort?{???????/**????*?排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序????*?@param?array?待排序的數(shù)組????*?@param?from?從哪里開始排序????*?@param?end?排到哪里????*?@param?c?比較器????*/??????public?void?select(Integer[]?array)?{???????int?minIndex;//最小索引???????/*????*?循環(huán)整個(gè)數(shù)組（其實(shí)這里的上界為?array.length?-?1?即可，因?yàn)楫?dāng)?i=?array.length-1????*?時(shí)，最后一個(gè)元素就已是最大的了，如果為array.length時(shí)，內(nèi)層循環(huán)將不再循環(huán)），每輪假設(shè)????*?第一個(gè)元素為最小元素，如果從第一元素后能選出比第一個(gè)元素更小元素，則讓讓最小元素與第一????*?個(gè)元素交換?????*/??????for?(int?i=0;?i<array.length;?i++)?{???????minIndex?=?i;//假設(shè)每輪第一個(gè)元素為最小元素???????//從假設(shè)的最小元素的下一元素開始循環(huán)???????for?(int?j=i+1;j<array.length;?j++)?{???????//如果發(fā)現(xiàn)有比當(dāng)前array[smallIndex]更小元素，則記下該元素的索引于smallIndex中???????if?((array[j].compareTo(array[minIndex]))?<?0)?{???????minIndex?=?j;???????}???????}???????//先前只是記錄最小元素索引，當(dāng)最小元素索引確定后，再與每輪的第一個(gè)元素交換???????swap(array,?i,?minIndex);???????}???????}???????public?static?void?swap(Integer[]?intgArr,int?x,int?y){????//Integer?temp;?//這個(gè)也行????int?temp;????temp=intgArr[x];????intgArr[x]=intgArr[y];????intgArr[y]=temp;????}????/**????*?測(cè)試????*?@param?args????*/??????public?static?void?main(String[]?args)?{???????Integer[]?intgArr?=?{?5,?9,?1,?4,?2,?6,?3,?8,?0,?7?};???????SelectSort?insertSort?=?new?SelectSort();????insertSort.select(intgArr);????for(Integer?intObj:intgArr){????System.out.print(intObj?+?"?");????}??????}??????? }

三、插入排序(Insertion Sort)
1. 基本思想：
? 每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。
2. 排序過(guò)程：　?
【示例】：
[初始關(guān)鍵字] [49] 38 65 97 76 13 27 49
??? J=2(38) [38 49] 65 97 76 13 27 49
??? J=3(65) [38 49 65] 97 76 13 27 49
??? J=4(97) [38 49 65 97] 76 13 27 49
??? J=5(76) [38 49 65 76 97] 13 27 49
??? J=6(13) [13 38 49 65 76 97] 27 49
??? J=7(27) [13 27 38 49 65 76 97] 49
??? J=8(49) [13 27 38 49 49 65 76 97]?

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

/** *?直接插入排序： *?注意所有排序都是從小到大排。 */?public?class?InsertSort?{????/**?*?排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序?*?@param?array?待排序的數(shù)組?*?@param?from?從哪里開始排序?*?@param?end?排到哪里?*?@param?c?比較器?*/???public?void?insert(Integer[]?array,int?from,?int?end)?{????/*?*?第一層循環(huán)：對(duì)待插入（排序）的元素進(jìn)行循環(huán)?*?從待排序數(shù)組斷的第二個(gè)元素開始循環(huán)，到最后一個(gè)元素（包括）止?*/???for?(int?i=from+1;?i<=end;?i++)?{????/*?*?第二層循環(huán)：對(duì)有序數(shù)組進(jìn)行循環(huán)，且從有序數(shù)組最第一個(gè)元素開始向后循環(huán)?*?找到第一個(gè)大于待插入的元素?*?有序數(shù)組初始元素只有一個(gè)，且為源數(shù)組的第一個(gè)元素，一個(gè)元素?cái)?shù)組總是有序的?*/???for?(int?j?=0;?j?<?i;?j++)?{????Integer?insertedElem?=?array[i];//待插入到有序數(shù)組的元素???//從有序數(shù)組中最一個(gè)元素開始查找第一個(gè)大于待插入的元素???if?((array[j].compareTo(insertedElem))?>0)?{????//找到插入點(diǎn)后，從插入點(diǎn)開始向后所有元素后移一位???move(array,?j,?i?-?1);????//將待排序元素插入到有序數(shù)組中???array[j]?=?insertedElem;????break;????}????}????}?//=======以下是java.util.Arrays的插入排序算法的實(shí)現(xiàn)????/*?*?該算法看起來(lái)比較簡(jiǎn)潔一j點(diǎn)，有點(diǎn)像冒泡算法。? *?將數(shù)組邏輯上分成前后兩個(gè)集合，前面的集合是已經(jīng)排序好序的元素，而后面集合為待排序的*?集合，每次內(nèi)層循從后面集合中拿出一個(gè)元素，通過(guò)冒泡的形式，從前面集合最后一個(gè)元素開?*?始往前比較，如果發(fā)現(xiàn)前面元素大于后面元素，則交換，否則循環(huán)退出?*??*?總感覺(jué)這種算術(shù)有點(diǎn)怪怪，既然是插入排序，應(yīng)該是先找到插入點(diǎn)，而后再將待排序的元素插?*?入到的插入點(diǎn)上，那么其他元素就必然向后移，感覺(jué)算法與排序名稱不匹，但返過(guò)來(lái)與上面實(shí)?*?現(xiàn)比，其實(shí)是一樣的，只是上面先找插入點(diǎn)，待找到后一次性將大的元素向后移，而該算法卻?*?是走一步看一步，一步一步將待排序元素往前移?*/???/*?for?(int?i?=?from;?i?<=?end;?i++)?{?for?(int?j?=?i;?j?>?from?&&?c.compare(array[j?-?1],?array[j])?>?0;?j--)?{?swap(array,?j,?j?-?1);?}?}?*/???}????/**?*?數(shù)組元素后移?*?@param?array?待移動(dòng)的數(shù)組?*?@param?startIndex?從哪個(gè)開始移?*?@param?endIndex?到哪個(gè)元素止?*/???public?void?move(Integer[]?array,int?startIndex,?int?endIndex)?{????for?(int?i?=?endIndex;?i?>=?startIndex;?i--)?{????array[i+1]?=?array[i];????}????}????/**?*?測(cè)試?*?@param?args?*/???public?staticvoid?main(String[]?args)?{????Integer[]?intgArr?=?{?5,?9,?1,?4,?2,?6,?3,?8,?0,?7?};????InsertSort?insertSort?=?new?InsertSort();????insertSort.insert(intgArr,0,intgArr.length-1);?for(Integer?intObj:intgArr){?System.out.print(intObj?+?"?");?}?}???? }

四、稀爾排序

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

/**?? *?插入排序----希爾排序：我們選擇步長(zhǎng)為：15,7,3,1?? *?我們選擇步長(zhǎng)公式為：2^k-1,2^(k-1)-1,……,15,7,3,1?????(2^4-1,2^3-1,2^2-1,2^1-1)?? *?注意所有排序都是從小到大排。?? */???? public?class?ShellSort?{???????/**????*?排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序????*?@param?array?待排序的數(shù)組????*?@param?from?從哪里開始排序????*?@param?end?排到哪里????*?@param?c?比較器????*/??????public?void?sort(Integer[]?array,?int?from,?int?end)?{???????//初始步長(zhǎng)，實(shí)質(zhì)為每輪的分組數(shù)???????int?step?=?initialStep(end?-?from?+?1);???????//第一層循環(huán)是對(duì)排序輪次進(jìn)行循環(huán)。(step?+?1)?/?2?-?1?為下一輪步長(zhǎng)值???????for?(;?step?>=?1;?step?=?(step?+?1)?/?2?-?1)?{???????//對(duì)每輪里的每個(gè)分組進(jìn)行循環(huán)???????for?(int?groupIndex?=?0;?groupIndex?<?step;?groupIndex++)?{???????//對(duì)每組進(jìn)行直接插入排序???????insertSort(array,?groupIndex,?step,?end);???????}???????}???????}???????/**????*?直接插入排序?qū)崿F(xiàn)????*?@param?array?待排序數(shù)組????*?@param?groupIndex?對(duì)每輪的哪一組進(jìn)行排序????*?@param?step?步長(zhǎng)????*?@param?end?整個(gè)數(shù)組要排哪個(gè)元素止????*?@param?c?比較器????*/??????public?void?insertSort(Integer[]?array,?int?groupIndex,?int?step,?int?end)?{???????int?startIndex?=?groupIndex;//從哪里開始排序???????int?endIndex?=?startIndex;//排到哪里???????/*????*?排到哪里需要計(jì)算得到，從開始排序元素開始，以step步長(zhǎng)，可求得下元素是否在數(shù)組范圍內(nèi)，????*?如果在數(shù)組范圍內(nèi)，則繼續(xù)循環(huán)，直到索引超現(xiàn)數(shù)組范圍????*/??????while?((endIndex?+?step)?<=?end)?{???????endIndex?+=?step;???????}???????//?i為每小組里的第二個(gè)元素開始???????for?(int?i?=?groupIndex?+?step;?i?<=?end;?i?+=?step)?{???????for?(int?j?=?groupIndex;?j?<?i;?j?+=?step)?{???????Integer?insertedElem?=?array[i];???????//從有序數(shù)組中最一個(gè)元素開始查找第一個(gè)大于待插入的元素???????if?((array[j].compareTo(insertedElem))?>=?0)?{???????//找到插入點(diǎn)后，從插入點(diǎn)開始向后所有元素后移一位???????move(array,?j,?i?-?step,?step);???????array[j]?=?insertedElem;???????break;???????}???????}???????}???????}???????/**????*?根據(jù)數(shù)組長(zhǎng)度求初始步長(zhǎng)????*?????*?我們選擇步長(zhǎng)的公式為：2^k-1,2^(k-1)-1,...,15,7,3,1?，其中2^k?減一即為該步長(zhǎng)序列，k????*?為排序輪次????*?????*?初始步長(zhǎng)：step?=?2^k-1?????*?初始步長(zhǎng)約束條件：step?<?len?-?1?初始步長(zhǎng)的值要小于數(shù)組長(zhǎng)度還要減一的值（因????*?為第一輪分組時(shí)盡量不要分為一組，除非數(shù)組本身的長(zhǎng)度就小于等于4）????*?????*?由上面兩個(gè)關(guān)系試可以得知：2^k?-?1?<?len?-?1?關(guān)系式，其中k為輪次，如果把?2^k?表?達(dá)式????*?轉(zhuǎn)換成?step?表達(dá)式，則?2^k-1?可使用?(step?+?1)*2-1?替換（因?yàn)?step+1?相當(dāng)于第k-1????*?輪的步長(zhǎng)，所以在?step+1?基礎(chǔ)上乘以?2?就相當(dāng)于?2^k?了），即步長(zhǎng)與數(shù)組長(zhǎng)度的關(guān)系不等式為????*?(step?+?1)*2?-?1?<?len?-1????*?????*?@param?len?數(shù)組長(zhǎng)度????*?@return????*/??????public?static?int?initialStep(int?len)?{???????/*????*?初始值設(shè)置為步長(zhǎng)公式中的最小步長(zhǎng)，從最小步長(zhǎng)推導(dǎo)出最長(zhǎng)初始步長(zhǎng)值，即按照以下公式來(lái)推:????*?1,3,7,15,...,2^(k-1)-1,2^k-1????*?如果數(shù)組長(zhǎng)度小于等于4時(shí)，步長(zhǎng)為1，即長(zhǎng)度小于等于4的數(shù)組不用分組，此時(shí)直接退化為直接插入排序????*/??????int?step?=?1;???????//試探下一個(gè)步長(zhǎng)是否滿足條件，如果滿足條件，則步長(zhǎng)置為下一步長(zhǎng)???????while?((step?+?1)?*?2?-?1?<?len?-?1)?{???????step?=?(step?+?1)?*?2?-?1;???????}???????System.out.println("初始步長(zhǎng)?:?"?+?step);???????return?step;???????}???????/**????*?以指定的步長(zhǎng)將數(shù)組元素后移，步長(zhǎng)指定每個(gè)元素間的間隔????*?@param?array?待排序數(shù)組????*?@param?startIndex?從哪里開始移????*?@param?endIndex?到哪個(gè)元素止????*?@param?step?步長(zhǎng)????*/??????protected?final?void?move(Integer[]?array,?int?startIndex,?int?endIndex,?int?step)??{???????for?(int?i?=?endIndex;?i?>=?startIndex;?i?-=?step)?{???????array[i?+?step]?=?array[i];???????}???????}???????/**????*?測(cè)試????*?@param?args????*/??????public?static?void?main(String[]?args)?{???????Integer[]?intgArr?=?{?5,?9,?1,?4,?8,?2,?6,?3,?7,?0?};???????ShellSort?shellSort?=?new?ShellSort();???????shellSort.sort(intgArr,0,intgArr.length-1);????for(Integer?intObj:intgArr){????System.out.print(intObj?+?"?");????}????}??????? }

五、快速排序（Quick Sort）

1. 基本思想：

　在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?/p>

2. 排序過(guò)程：

【示例】：

初始關(guān)鍵字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］?
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序結(jié)果 13 27 38 49 49 65 76 97?
各趟排序之后的狀態(tài)

java代碼實(shí)現(xiàn)： ?

/**?? *?快速排序：?? */????public?class?QuickSort?{???????/**????*?排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序????*?@param?array?待排序的數(shù)組????*?@param?from?從哪里開始排序????*?@param?end?排到哪里????*?@param?c?比較器????*/??????//定義了一個(gè)這樣的公有方法sort，在這個(gè)方法體里面執(zhí)行私有方法quckSort（這種方式值得借鑒）。????public?void?sort(Integer[]?array,?int?from,?int?end)?{???????quickSort(array,?from,?end);???????}???????/**????*?遞歸快速排序?qū)崿F(xiàn)????*?@param?array?待排序數(shù)組????*?@param?low?低指針????*?@param?high?高指針????*?@param?c?比較器????*/??????private?void?quickSort(Integer[]?array,?int?low,?int?high)?{???????/*????*?如果分區(qū)中的低指針小于高指針時(shí)循環(huán)；如果low=higth說(shuō)明數(shù)組只有一個(gè)元素，無(wú)需再處理；????*?如果low?>?higth，則說(shuō)明上次樞紐元素的位置pivot就是low或者是higth，此種情況????*?下分區(qū)不存，也不需處理????*/??????if?(low?<?high)?{???????//對(duì)分區(qū)進(jìn)行排序整理???????//int?pivot?=?partition1(array,?low,?high);????int?pivot?=?partition2(array,?low,?high);???????//int?pivot?=?partition3(array,?low,?high);??????????/*????*?以pivot為邊界，把數(shù)組分成三部分[low,?pivot?-?1]、[pivot]、[pivot?+?1,?high]????*?其中[pivot]為樞紐元素，不需處理，再對(duì)[low,?pivot?-?1]與[pivot?+?1,?high]????*?各自進(jìn)行分區(qū)排序整理與進(jìn)一步分區(qū)????*/??????quickSort(array,?low,?pivot?-?1);???????quickSort(array,?pivot?+?1,?high);???????}???????}???????/**????*?實(shí)現(xiàn)一????*?????*?@param?array?待排序數(shù)組????*?@param?low?低指針????*?@param?high?高指針????*?@param?c?比較器????*?@return?int?調(diào)整后中樞位置????*/??????private?int?partition1(Integer[]?array,?int?low,?int?high)?{???????Integer?pivotElem?=?array[low];//以第一個(gè)元素為中樞元素???????//從前向后依次指向比中樞元素小的元素，剛開始時(shí)指向中樞，也是小于與大小中樞的元素的分界點(diǎn)???????int?border?=?low;???????/*????*?在中樞元素后面的元素中查找小于中樞元素的所有元素，并依次從第二個(gè)位置從前往后存放????*?注，這里最好使用i來(lái)移動(dòng)，如果直接移動(dòng)low的話，最后不知道數(shù)組的邊界了，但后面需要????*?知道數(shù)組的邊界????*/??????for?(int?i?=?low?+?1;?i?<=?high;?i++)?{???????//如果找到一個(gè)比中樞元素小的元素???????if?((array[i].compareTo(pivotElem))?<?0)?{???????swap(array,?++border,?i);//border前移，表示有小于中樞元素的元素???????}???????}???????/*????*?如果border沒(méi)有移動(dòng)時(shí)說(shuō)明說(shuō)明后面的元素都比中樞元素要大，border與low相等，此時(shí)是????*?同一位置交換，是否交換都沒(méi)關(guān)系；當(dāng)border移到了high時(shí)說(shuō)明所有元素都小于中樞元素，此????*?時(shí)將中樞元素與最后一個(gè)元素交換即可，即low與high進(jìn)行交換，大的中樞元素移到了?序列最????*?后；如果?low?<minIndex<?high，表?明中樞后面的元素前部分小于中樞元素，而后部分大于????*?中樞元素，此時(shí)中樞元素與前部分?jǐn)?shù)組中最后一個(gè)小于它的元素交換位置，使得中樞元素放置在????*?正確的位置????*/??????swap(array,?border,?low);???????return?border;???????}???????/**????*?實(shí)現(xiàn)二????*?????*?@param?array?待排序數(shù)組????*?@param?low?待排序區(qū)低指針????*?@param?high?待排序區(qū)高指針????*?@param?c?比較器????*?@return?int?調(diào)整后中樞位置????*/??????private?int?partition2(Integer[]?array,?int?low,?int?high)?{???????int?pivot?=?low;//中樞元素位置，我們以第一個(gè)元素為中樞元素???????//退出條件這里只可能是?low?=?high???????while?(true)?{???????if?(pivot?!=?high)?{//如果中樞元素在低指針位置時(shí)，我們移動(dòng)高指針???????//如果高指針元素小于中樞元素時(shí)，則與中樞元素交換???????if?((array[high].compareTo(array[pivot]))?<?0)?{???????swap(array,?high,?pivot);???????//交換后中樞元素在高指針位置了???????pivot?=?high;???????}?else?{//如果未找到小于中樞元素，則高指針前移繼續(xù)找???????high--;???????}???????}?else?{//否則中樞元素在高指針位置???????//如果低指針元素大于中樞元素時(shí)，則與中樞元素交換???????if?((array[low].compareTo(array[pivot]))?>?0)?{???????swap(array,?low,?pivot);???????//交換后中樞元素在低指針位置了???????pivot?=?low;???????}?else?{//如果未找到大于中樞元素，則低指針后移繼續(xù)找???????low++;???????}???????}???????if?(low?==?high)?{???????break;???????}???????}???????//返回中樞元素所在位置，以便下次分區(qū)???????return?pivot;???????}???????/**????*?實(shí)現(xiàn)三????*?????*?@param?array?待排序數(shù)組????*?@param?low?待排序區(qū)低指針????*?@param?high?待排序區(qū)高指針????*?@param?c?比較器????*?@return?int?調(diào)整后中樞位置????*/??????private?int?partition3(Integer[]?array,?int?low,?int?high)?{???????int?pivot?=?low;//中樞元素位置，我們以第一個(gè)元素為中樞元素???????low++;???????//----調(diào)整高低指針?biāo)赶虻脑仨樞?#xff0c;把小于中樞元素的移到前部分，大于中樞元素的移到后面部分???????//退出條件這里只可能是?low?=?high???????while?(true)?{???????//如果高指針未超出低指針???????while?(low?<?high)?{???????//如果低指針指向的元素大于或等于中樞元素時(shí)表示找到了，退出，注：等于時(shí)也要后移???????if?((array[low].compareTo(array[pivot]))?>=?0)?{???????break;???????}?else?{//如果低指針指向的元素小于中樞元素時(shí)繼續(xù)找???????low++;???????}???????}???????while?(high?>?low)?{???????//如果高指針指向的元素小于中樞元素時(shí)表示找到，退出???????if?((array[high].compareTo(array[pivot]))?<?0)?{???????break;???????}?else?{//如果高指針指向的元素大于中樞元素時(shí)繼續(xù)找???????high--;???????}???????}???????//退出上面循環(huán)時(shí)?low?=?high???????if?(low?==?high)?{???????break;???????}???????swap(array,?low,?high);???????}???????//----高低指針?biāo)赶虻脑嘏判蛲瓿珊?#xff0c;還得要把中樞元素放到適當(dāng)?shù)奈恢???????if?((array[pivot].compareTo(array[low]))?>?0)?{???????//如果退出循環(huán)時(shí)中樞元素大于了低指針或高指針元素時(shí)，中樞元素需與low元素交換???????swap(array,?low,?pivot);???????pivot?=?low;???????}?else?if?((array[pivot].compareTo(array[low]))?<=?0)?{???????swap(array,?low?-?1,?pivot);???????pivot?=?low?-?1;???????}???????//返回中樞元素所在位置，以便下次分區(qū)???????return?pivot;???????}???????/**????*?交換數(shù)組中的兩個(gè)元素的位置????*?@param?array?待交換的數(shù)組????*?@param?i?第一個(gè)元素????*?@param?j?第二個(gè)元素????*/??????public?void?swap(Integer[]?array,?int?i,?int?j)?{???????if?(i?!=?j)?{//只有不是同一位置時(shí)才需交換???????Integer?tmp?=?array[i];???????array[i]?=?array[j];???????array[j]?=?tmp;???????}???????}?????/**?????*?測(cè)試?????*?@param?args?????*/??????public?static?void?main(String[]?args)?{???????Integer[]?intgArr?=?{?5,?9,?1,?4,?2,?6,?3,?8,?0,?7?};??????QuickSort?quicksort?=?new?QuickSort();???????quicksort.sort(intgArr,0,intgArr.length-1);????for(Integer?intObj:intgArr){????System.out.print(intObj?+?"?");????}????}??????? }

六、歸并排序

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

/**??? *歸并排序：里面是一個(gè)遞歸程序，深刻理解之。??? */???? public?class?MergeSort{???????/**????*?遞歸劃分?jǐn)?shù)組????*?@param?arr????*?@param?from????*?@param?end????*?@param?c?void????*/??????public?void?partition(Integer[]?arr,?int?from,?int?end)?{???????//劃分到數(shù)組只有一個(gè)元素時(shí)才不進(jìn)行再劃分???????if?(from?<?end)?{???????//從中間劃分成兩個(gè)數(shù)組???????int?mid?=?(from?+?end)?/?2;???????partition(arr,?from,?mid);???????partition(arr,?mid?+?1,?end);???????//合并劃分后的兩個(gè)數(shù)組???????merge(arr,?from,?end,?mid);???????}???????}???????/**????*?數(shù)組合并，合并過(guò)程中對(duì)兩部分?jǐn)?shù)組進(jìn)行排序????*?前后兩部分?jǐn)?shù)組里是有序的????*?@param?arr????*?@param?from????*?@param?end????*?@param?mid????*?@param?c?void????*/??????public?void?merge(Integer[]?arr,?int?from,?int?end,?int?mid)?{???????Integer[]?tmpArr?=?new?Integer[10];????int?tmpArrIndex?=?0;//指向臨時(shí)數(shù)組???????int?part1ArrIndex?=?from;//指向第一部分?jǐn)?shù)組???????int?part2ArrIndex?=?mid?+?1;//指向第二部分?jǐn)?shù)組???????//由于兩部分?jǐn)?shù)組里是有序的，所以每部分可以從第一個(gè)元素依次取到最后一個(gè)元素，再對(duì)兩部分???????//取出的元素進(jìn)行比較。只要某部分?jǐn)?shù)組元素取完后，退出循環(huán)???????while?((part1ArrIndex?<=?mid)?&&?(part2ArrIndex?<=?end))?{???????//從兩部分?jǐn)?shù)組里各取一個(gè)進(jìn)行比較，取最小一個(gè)并放入臨時(shí)數(shù)組中???????if?(arr[part1ArrIndex]?-?arr[part2ArrIndex]?<?0)?{???????//如果第一部分?jǐn)?shù)組元素小，則將第一部分?jǐn)?shù)組元素放入臨時(shí)數(shù)組中，并且臨時(shí)數(shù)組指針???????//tmpArrIndex下移一個(gè)以做好下次存儲(chǔ)位置準(zhǔn)備，前部分?jǐn)?shù)組指針part1ArrIndex???????//也要下移一個(gè)以便下次取出下一個(gè)元素與后部分?jǐn)?shù)組元素比較???????tmpArr[tmpArrIndex++]?=?arr[part1ArrIndex++];???????}?else?{???????//如果第二部分?jǐn)?shù)組元素小，則將第二部分?jǐn)?shù)組元素放入臨時(shí)數(shù)組中???????tmpArr[tmpArrIndex++]?=?arr[part2ArrIndex++];???????}???????}???????//由于退出循環(huán)后，兩部分?jǐn)?shù)組中可能有一個(gè)數(shù)組元素還未處理完，所以需要額外的處理，當(dāng)然不可???????//能兩部分?jǐn)?shù)組都有未處理完的元素，所以下面兩個(gè)循環(huán)最多只有一個(gè)會(huì)執(zhí)行，并且都是大于已放入???????//臨時(shí)數(shù)組中的元素???????while?(part1ArrIndex?<=?mid)?{???????tmpArr[tmpArrIndex++]?=?arr[part1ArrIndex++];???????}???????while?(part2ArrIndex?<=?end)?{???????tmpArr[tmpArrIndex++]?=?arr[part2ArrIndex++];???????}???????//最后把臨時(shí)數(shù)組拷貝到源數(shù)組相同的位置???????System.arraycopy(tmpArr,?0,?arr,?from,?end?-?from?+?1);???????}???????/**????*?測(cè)試????*?@param?args????*/??????public?static?void?main(String[]?args)?{???????Integer[]?intgArr?=?{5,9,1,4,2,6,3,8,0,7};???????MergeSort?insertSort?=?new?MergeSort();???????insertSort.partition(intgArr,0,intgArr.length-1);????for(Integer?a:intgArr){????System.out.print(a?+?"?");????}????}??????? }

七、堆排序(Heap Sort)
1. 基本思想：
? 堆排序是一樹形選擇排序，在排序過(guò)程中，將R[1..N]看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。
2. 堆的定義: N個(gè)元素的序列K1,K2,K3,...,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：
?????? Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

? 堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個(gè)堆，它對(duì)應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點(diǎn)（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。
3. 排序過(guò)程：
堆排序正是利用小根堆（或大根堆）來(lái)選取當(dāng)前無(wú)序區(qū)中關(guān)鍵字小（或最大）的記錄實(shí)現(xiàn)排序的。我們不妨利用大根堆來(lái)排序。每一趟排序的基本操作是：將當(dāng)前無(wú)序區(qū)調(diào)整為一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無(wú)序區(qū)中的最后一個(gè)記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個(gè)記錄區(qū)。
【示例】：對(duì)關(guān)鍵字序列42，13，91，23，24，16，05，88建堆?

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

/**?? *?選擇排序之堆排序：?? */???? public?class?HeapSort?{???????/**????*?排序算法的實(shí)現(xiàn)，對(duì)數(shù)組中指定的元素進(jìn)行排序????*?@param?array?待排序的數(shù)組????*?@param?from?從哪里開始排序????*?@param?end?排到哪里????*?@param?c?比較器????*/??????public?void?sort(Integer[]?array,?int?from,?int?end)?{???????//創(chuàng)建初始堆???????initialHeap(array,?from,?end);???????/*????*?對(duì)初始堆進(jìn)行循環(huán)，且從最后一個(gè)節(jié)點(diǎn)開始，直接樹只有兩個(gè)節(jié)點(diǎn)止????*?每輪循環(huán)后丟棄最后一個(gè)葉子節(jié)點(diǎn)，再看作一個(gè)新的樹????*/??????for?(int?i?=?end?-?from?+?1;?i?>=?2;?i--)?{???????//根節(jié)點(diǎn)與最后一個(gè)葉子節(jié)點(diǎn)交換位置，即數(shù)組中的第一個(gè)元素與最后一個(gè)元素互換???????swap(array,?from,?i?-?1);???????//交換后需要重新調(diào)整堆???????adjustNote(array,?1,?i?-?1);???????}???????}???????/**????*?初始化堆????*?比如原序列為：7,2,4,3,12,1,9,6,8,5,10,11????*?則初始堆為：1,2,4,3,5,7,9,6,8,12,10,11????*?@param?arr?排序數(shù)組????*?@param?from?從哪????*?@param?end?到哪????*?@param?c?比較器????*/??????private?void?initialHeap(Integer[]?arr,?int?from,?int?end)?{???????int?lastBranchIndex?=?(end?-?from?+?1)?/?2;//最后一個(gè)非葉子節(jié)點(diǎn)???????//對(duì)所有的非葉子節(jié)點(diǎn)進(jìn)行循環(huán)?，且從最一個(gè)非葉子節(jié)點(diǎn)開始???????for?(int?i?=?lastBranchIndex;?i?>=?1;?i--)?{???????adjustNote(arr,?i,?end?-?from?+?1);???????}???????}???????/**????*?調(diào)整節(jié)點(diǎn)順序，從父、左右子節(jié)點(diǎn)三個(gè)節(jié)點(diǎn)中選擇一個(gè)最大節(jié)點(diǎn)與父節(jié)點(diǎn)轉(zhuǎn)換????*?@param?arr?待排序數(shù)組????*?@param?parentNodeIndex?要調(diào)整的節(jié)點(diǎn)，與它的子節(jié)點(diǎn)一起進(jìn)行調(diào)整????*?@param?len?樹的節(jié)點(diǎn)數(shù)????*?@param?c?比較器????*/??????private?void?adjustNote(Integer[]?arr,?int?parentNodeIndex,?int?len)?{???????int?minNodeIndex?=?parentNodeIndex;???????//如果有左子樹，i?*?2為左子節(jié)點(diǎn)索引????????if?(parentNodeIndex?*?2?<=?len)?{???????//如果父節(jié)點(diǎn)小于左子樹時(shí)????????if?((arr[parentNodeIndex?-?1].compareTo(arr[parentNodeIndex?*?2?-?1]))?<?0)?{???????minNodeIndex?=?parentNodeIndex?*?2;//記錄最大索引為左子節(jié)點(diǎn)索引????????}???????//?只有在有或子樹的前提下才可能有右子樹，再進(jìn)一步斷判是否有右子樹????????if?(parentNodeIndex?*?2?+?1?<=?len)?{???????//如果右子樹比最大節(jié)點(diǎn)更大????????if?((arr[minNodeIndex?-?1].compareTo(arr[(parentNodeIndex?*?2?+?1)?-?1]))?<?0)?{???????minNodeIndex?=?parentNodeIndex?*?2?+?1;//記錄最大索引為右子節(jié)點(diǎn)索引????????}???????}???????}???????//如果在父節(jié)點(diǎn)、左、右子節(jié)點(diǎn)三都中，最大節(jié)點(diǎn)不是父節(jié)點(diǎn)時(shí)需交換，把最大的與父節(jié)點(diǎn)交換，創(chuàng)建大頂堆???????if?(minNodeIndex?!=?parentNodeIndex)?{???????swap(arr,?parentNodeIndex?-?1,?minNodeIndex?-?1);???????//交換后可能需要重建堆，原父節(jié)點(diǎn)可能需要繼續(xù)下沉???????if?(minNodeIndex?*?2?<=?len)?{//是否有子節(jié)點(diǎn)，注，只需判斷是否有左子樹即可知道???????adjustNote(arr,?minNodeIndex,?len);???????}???????}???????}???????/**????*?交換數(shù)組中的兩個(gè)元素的位置????*?@param?array?待交換的數(shù)組????*?@param?i?第一個(gè)元素????*?@param?j?第二個(gè)元素????*/??????public?void?swap(Integer[]?array,?int?i,?int?j)?{???????if?(i?!=?j)?{//只有不是同一位置時(shí)才需交換???????Integer?tmp?=?array[i];???????array[i]?=?array[j];???????array[j]?=?tmp;???????}???????}?????/**?????*?測(cè)試?????*?@param?args?????*/??????public?static?void?main(String[]?args)?{???????Integer[]?intgArr?=?{?5,?9,?1,?4,?2,?6,?3,?8,?0,?7?};??????HeapSort?heapsort?=?new?HeapSort();???????heapsort.sort(intgArr,0,intgArr.length-1);????for(Integer?intObj:intgArr){????System.out.print(intObj?+?"?");????}????}??????? }

八、桶式排序

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

/**????*?桶式排序:????*?桶式排序不再是基于比較的了，它和基數(shù)排序同屬于分配類的排序，????*?這類排序的特點(diǎn)是事先要知道待排?序列的一些特征。????*?桶式排序事先要知道待排?序列在一個(gè)范圍內(nèi)，而且這個(gè)范圍應(yīng)該不是很大的。????*?比如知道待排序列在[0,M）內(nèi)，那么可以分配M個(gè)桶，第I個(gè)桶記錄I的出現(xiàn)情況，????*?最后根據(jù)每個(gè)桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。????*?這里我們用兩個(gè)臨時(shí)性數(shù)組，一個(gè)用于記錄位置信息，一個(gè)用于方便輸出數(shù)據(jù)成有序方式，????*?另外我們假設(shè)數(shù)據(jù)落在0到MAX,如果所給數(shù)據(jù)不是從0開始，你可以把每個(gè)數(shù)減去最小的數(shù)。????*/?????? public?class?BucketSort?{???????public?void?sort(int[]?keys,int?from,int?len,int?max)???????{???????int[]?temp=new?int[len];???????int[]?count=new?int[max];???????for(int?i=0;i<len;i++)???????{???????count[keys[from+i]]++;???????}???????//calculate?position?info???????for(int?i=1;i<max;i++)???????{???????count[i]=count[i]+count[i-1];//這意味著有多少數(shù)目小于或等于i，因此它也是position+?1???????}???????System.arraycopy(keys,?from,?temp,?0,?len);???????for(int?k=len-1;k>=0;k--)//從最末到開頭保持穩(wěn)定性???????{???????keys[--count[temp[k]]]=temp[k];//?position?+1?=count???????}???????}???????/**????*?@param?args????*/??????public?static?void?main(String[]?args)?{???????int[]?a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};???????BucketSort?bucketSort=new?BucketSort();???????bucketSort.sort(a,0,a.length,20);//actually?is?18,?but?20?will?also?work???????for(int?i=0;i<a.length;i++)???????{???????System.out.print(a[i]+",");???????}???????}???????}

九、基數(shù)排序

java代碼實(shí)現(xiàn)：?

/**?? *?基數(shù)排序：?? */???? import?java.util.Arrays;????? public?class?RadixSort?{???????/**????*?取數(shù)x上的第d位數(shù)字????*?@param?x?數(shù)????*?@param?d?第幾位，從低位到高位????*?@return????*/??????public?int?digit(long?x,?long?d)?{???????long?pow?=?1;???????while?(--d?>?0)?{???????pow?*=?10;???????}???????return?(int)?(x?/?pow?%?10);???????}???????/**????*?基數(shù)排序?qū)崿F(xiàn)，以升序排序（下面程序中的位記錄器count中，從第0個(gè)元素到第9個(gè)元素依次用來(lái)????*?記錄當(dāng)前比較位是0的有多少個(gè)..是9的有多少個(gè)數(shù)，而降序時(shí)則從第0個(gè)元素到第9個(gè)元素依次用來(lái)????*?記錄當(dāng)前比較位是9的有多少個(gè)..是0的有多少個(gè)數(shù)）????*?@param?arr?待排序數(shù)組????*?@param?digit?數(shù)組中最大數(shù)的位數(shù)????*?@return????*/??????public?long[]?radixSortAsc(long[]?arr)?{???????//從低位往高位循環(huán)???????for?(int?d?=?1;?d?<=?getMax(arr);?d++)?{???????//臨時(shí)數(shù)組，用來(lái)存放排序過(guò)程中的數(shù)據(jù)???????long[]?tmpArray?=?new?long[arr.length];???????//位記數(shù)器，從第0個(gè)元素到第9個(gè)元素依次用來(lái)記錄當(dāng)前比較位是0的有多少個(gè)..是9的有多少個(gè)數(shù)???????int[]?count?=?new?int[10];???????//開始統(tǒng)計(jì)0有多少個(gè)，并存儲(chǔ)在第0位，再統(tǒng)計(jì)1有多少個(gè)，并存儲(chǔ)在第1位..依次統(tǒng)計(jì)到9有多少個(gè)???????for?(int?i?=?0;?i?<?arr.length;?i++)?{???????count[digit(arr[i],?d)]?+=?1;???????}???????/*????*?比如某次經(jīng)過(guò)上面統(tǒng)計(jì)后結(jié)果為：[0,?2,?3,?3,?0,?0,?0,?0,?0,?0]則經(jīng)過(guò)下面計(jì)算后?結(jié)果為：????*?[0,?2,?5,?8,?8,?8,?8,?8,?8,?8]但實(shí)質(zhì)上只有如下[0,?2,?5,?8,?0,?0,?0,?0,?0,?0]中????*?非零數(shù)才用到，因?yàn)槠渌徊淮嬖?#xff0c;它們分別表示如下：2表示比較位為1的元素可以存放在索引為1、0的????*?位置，5表示比較位為2的元素可以存放在4、3、2三個(gè)(5-2=3)位置，8表示比較位為3的元素可以存放在????*?7、6、5三個(gè)(8-5=3)位置????*/??????for?(int?i?=?1;?i?<?10;?i++)?{???????count[i]?+=?count[i?-?1];???????}???????/*????*?注，這里只能從數(shù)組后往前循環(huán)，因?yàn)榕判驎r(shí)還需保持以前的已排序好的?順序，不應(yīng)該打????*?亂原來(lái)已排好的序，如果從前往后處理，則會(huì)把原來(lái)在前面會(huì)擺到后面去，因?yàn)樵谔幚砟硞€(gè)????*?元素的位置時(shí)，位記數(shù)器是從大到到小（count[digit(arr[i],?d)]--）的方式來(lái)處????*?理的，即先存放索引大的元素，再存放索引小的元素，所以需從最后一個(gè)元素開始處理。????*?如有這樣的一個(gè)序列[212,213,312]，如果按照從第一個(gè)元素開始循環(huán)的話，經(jīng)過(guò)第一輪????*?后（個(gè)位）排序后，得到這樣一個(gè)序列[312,212,213]，第一次好像沒(méi)什么問(wèn)題，但問(wèn)題會(huì)????*?從第二輪開始出現(xiàn)，第二輪排序后，會(huì)得到[213,212,312]，這樣個(gè)位為3的元素本應(yīng)該????*?放在最后，但經(jīng)過(guò)第二輪后卻排在了前面了，所以出現(xiàn)了問(wèn)題????*/??????for?(int?i?=?arr.length?-?1;?i?>=?0;?i--)?{//只能從最后一個(gè)元素往前處理???????//for?(int?i?=?0;?i?<?arr.length;?i++)?{//不能從第一個(gè)元素開始循環(huán)???????tmpArray[count[digit(arr[i],?d)]?-?1]?=?arr[i];???????count[digit(arr[i],?d)]--;???????}???????System.arraycopy(tmpArray,?0,?arr,?0,?tmpArray.length);???????}???????return?arr;???????}???????/**????*?基數(shù)排序?qū)崿F(xiàn)，以降序排序（下面程序中的位記錄器count中，從第0個(gè)元素到第9個(gè)元素依次用來(lái)????*?記錄當(dāng)前比較位是0的有多少個(gè)..是9的有多少個(gè)數(shù)，而降序時(shí)則從第0個(gè)元素到第9個(gè)元素依次用來(lái)????*?記錄當(dāng)前比較位是9的有多少個(gè)..是0的有多少個(gè)數(shù)）????*?@param?arr?待排序數(shù)組????*?@return????*/??????public?long[]?radixSortDesc(long[]?arr)?{???????for?(int?d?=?1;?d?<=?getMax(arr);?d++)?{???????long[]?tmpArray?=?new?long[arr.length];???????//位記數(shù)器，從第0個(gè)元素到第9個(gè)元素依次用來(lái)記錄當(dāng)前比較位是9的有多少個(gè)..是0的有多少個(gè)數(shù)???????int[]?count?=?new?int[10];???????//開始統(tǒng)計(jì)0有多少個(gè)，并存儲(chǔ)在第9位，再統(tǒng)計(jì)1有多少個(gè)，并存儲(chǔ)在第8位..依次統(tǒng)計(jì)???????//到9有多少個(gè)，并存儲(chǔ)在第0位???????for?(int?i?=?0;?i?<?arr.length;?i++)?{???????count[9?-?digit(arr[i],?d)]?+=?1;???????}???????for?(int?i?=?1;?i?<?10;?i++)?{???????count[i]?+=?count[i?-?1];???????}???????for?(int?i?=?arr.length?-?1;?i?>=?0;?i--)?{???????tmpArray[count[9?-?digit(arr[i],?d)]?-?1]?=?arr[i];???????count[9?-?digit(arr[i],?d)]--;???????}???????System.arraycopy(tmpArray,?0,?arr,?0,?tmpArray.length);???????}???????return?arr;???????}???????private?int?getMax(long[]?array)?{???????int?maxlIndex?=?0;???????for?(int?j?=?1;?j?<?array.length;?j++)?{???????if?(array[j]?>?array[maxlIndex])?{???????maxlIndex?=?j;???????}???????}???????return?String.valueOf(array[maxlIndex]).length();???????}???????public?static?void?main(String[]?args)?{???????long[]?ary?=?new?long[]?{?123,?321,?132,?212,?213,?312,?21,?223?};???????RadixSort?rs?=?new?RadixSort();???????System.out.println("升?-?"?+?Arrays.toString(rs.radixSortAsc(ary)));???????ary?=?new?long[]?{?123,?321,?132,?212,?213,?312,?21,?223?};???????System.out.println("降?-?"?+?Arrays.toString(rs.radixSortDesc(ary)));???????}??????? }

十、幾種排序算法的比較和選擇?
1. 選取排序方法需要考慮的因素：
(1) 待排序的元素?cái)?shù)目n；
(2) 元素本身信息量的大小；
(3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況；
(4) 語(yǔ)言工具的條件，輔助空間的大小等。
2. 小結(jié)：
(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動(dòng)操作較直接選擇排序多，因而當(dāng)記錄本身信息量較大時(shí)，用直接選擇排序較好。
(2) 若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒泡排序?yàn)橐恕?br />(3) 若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內(nèi)部排序法中被認(rèn)為是最好的方法。
(4) 在基于比較排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來(lái)描述比較判定過(guò)程，由此可以證明：當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時(shí)間。
(5) 當(dāng)記錄本身信息量較大時(shí)，為避免耗費(fèi)大量時(shí)間移動(dòng)記錄，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。

?

?

排序簡(jiǎn)介?
排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算,在計(jì)算機(jī)及其應(yīng)用系統(tǒng)中,花費(fèi)在排序上的時(shí)間在系統(tǒng)運(yùn)行時(shí)間中占有很大比重;并且排序本身對(duì)推動(dòng)算法分析的發(fā)展也起很大作用。目前已有上百種排序方法，但尚未有一個(gè)最理想的盡如人意的方法，本章介紹常用的如下排序方法，并對(duì)它們進(jìn)行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸并排序；
5、基數(shù)排序；

學(xué)習(xí)重點(diǎn)?
1、掌握排序的基本概念和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸并排序的方法及其性能分析方法；
3、了解基數(shù)排序方法及其性能分析方法。

排序（sort）或分類

??? 　所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來(lái)。其確切定義如下：
　　輸入：n個(gè)記錄R₁，R₂，…，R_n，其相應(yīng)的關(guān)鍵字分別為K₁，K₂，…，K_n。
　　輸出：R_il，R_i2，…，R_in，使得K_i1≤K_i2≤…≤K_in。(或K_i1≥K_i2≥…≥K_in)。

1．被排序?qū)ο?-文件
　　被排序的對(duì)象--文件由一組記錄組成。
　　記錄則由若干個(gè)數(shù)據(jù)項(xiàng)(或域)組成。其中有一項(xiàng)可用來(lái)標(biāo)識(shí)一個(gè)記錄，稱為關(guān)鍵字項(xiàng)。該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字(Key)。
??注意：
　??? 在不易產(chǎn)生混淆時(shí)，將關(guān)鍵字項(xiàng)簡(jiǎn)稱為關(guān)鍵字。

2．排序運(yùn)算的依據(jù)--關(guān)鍵字
??? 　用來(lái)作排序運(yùn)算依據(jù)的關(guān)鍵字，可以是數(shù)字類型，也可以是字符類型。
　??? 關(guān)鍵字的選取應(yīng)根據(jù)問(wèn)題的要求而定。
【例】在高考成績(jī)統(tǒng)計(jì)中將每個(gè)考生作為一個(gè)記錄。每條記錄包含準(zhǔn)考證號(hào)、姓名、各科的分?jǐn)?shù)和總分?jǐn)?shù)等項(xiàng)內(nèi)容。若要惟一地標(biāo)識(shí)一個(gè)考生的記錄，則必須用"準(zhǔn)考證號(hào)"作為關(guān)鍵字。若要按照考生的總分?jǐn)?shù)排名次，則需用"總分?jǐn)?shù)"作為關(guān)鍵字。

排序的穩(wěn)定性

　??? 當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，排序結(jié)果是惟一的，否則排序結(jié)果不唯一。
??? 　在待排序的文件中，若存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對(duì)次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。
??注意：
　??? 排序算法的穩(wěn)定性是針對(duì)所有輸入實(shí)例而言的。即在所有可能的輸入實(shí)例中，只要有一個(gè)實(shí)例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。

排序方法的分類

1．按是否涉及數(shù)據(jù)的內(nèi)、外存交換分
??? 　在排序過(guò)程中，若整個(gè)文件都是放在內(nèi)存中處理，排序時(shí)不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)部排序(簡(jiǎn)稱內(nèi)排序)；反之，若排序過(guò)程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。
??注意：
　??? ① 內(nèi)排序適用于記錄個(gè)數(shù)不很多的小文件
??? 　② 外排序則適用于記錄個(gè)數(shù)太多，不能一次將其全部記錄放人內(nèi)存的大文件。

2．按策略劃分內(nèi)部排序方法
??? 　可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。

排序算法分析

1．排序算法的基本操作
??? 　大多數(shù)排序算法都有兩個(gè)基本的操作：
　　(1) 比較兩個(gè)關(guān)鍵字的大小；
　　(2) 改變指向記錄的指針或移動(dòng)記錄本身。
??注意：
　??? 第(2)種基本操作的實(shí)現(xiàn)依賴于待排序記錄的存儲(chǔ)方式。

2．待排文件的常用存儲(chǔ)方式
（1） 以順序表(或直接用向量)作為存儲(chǔ)結(jié)構(gòu)
??? 排序過(guò)程：對(duì)記錄本身進(jìn)行物理重排（即通過(guò)關(guān)鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲(chǔ)結(jié)構(gòu)
　　排序過(guò)程：無(wú)須移動(dòng)記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈?zhǔn)?排序；

（3） 用順序的方式存儲(chǔ)待排序的記錄，但同時(shí)建立一個(gè)輔助表(如包括關(guān)鍵字和指向記錄位置的指針組成的索引表)
　　排序過(guò)程：只需對(duì)輔助表的表目進(jìn)行物理重排（即只移動(dòng)輔助表的表目，而不移動(dòng)記錄本身）。適用于難于在鏈表上實(shí)現(xiàn)，仍需避免排序過(guò)程中移動(dòng)記錄的排序方法。

3．排序算法性能評(píng)價(jià)
（1） 評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)
　　評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：
??? 　① 執(zhí)行時(shí)間和所需的輔助空間
??? 　② 算法本身的復(fù)雜程度

（2） 排序算法的空間復(fù)雜度
　　若排序算法所需的輔助空間并不依賴于問(wèn)題的規(guī)模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
　　非就地排序一般要求的輔助空間為O(n)。

（3） 排序算法的時(shí)間開銷
　　大多數(shù)排序算法的時(shí)間開銷主要是關(guān)鍵字之間的比較和記錄的移動(dòng)。有的排序算法其執(zhí)行時(shí)間不僅依賴于問(wèn)題的規(guī)模，還取決于輸入實(shí)例中數(shù)據(jù)的狀態(tài)。

文件的順序存儲(chǔ)結(jié)構(gòu)表示

? #define n l00 //假設(shè)的文件長(zhǎng)度，即待排序的記錄數(shù)目
? typedef int KeyType； //假設(shè)的關(guān)鍵字類型
? typedef struct{ //記錄類型
??? KeyType key； //關(guān)鍵字項(xiàng)
??? InfoType otherinfo；//其它數(shù)據(jù)項(xiàng)，類型InfoType依賴于具體應(yīng)用而定義
?? }RecType；
? typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個(gè)單元一般用作哨兵
??注意：
??? 　若關(guān)鍵字類型沒(méi)有比較算符，則可事先定義宏或函數(shù)來(lái)表示比較運(yùn)算。
【例】關(guān)鍵字為字符串時(shí)，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

?

按平均時(shí)間將排序分為四類：

（1）平方階(O(n²))排序
??? 　一般稱為簡(jiǎn)單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對(duì)數(shù)階(O(nlgn))排序
??? 　如快速、堆和歸并排序；

（3）O(n^1+￡)階排序
??? 　￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序
??? 　如桶、箱和基數(shù)排序。

各種排序方法比較

???? 簡(jiǎn)單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)，直接插入和冒泡均最佳。

影響排序效果的因素

??? 　因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：
　　①待排序的記錄數(shù)目n；
　　②記錄的大小(規(guī)模)；
　　③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；
　　④對(duì)穩(wěn)定性的要求；
　　⑤語(yǔ)言工具的條件；
　　⑥存儲(chǔ)結(jié)構(gòu)；
　　⑦時(shí)間和輔助空間復(fù)雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。
??? 　當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?br />(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐?#xff1b;
(3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
??? 　快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；
??? 　堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。
??? 　若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的? 排序算法并不值得提倡，通常可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長(zhǎng)的有序子文件，然后再兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。

4)在基于比較的排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來(lái)描述比較判定過(guò)程。
??? 　當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于"比較"的排序算法，至少需要O(nlgn)的時(shí)間。
??? 　箱排序和基數(shù)排序只需一步就會(huì)引起m種可能的轉(zhuǎn)移，即把一個(gè)記錄裝入m個(gè)箱子之一，因此在一般情況下，箱排序和基數(shù)排序可能在O(n)時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序。但是，箱排序和基數(shù)排序只適用于像字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵字，而當(dāng)關(guān)鍵字的取值范圍屬于某個(gè)無(wú)窮集合(例如實(shí)數(shù)型關(guān)鍵字)時(shí)，無(wú)法使用箱排序和基數(shù)排序，這時(shí)只有借助于"比較"的方法來(lái)排序。
??? 　若n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好。雖然桶排序?qū)﹃P(guān)鍵字的結(jié)構(gòu)無(wú)要求，但它也只有在關(guān)鍵字是隨機(jī)分布時(shí)才能使平均時(shí)間達(dá)到線性階，否則為平方階。同時(shí)要注意，箱、桶、基數(shù)這三種分配排序均假定了關(guān)鍵字若為數(shù)字時(shí)，則其值均是非負(fù)的，否則將其映射到箱(桶)號(hào)時(shí)，又要增加相應(yīng)的時(shí)間。
(5)有的語(yǔ)言(如Fortran，Cobol或Basic等)沒(méi)有提供指針及遞歸，導(dǎo)致實(shí)現(xiàn)歸并、快速(它們用遞歸實(shí)現(xiàn)較簡(jiǎn)單)和基數(shù)(使用了指針)等排序算法變得復(fù)雜。此時(shí)可考慮用其它排序。
(6)本章給出的排序算法，輸人數(shù)據(jù)均是存儲(chǔ)在一個(gè)向量中。當(dāng)記錄的規(guī)模較大時(shí)，為避免耗費(fèi)大量的時(shí)間去移動(dòng)記錄，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。譬如插入排序、歸并排序、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)，使之減少記錄的移動(dòng)次數(shù)。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下，可以提取關(guān)鍵字建立索引表，然后對(duì)索引表進(jìn)行排序。然而更為簡(jiǎn)單的方法是：引人一個(gè)整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結(jié)束后，向量t就指示了記錄之間的順序關(guān)系：
??????? R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
? 若要求最終結(jié)果是：
?????? R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結(jié)束后，再按輔助表所規(guī)定的次序重排各記錄，完成這種重排的時(shí)間是O(n)。

轉(zhuǎn)載于:https://blog.51cto.com/8892608/1542827

總結(jié)

以上是生活随笔為你收集整理的各种排序算法及其java程序实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。