排序就是將一組對(duì)象按照某種邏輯順序重新排列的過(guò)程。比如，訂單按照日期排序的——這種排序很可能使用了某種排序算法?，F(xiàn)在計(jì)算機(jī)的廣泛使用使得數(shù)據(jù)無(wú)處不在，而整理數(shù)據(jù)的第一步通常就是進(jìn)行排序。
學(xué)習(xí)排序算法三大實(shí)際意義
- IT從業(yè)人員必備技能，也是互聯(lián)網(wǎng)公司面試的必考點(diǎn)
- 其中包含的技術(shù)和思想也能有效解決其他類型的問(wèn)題
- 排序算法常常是我們解決其他問(wèn)題的第一步
圖片來(lái)源于網(wǎng)絡(luò)
十大排序算法：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序、希爾排序、計(jì)數(shù)排序，基數(shù)排序，桶排序
一、冒泡排序算法
一種簡(jiǎn)單的排序算法。它反復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。這個(gè)工作重復(fù)地進(jìn)行直到?jīng)]有元素再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
具體步驟
- 從數(shù)組頭開始，比較相鄰的元素。如果第一個(gè)比第二個(gè)大(小)，就交換它們兩個(gè)；
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到尾部的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大(小)的數(shù)；
- 重復(fù)步驟1~2，重復(fù)次數(shù)等于數(shù)組的長(zhǎng)度，直到排序完成
原理圖如下
代碼如下
public static int[] sort(int[] array) {
if (array.length == 0)
return array;
/*循環(huán)數(shù)組長(zhǎng)度的次數(shù)*/
for (int i = 0; i < array.length; i++){
/*從第0個(gè)元素開始，依次和后面的元素進(jìn)行比較
* j < array.length - 1 - i表示第[array.length - 1 - i]
* 個(gè)元素已經(jīng)冒泡到了合適的位置，無(wú)需進(jìn)行比較，可以減少比較次數(shù)*/
for (int j = 0; j < array.length - 1 - i; j++){
/*如果第j個(gè)元素比后面的第j+1元素大，交換兩者的位置*/
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
PrintArray.print(array);
}
System.out.println("---------------");
//PrintArray.print(array);
}
return array;
}
二、簡(jiǎn)單選擇排序
選擇排序的思想其實(shí)和冒泡排序有點(diǎn)類似，都是在一次排序后把最小的元素放到最前面。但是過(guò)程不同，冒泡排序是通過(guò)相鄰的比較和交換。而選擇排序是通過(guò)對(duì)整體的選擇。
其實(shí)選擇排序可以看成冒泡排序的優(yōu)化，因?yàn)槠淠康南嗤皇沁x擇排序只有在確定了最小數(shù)的前提下才進(jìn)行交換，大大減少了交換的次數(shù)。
舉個(gè)例子，對(duì)5,3,8,6,4這個(gè)無(wú)序序列進(jìn)行簡(jiǎn)單選擇排序，首先要選擇5以外的最小數(shù)來(lái)和5交換，也就是選擇3和5交換，一次排序后就變成了3,5,8,6,4.對(duì)剩下的序列繼續(xù)進(jìn)行選擇和交換，最終就會(huì)得到一個(gè)有序序列。
具體步驟
- 首先，找到數(shù)組中最大（?。┑哪莻€(gè)元素；
- 其次，將它和數(shù)組的第一個(gè)元素交換位置（如果第一個(gè)元素就是最大（?。┰啬敲此秃妥约航粨Q）；
- 再次，在剩下的元素中找到最大（小）的元素，將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù)，直到將整個(gè)數(shù)組排序。
原理圖如下
代碼如下
public static int[] sort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++) {
int minIndex=i;/*最小數(shù)的下標(biāo)，每個(gè)循環(huán)開始總是假設(shè)第一個(gè)數(shù)最小*/
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) /*找到最小的數(shù)*/
minIndex = j; /*將最小數(shù)的索引保存*/
}
System.out.println("最小數(shù)為："+array[minIndex]);
/*交換最小數(shù)和i當(dāng)前所指的元素*/
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
PrintArray.print(array);
System.out.println("---------------");
}
return array;
}
三、簡(jiǎn)單插入排序
插入排序不是通過(guò)交換位置而是通過(guò)比較找到合適的位置插入元素來(lái)達(dá)到排序的目的的。相信大家都有過(guò)打撲克牌的經(jīng)歷，特別是牌數(shù)較大的。在分牌時(shí)可能要整理自己的牌，牌多的時(shí)候怎么整理呢？就是拿到一張牌，找到一個(gè)合適的位置插入。這個(gè)原理其實(shí)和插入排序是一樣的。
舉個(gè)例子，我們將要收到5,3,4,,8,6這幾張牌，我們先收到5這張牌，毫無(wú)疑問(wèn)，這張牌的位置是正確的，沒(méi)必要整理。接著收到了牌3，然后3要插到5前面，把5后移一位，變成3,5。接著又收到了牌4，現(xiàn)在我們會(huì)怎么做？把4插入到5前面，把5后移一位。
具體步驟
- 對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
- 為了給要插入的元素騰出空間，我們需要將插入位置之后的已排序元素在都向右移動(dòng)一位。
插入排序所需的時(shí)間取決于輸入中元素的初始順序。例如，對(duì)一個(gè)很大且其中的元素已經(jīng)有序（或接近有序）的數(shù)組進(jìn)行排序?qū)?huì)比對(duì)隨機(jī)順序的數(shù)組或是逆序數(shù)組進(jìn)行排序要快得多。
總的來(lái)說(shuō)，插入排序?qū)τ诓糠钟行虻臄?shù)組十分高效，也很適合小規(guī)模數(shù)組。
原理圖如下
代碼如下
public static int[] sort(int[] array) {
if (array.length == 0)
return array;
int currentValue;/*當(dāng)前待排序數(shù)據(jù)，該元素之前的元素均已被排序過(guò)*/
for (int i = 0; i < array.length - 1; i++) {
int preIndex = i;/*已被排序數(shù)據(jù)的索引*/
currentValue = array[preIndex + 1];
System.out.println("待排序元素索引:"+(i + 1)+"，值為：" +currentValue+
",已被排序數(shù)據(jù)的索引:"+preIndex);
/*在已被排序過(guò)數(shù)據(jù)中倒序?qū)ふ液线m的位置，如果當(dāng)前待排序數(shù)據(jù)比比較的元素要小，
將比較的元素元素后移一位*/
while (preIndex >= 0 && currentValue < array[preIndex]) {
//將當(dāng)前元素后移一位
array[preIndex + 1] = array[preIndex];
preIndex--;
PrintArray.print(array);
}
/*while循環(huán)結(jié)束時(shí)，說(shuō)明已經(jīng)找到了當(dāng)前待排序數(shù)據(jù)的合適位置，插入*/
array[preIndex + 1] = currentValue;
System.out.println("本輪被插入排序后的數(shù)組");
PrintArray.print(array);
System.out.println("--------------------");
}
return array;
}
四、希爾排序
一種基于插入排序的快速的排序算法(請(qǐng)大家先學(xué)習(xí)插入排序，了解基本的插入排序的思想。對(duì)于大規(guī)模亂序數(shù)組插入排序很慢，因?yàn)樵刂荒芤稽c(diǎn)一點(diǎn)地從數(shù)組的一端移動(dòng)到另一端。例如，如果主鍵最小的元素正好在數(shù)組的盡頭，要將它挪到正確的位置就需要N-1 次移動(dòng)。
希爾排序?yàn)榱思涌焖俣群?jiǎn)單地改進(jìn)了插入排序，也稱為縮小增量排序，同時(shí)該算法是沖破O(n^2）的第一批算法之一。
希爾排序是把待排序數(shù)組按一定增量的分組，對(duì)每組使用直接插入排序算法排序；然后縮小增量繼續(xù)分組排序，隨著增量逐漸減少，每組包含的元素越來(lái)越多，當(dāng)增量減至 1 時(shí)，整個(gè)數(shù)組恰被分成一組，排序便完成了。這個(gè)不斷縮小的增量，就構(gòu)成了一個(gè)增量序列。
原理圖如下
希爾排序中的增量序列
- 在先前較大的增量下每個(gè)子序列的規(guī)模都不大,用直接插入排序效率都較高，盡管在隨后的增量遞減分組中子序列越來(lái)越大,由于整個(gè)序列的有序性也越來(lái)越明顯,則排序效率依然較高。
- 從理論上說(shuō)，只要一個(gè)數(shù)組是遞減的，并且最后一個(gè)值是1，都可以作為增量序列使用。有沒(méi)有一個(gè)步長(zhǎng)序列,使得排序過(guò)程中所需的比較和移動(dòng)次數(shù)相對(duì)較少,并且無(wú)論待排序列記錄數(shù)有多少,算法的時(shí)間復(fù)雜度都能漸近最佳呢？但是目前從數(shù)學(xué)上來(lái)說(shuō)，無(wú)法證明某個(gè)序列是“最好的”。
- 常用的增量序列
希爾增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N為原始數(shù)組的長(zhǎng)度，這是最常用的序列，但卻不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列： {... , 109 , 41 , 19 , 5，1}
代碼如下
public static int[] sort(int[] array) {
int len = array.length;
/*按增量分組后，每個(gè)分組中，temp代表當(dāng)前待排序數(shù)據(jù)，該元素之前的元素均已被排序過(guò)*/
/*gap指用來(lái)分組的增量，會(huì)依次遞減*/
int currentValue, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
currentValue = array[i];
/*組內(nèi)已被排序數(shù)據(jù)的索引*/
int preIndex = i - gap;
/*在組內(nèi)已被排序過(guò)數(shù)據(jù)中倒序?qū)ふ液线m的位置，如果當(dāng)前待排序數(shù)據(jù)比比較的元素要小，
并將比較的元素元素在組內(nèi)后移一位*/
while (preIndex >= 0 && array[preIndex] > currentValue) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
/*while循環(huán)結(jié)束時(shí)，說(shuō)明已經(jīng)找到了當(dāng)前待排序數(shù)據(jù)的合適位置，插入*/
array[preIndex + gap] = currentValue;
}
System.out.println("本輪增量【"+gap+"】排序后的數(shù)組");
PrintArray.print(array);
System.out.println("--------------------");
gap /= 2;
}
return array;
}
五、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用。
對(duì)于給定的一組數(shù)據(jù)，利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來(lái)越小的半子表，在對(duì)半子表排序后，再用遞歸方法將排好序的半子表合并成為越來(lái)越大的有序序列。
為了提升性能，有時(shí)我們?cè)诎胱颖淼膫€(gè)數(shù)小于某個(gè)數(shù)（比如15）的情況下，對(duì)半子表的排序采用其他排序算法，比如插入排序。
若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并，與之對(duì)應(yīng)的還有多路歸并
原理圖如下
代碼實(shí)現(xiàn)
public static int[] sort(int[] array) {
if (array.length < 2) return array;
/*切分?jǐn)?shù)組，然后遞歸調(diào)用*/
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(sort(left), sort(right));
}
/**
* 歸并排序——將兩段排序好的數(shù)組結(jié)合成一個(gè)排序數(shù)組
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length)/*左邊數(shù)組已經(jīng)取完，完全取右邊數(shù)組的值即可*/
result[index] = right[j++];
else if (j >= right.length)/*右邊數(shù)組已經(jīng)取完，完全取左邊數(shù)組的值即可*/
result[index] = left[i++];
else if (left[i] > right[j])/*左邊數(shù)組的元素值大于右邊數(shù)組，取右邊數(shù)組的值*/
result[index] = right[j++];
else/*右邊數(shù)組的元素值大于左邊數(shù)組，取左邊數(shù)組的值*/
result[index] = left[i++];
}
System.out.print("左子數(shù)組:");
PrintArray.print(left);
System.out.print("右子數(shù)組:");
PrintArray.print(right);
System.out.print("合并后數(shù)組:");
PrintArray.print(result);
System.out.println("--------------------");
return result;
}
六、快速排序
快速排序被譽(yù)為20 世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一?？焖倥判颍≦uicksort）是對(duì)冒泡排序的一種改進(jìn)，也是采用分治法的一個(gè)典型的應(yīng)用。
具體步驟
- 首先任意選取一個(gè)數(shù)據(jù)（比如數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，我們稱為基準(zhǔn)數(shù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一趟快速排序，也稱為分區(qū)（partition）操作。在實(shí)際實(shí)現(xiàn)時(shí)，一般會(huì)在原數(shù)組上直接操作。
- 通過(guò)一趟快速排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
- 為了提升性能，有時(shí)我們?cè)诜指詈螵?dú)立的兩部分的個(gè)數(shù)小于某個(gè)數(shù)（比如15）的情況下，會(huì)采用其他排序算法，比如插入排序。
原理圖如下
基準(zhǔn)數(shù)
- 基準(zhǔn)的選?。鹤顑?yōu)的情況是基準(zhǔn)值剛好取在無(wú)序區(qū)數(shù)值的中位數(shù)，這樣能夠最大效率地讓兩邊排序，同時(shí)最大地減少遞歸劃分的次數(shù)，但是一般很難做到最優(yōu)?；鶞?zhǔn)的選取一般有三種方式，選取數(shù)組的第一個(gè)元素，選取數(shù)組的最后一個(gè)元素，以及選取第一個(gè)、最后一個(gè)以及中間的元素的中位數(shù)（如4 5 6 7, 第一個(gè)4, 最后一個(gè)7, 中間的為5, 這三個(gè)數(shù)的中位數(shù)為５, 所以選擇5作為基準(zhǔn)）。
- Dual-Pivot快排：雙基準(zhǔn)快速排序算法，其實(shí)就是用兩個(gè)基準(zhǔn)數(shù), 把整個(gè)數(shù)組分成三份來(lái)進(jìn)行快速排序，在這種新的算法下面，比經(jīng)典快排從實(shí)驗(yàn)來(lái)看節(jié)省了10%的時(shí)間。
代碼如下
public static int[] sort(int[] array, int start, int end) {
if (array.length < 1 || start < 0 || end >= array.length || start > end)
return null;
/*數(shù)據(jù)分割成獨(dú)立的兩部分時(shí)，從哪兒分區(qū)的指示器*/
int zoneIndex = partition(array, start, end);
if (zoneIndex > start)
sort(array, start, zoneIndex - 1);
if (zoneIndex < end)
sort(array, zoneIndex + 1, end);
System.out.println("本輪排序后的數(shù)組");
PrintArray.printIndex(array,start,end);
System.out.println("--------------------");
return array;
}
/**
* 快速排序算法——partition
* @param array
* @param start
* @param end
* @return
*/
public static int partition(int[] array, int start, int end) {
int pivot = (int) (start + Math.random() * (end - start + 1));
System.out.println("開始下標(biāo)："+start+",結(jié)束下標(biāo):"+end+",基準(zhǔn)數(shù)下標(biāo)："
+pivot+",元素值:"+array[pivot]);
/*zoneIndex是分割指示器
從業(yè)務(wù)上來(lái)說(shuō)：比基準(zhǔn)數(shù)小的，放到指示器的左邊，比基準(zhǔn)數(shù)大的，放到指示器的右邊，
* 但在實(shí)際實(shí)現(xiàn)時(shí)，通過(guò)移動(dòng)比基準(zhǔn)數(shù)小的元素和分割指示器本身也可以達(dá)到一樣的效果*/
int zoneIndex = start - 1;
swap(array, pivot, end);/*將基準(zhǔn)數(shù)和數(shù)組尾元素交換位置*/
for (int i = start; i <= end; i++){
if (array[i] <= array[end]) {/*當(dāng)前元素小于等于基準(zhǔn)數(shù)*/
zoneIndex++;/*首先分割指示器累加*/
if (i > zoneIndex)/*當(dāng)前元素在分割指示器的右邊時(shí)，交換當(dāng)前元素和分割指示器元素*/
swap(array, i, zoneIndex);
}
System.out.println("zoneIndex："+zoneIndex+",i:"+i);
PrintArray.printIndex(array,start,end);
}
System.out.println("---------------");
return zoneIndex;
}
/**
* 交換數(shù)組內(nèi)兩個(gè)元素
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
七、堆排序
許多應(yīng)用程序都需要處理有序的元素，但不一定要求他們?nèi)坑行?，或者不一定要一次就將他們排序，很多時(shí)候，我們每次只需要操作數(shù)據(jù)中的最大元素（最小元素），那么有一種基于二叉堆的數(shù)據(jù)結(jié)構(gòu)可以提供支持。
具體步驟
- 所謂二叉堆，是一個(gè)完全二叉樹的結(jié)構(gòu)，同時(shí)滿足堆的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。在一個(gè)二叉堆中，根節(jié)點(diǎn)總是最大（或者最?。┕?jié)點(diǎn)。
- 堆排序算法就是抓住了這一特點(diǎn)，每次都取堆頂?shù)脑兀缓髮⑹Ｓ嗟脑刂匦抡{(diào)整為最大（最?。┒?，依次類推，最終得到排序的序列。
完全二叉樹
原理圖如下
代碼如下
public class HeapSort {
//聲明全局變量，用于記錄數(shù)組array的長(zhǎng)度；
private static int len;
public static int[] sort(int[] array) {
len = array.length;
if (len < 1) return array;
//1.構(gòu)建一個(gè)最大堆
buildMaxHeap(array);
//2.循環(huán)將堆首位（最大值）與末位交換，然后在重新調(diào)整最大堆
while (len > 0) {
swap(array, 0, len - 1);
len--;
adjustHeap(array, 0);
PrintArray.print(array);
System.out.println("--------------------");
}
return array;
}
/**
* 建立最大堆
*
* @param array
*/
public static void buildMaxHeap(int[] array) {
//從最后一個(gè)非葉子節(jié)點(diǎn)開始向上構(gòu)造最大堆
for (int i = (len/2-1); i >= 0; i--) {
adjustHeap(array, i);
}
System.out.println("構(gòu)造完成最大堆");
PrintArray.print(array);
System.out.println("============================================");
}
/**
* 調(diào)整使之成為最大堆
*
* @param array
* @param i
*/
public static void adjustHeap(int[] array, int i) {
int maxIndex = i;
int left = 2*i+1;
int right = 2*(i+1);
//如果有左子樹，且左子樹大于父節(jié)點(diǎn)，則將最大指針指向左子樹
if (left < len && array[left] > array[maxIndex])
maxIndex = left;
//如果有右子樹，且右子樹大于父節(jié)點(diǎn)，則將最大指針指向右子樹
if (right < len && array[right] > array[maxIndex])
maxIndex = right;
//如果父節(jié)點(diǎn)不是最大值，則將父節(jié)點(diǎn)與最大值交換，并且遞歸調(diào)整與父節(jié)點(diǎn)交換的位置。
if (maxIndex != i) {
swap(array, maxIndex, i);
adjustHeap(array, maxIndex);
}
}
/**
* 交換數(shù)組內(nèi)兩個(gè)元素
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
PrintArray.print(PrintArray.SRC);
System.out.println("============================================");
int[] dest = HeapSort.sort(PrintArray.SRC);
PrintArray.print(dest);
}
}
八、計(jì)數(shù)排序
具體步驟
- 計(jì)數(shù)排序?qū)σ欢ǚ秶鷥?nèi)的整數(shù)排序時(shí)候的速度非常快，一般快于其他排序算法。但計(jì)數(shù)排序局限性比較大，只限于對(duì)整數(shù)進(jìn)行排序，而且待排序元素值分布較連續(xù)、跨度小的情況。
- 計(jì)數(shù)排序是一個(gè)排序時(shí)不比較元素大小的排序算法。
- 如果一個(gè)數(shù)組里所有元素都是整數(shù)，而且都在0-K以內(nèi)。對(duì)于數(shù)組里每個(gè)元素來(lái)說(shuō)，如果能知道數(shù)組里有多少項(xiàng)小于或等于該元素，就能準(zhǔn)確地給出該元素在排序后的數(shù)組的位置。
原理圖如下
實(shí)際應(yīng)用中我們會(huì)同時(shí)找出數(shù)組中的max和min，主要是為了盡量節(jié)省空間。試想[1003, 1001, 1030, 1050]這樣的數(shù)據(jù)要排序，真的需要建立長(zhǎng)度為1050 + 1的數(shù)組嗎？我們只需要長(zhǎng)度為1050 - 1003 + 1= 48的數(shù)組（先不考慮額外+1的長(zhǎng)度），就能囊括從最小到最大元素之間的所有元素了。
如果待排序數(shù)組的元素值跨度很大，比如[99999, 1, 2]，為三個(gè)元素排序要使用99999 - 1 + 1的空間，實(shí)在是浪費(fèi)。所以計(jì)數(shù)排序適用于待排序元素值分布較連續(xù)、跨度小的情況。
代碼如下
public static int[] sort(int[] array) {
if (array.length == 0) return array;
/*尋找數(shù)組中最大值，最小值
* bias:偏移量,用以定位原始數(shù)組每個(gè)元素在計(jì)數(shù)數(shù)組中的下標(biāo)位置*/
int bias, min = array[0], max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
bias = 0 - min;
/*獲得計(jì)數(shù)數(shù)組的容量*/
int[] counterArray = new int[max - min + 1];
Arrays.fill(counterArray, 0);
/*遍歷整個(gè)原始數(shù)組，將原始數(shù)組中每個(gè)元素值轉(zhuǎn)化為計(jì)數(shù)數(shù)組下標(biāo)，
并將計(jì)數(shù)數(shù)組下標(biāo)對(duì)應(yīng)的元素值大小進(jìn)行累加*/
for (int i = 0; i < array.length; i++) {
counterArray[array[i] + bias]++;
}
System.out.println("計(jì)數(shù)數(shù)組為：");
PrintArray.print(counterArray);
System.out.println("============================================");
int index = 0;/*訪問(wèn)原始數(shù)組時(shí)的下標(biāo)計(jì)數(shù)器*/
int i = 0;/*訪問(wèn)計(jì)數(shù)數(shù)組時(shí)的下標(biāo)計(jì)數(shù)器*/
/*訪問(wèn)計(jì)數(shù)數(shù)組，將計(jì)數(shù)數(shù)組中的元素轉(zhuǎn)換后，重新寫回原始數(shù)組*/
while (index < array.length) {
/*只要計(jì)數(shù)數(shù)組中當(dāng)前下標(biāo)元素的值不為0，就將計(jì)數(shù)數(shù)組中的元素轉(zhuǎn)換后，重新寫回原始數(shù)組*/
if (counterArray[i] != 0) {
array[index] = i - bias;
counterArray[i]--;
index++;
} else
i++;
PrintArray.print(counterArray);
PrintArray.print(array);
System.out.println("--------------------");
}
return array;
}
final static int[] src = {5,4,5,0,3,6,2,0,2,4,3,3};
public static void main(String[] args) {
PrintArray.print(src);
System.out.println("============================================");
int[] dest = CountingSort.sort(src);
PrintArray.print(dest);
}
九、桶排序
簡(jiǎn)介
桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，利用某種函數(shù)的映射關(guān)系將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序）。
桶排序利用函數(shù)的映射關(guān)系，減少了幾乎所有的比較工作。實(shí)際上，桶排序的f(k)值的計(jì)算，其作用就相當(dāng)于快排中劃分，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)。然后只需要對(duì)桶中的少量數(shù)據(jù)做排序即可。
原理圖如下
代碼如下
public class BucketSort {
/**
*
* @param array
* @param bucketSize BucketSize，作為每個(gè)桶所能放置多少個(gè)不同數(shù)值
* （例如當(dāng)BucketSize==5時(shí)，該桶可以存放｛1,2,3,4,5｝這幾種數(shù)字，
* 但是容量不限，即可以存放100個(gè)3）；
* @return
*/
public static ArrayList<Integer> sort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
/*獲得桶的數(shù)量*/
int bucketCount = (max - min) / bucketSize + 1;
/*構(gòu)建桶*/
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
/*將原始數(shù)組中的數(shù)據(jù)分配到桶中*/
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
/*看看桶中數(shù)據(jù)的分布*/
for (int i = 0; i < bucketArr.size(); i++) {
System.out.print("第"+i+"個(gè)桶包含數(shù)據(jù)：");
PrintArray.printObject(bucketArr.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) {
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
/*對(duì)桶中的數(shù)據(jù)再次用桶進(jìn)行排序*/
ArrayList<Integer> temp = sort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
public static void main(String[] args) {
ArrayList<Integer> array = new ArrayList<>();
array.add(86);
array.add(11);
array.add(77);
array.add(23);
array.add(32);
array.add(45);
array.add(58);
array.add(63);
array.add(93);
array.add(4);
array.add(37);
array.add(22);
PrintArray.printObject(array);
System.out.println("============================================");
ArrayList<Integer> dest = BucketSort.sort(array,2);
PrintArray.printObject(dest);
}
}
十、基數(shù)排序
原理
常見(jiàn)的數(shù)據(jù)元素一般是由若干位組成的，比如字符串由若干字符組成，整數(shù)由若干位0~9數(shù)字組成?；鶖?shù)排序按照從右往左的順序，依次將每一位都當(dāng)做一次關(guān)鍵字，然后按照該關(guān)鍵字對(duì)數(shù)組排序，同時(shí)每一輪排序都基于上輪排序后的結(jié)果；當(dāng)我們將所有的位排序后，整個(gè)數(shù)組就達(dá)到有序狀態(tài)。比如對(duì)于數(shù)字2985，從右往左就是先以個(gè)位為關(guān)鍵字進(jìn)行排序，然后是十位、百位、千位，總共需要四輪。
基數(shù)是什么意思？對(duì)于十進(jìn)制整數(shù)，每一位都只可能是0~9中的某一個(gè)，總共10種可能。那10就是它的基，同理二進(jìn)制數(shù)字的基為2；對(duì)于字符串，如果它使用的是8位的擴(kuò)展ASCII字符集，那么它的基就是256。
原理圖如下
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
基數(shù)排序有兩種方法：
- MSD 從高位開始進(jìn)行排序
- LSD 從低位開始進(jìn)行排序
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：
- 基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶
- 計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
- 桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值
代碼如下
public static int[] sort(int[] array) {
if (array == null || array.length < 2)
return array;
/*找出最大數(shù)*/
int max = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
/*先算出最大數(shù)的位數(shù)*/
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
/*構(gòu)建桶*/
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++)
bucketList.add(new ArrayList<Integer>());
/*按照從右往左的順序，依次將每一位都當(dāng)做一次關(guān)鍵字，然后按照該關(guān)鍵字對(duì)數(shù)組排序，
每一輪排序都基于上輪排序后的結(jié)果*/
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
/*遍歷原始數(shù)組，投入桶中*/
for (int j = 0; j < array.length; j++) {
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
/*桶中的數(shù)據(jù)寫回原始數(shù)組，清除桶，準(zhǔn)備下一輪的排序*/
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++)
array[index++] = bucketList.get(j).get(k);
bucketList.get(j).clear();
}
}
return array;
}
十一、外部排序
原理
有時(shí)，待排序的文件很大，計(jì)算機(jī)內(nèi)存不能容納整個(gè)文件，這時(shí)候?qū)ξ募筒荒苁褂脙?nèi)部排序了（我們一般的排序都是在內(nèi)存中做的，所以稱之為內(nèi)部排序，而外部排序是指待排序的內(nèi)容不能在內(nèi)存中一下子完成，它需要做內(nèi)外存的內(nèi)容交換），外部排序常采用的排序方法也是歸并排序，這種歸并方法由兩個(gè)不同的階段組成：
- 采用適當(dāng)?shù)膬?nèi)部排序方法對(duì)輸入文件的每個(gè)片段進(jìn)行排序，將排好序的片段（成為歸并段）寫到外部存儲(chǔ)器中（通常由一個(gè)可用的磁盤作為臨時(shí)緩沖區(qū)），這樣臨時(shí)緩沖區(qū)中的每個(gè)歸并段的內(nèi)容是有序的。
- 利用歸并算法，歸并第一階段生成的歸并段，直到只剩下一個(gè)歸并段為止。
1、將內(nèi)存空間劃分為三份，每份大小250個(gè)記錄，其中兩個(gè)用作輸入緩沖區(qū)，另外一個(gè)用作輸出緩沖區(qū)。首先對(duì)Segment_1和Segment_2進(jìn)行歸并，先從每個(gè)歸并段中讀取250個(gè)記錄到輸入緩沖區(qū)，對(duì)其歸并，歸并結(jié)果放到輸出緩沖區(qū)，當(dāng)輸出緩沖區(qū)滿后，將其寫到臨時(shí)緩沖區(qū)（由一個(gè)可用的磁盤充當(dāng)）內(nèi)，如果某個(gè)輸入緩沖區(qū)空了，則從相應(yīng)的歸并段中再讀取250個(gè)記錄進(jìn)行繼續(xù)歸并，反復(fù)以上步驟，直至Segment_1和Segment_2全都排好序，形成一個(gè)大小為1500的記錄，然后對(duì)Segment_3和Segment_4、Segment_5和Segment_6進(jìn)行同樣的操作。
2、對(duì)歸并好的大小為1500的記錄進(jìn)行如同步驟1一樣的操作，進(jìn)行繼續(xù)排序，直至最后形成大小為4500的歸并段，至此，排序結(jié)束。
排序算法總結(jié)
算法的穩(wěn)定性
- 穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
- 不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會(huì)出現(xiàn)在b的后面；
排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再?gòu)牧硪粋€(gè)鍵上排序，前一個(gè)鍵排序的結(jié)果可以為后一個(gè)鍵排序所用。
算法的復(fù)雜度
算法的復(fù)雜度往往取決于數(shù)據(jù)的規(guī)模大小和數(shù)據(jù)本身分布性質(zhì)。
- 時(shí)間復(fù)雜度： 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
- 空間復(fù)雜度：對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。
- 常見(jiàn)復(fù)雜度由小到大：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)(占用空間)為一個(gè)常數(shù)，則復(fù)雜度為O(1)；
當(dāng)一個(gè)算法的復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，可表示為O(log n)；
當(dāng)一個(gè)算法的復(fù)雜度與n成線性比例關(guān)系時(shí)，可表示為O (n)，依次類推。
時(shí)間復(fù)雜度記憶
- 冒泡、選擇、插入排序需要兩個(gè)for循環(huán)，每次只關(guān)注一個(gè)元素，平均時(shí)間復(fù)雜度為O(n的平方)（一遍找元素O(n)，一遍找位置O(n)）
- 快速、歸并、堆基于分治思想，log以2為底，平均時(shí)間復(fù)雜度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相關(guān)
- 而希爾排序依賴于所取增量序列的性質(zhì)，但是到目前為止還沒(méi)有一個(gè)最好的增量序列 。例如希爾增量序列時(shí)間復(fù)雜度為O(n2)，而Hibbard增量序列的希爾排序的時(shí)間復(fù)雜度為O(n3/2次方) ， 有人在大量的實(shí)驗(yàn)后得出結(jié)論;當(dāng)n在某個(gè)特定的范圍后希爾排序的最小時(shí)間復(fù)雜度大約為n^1.3。
從平均時(shí)間來(lái)看，快速排序是效率最高的：
- 快速排序中平均時(shí)間復(fù)雜度O(nlog n)，這個(gè)公式中隱含的常數(shù)因子很小，比歸并排序的O(nlog n)中的要小很多，所以大多數(shù)情況下，快速排序總是優(yōu)于合并排序的。
- 而堆排序的平均時(shí)間復(fù)雜度也是O(nlog n)，但是堆排序存在著重建堆的過(guò)程，它把根節(jié)點(diǎn)移除后，把最后的葉子結(jié)點(diǎn)拿上來(lái)后需要重建堆，但是，拿上的值是要比它的兩個(gè)葉子結(jié)點(diǎn)要差很多的，一般要比較很多次，才能回到合適的位置。堆排序就會(huì)有很多的時(shí)間耗在堆調(diào)整上。
- 雖然快速排序的最壞情況為排序規(guī)模（n）的平方關(guān)系，但是這種最壞情況取決于每次選擇的基準(zhǔn)， 對(duì)于這種情況，已經(jīng)提出了很多優(yōu)化的方法，比如三取樣劃分和Dual-Pivot快排。 同時(shí)，當(dāng)排序規(guī)模較小時(shí)，劃分的平衡性容易被打破，而且頻繁的方法調(diào)用超過(guò)了O(nlog n)為O(n的平方)省出的時(shí)間，所以一般排序規(guī)模較小時(shí)，會(huì)改用插入排序或者其他排序算法。
