1. 冒泡排序

來源百度百科:

冒泡排序(Bubble Sort，臺(tái)灣譯為:泡沫排序或氣泡排序)是一種簡單的排序算法苍姜。它重復(fù)地走 訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來医咨。走訪數(shù)列的工 作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換枫匾，也就是說該數(shù)列已經(jīng)排序完成架诞。這個(gè)算法的名字由來是因 為越大的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名干茉。

算法描述:

1. i從0開始谴忧，i與i+1比較，如果i>i+1角虫，那么就互換
2. i不斷增加沾谓，直到i<n-1(n是數(shù)組元素的個(gè)數(shù)，n-1是數(shù)組已經(jīng)最后一個(gè)元素)戳鹅，一趟下來均驶，可以讓數(shù)組元素中最大值排在數(shù)組的最后面

從最簡單開始，首先我們創(chuàng)建一個(gè)數(shù)組枫虏，該數(shù)組有5位數(shù)字：

int[] arrays = {2, 5, 1, 3, 4};

1. 第一趟排序
   下面我們根據(jù)算法的描述來進(jìn)行代碼驗(yàn)算(第一趟排序):

//使用臨時(shí)變量妇穴，讓兩個(gè)數(shù)互換 
int temp;
//第一位和第二位比
if (arrays[0] > arrays[1]) {
//交換
temp = arrays[0]; 
arrays[0] = arrays[1]; 
arrays[1] = temp;
}

 
//第二位和第三位比
if (arrays[1] > arrays[2]) {
temp = arrays[1]; 
arrays[1] = arrays[2]; 
arrays[2] = temp;
}
//第三位和第四位比
if (arrays[2] > arrays[3]) {
temp = arrays[2]; 
arrays[2] = arrays[3]; 
arrays[3] = temp;
}
//第四位和第五位比
if (arrays[3] > arrays[4]) {
temp = arrays[3]; 
arrays[3] = arrays[4]; 
arrays[4] = temp;
}

如果前一位的數(shù)比后一位的數(shù)要大爬虱，那么就交換，直到將數(shù)組的所有元素都比較了一遍! 經(jīng)過我們第一趟比較腾它，我們可以發(fā)現(xiàn):最大的值就在數(shù)組的末尾了!

image.png

2. 第二趟排序
   第二趟排序跟第一趟排序一樣跑筝，也是用前一位與后一位比較，如果前一位比后一位要大瞒滴，那就交換曲梗。值 得注意的是：并不需要與最后一位比較了，因?yàn)樵诘谝惶伺判蛲炅思巳蹋詈笠晃灰呀?jīng)是最大的數(shù)了虏两。同理，我們第二趟排序完了之后单默，倒數(shù)第二位也是第二大的數(shù)了碘举。

第二趟排序的代碼如下:

//第一位和第二位比
if (arrays[0] > arrays[1]) {
//交換
temp = arrays[0]; 
arrays[0] = arrays[1]; 
arrays[1] = temp;
}
//第二位和第三位比
if (arrays[1] > arrays[2]) {
 
temp = arrays[1]; arrays[1] = arrays[2]; arrays[2] = temp;
}
//第三位和第四位比
if (arrays[2] > arrays[3]) {
temp = arrays[2]; arrays[2] = arrays[3]; arrays[3] = temp;
}
//第四位不需要和第五位比了，因?yàn)樵诘谝惶伺判蚪Y(jié)束后搁廓，第五位是最大的了

結(jié)果:我們的第二大數(shù)已經(jīng)排在了倒數(shù)第二位了

image.png

3. 代碼簡化
   值得說明的是：上面的結(jié)果看起來已經(jīng)是排序好的了引颈，其實(shí)是我在測試時(shí)數(shù)據(jù)還不足夠亂，如果數(shù)據(jù)足夠亂的話境蜕，是需要4(n-1)趟排序的蝙场！

但我們從上面的代碼就可以發(fā)現(xiàn):第一趟和第二趟的比較、交換代碼都是重復(fù)的粱年，并且我們的比較都是
寫死的(0,1,2,3,4)售滤，并不通用!

我們的數(shù)組有5位數(shù)字
第一趟需要比較4次
第二趟需要比較3次

我們可以根據(jù)上面規(guī)律推斷出:
第三趟需要比較2次
第四躺需要比較1次

再從上面的規(guī)律可以總結(jié)出：**5位數(shù)的數(shù)組需要4躺排序的，每躺排序之后次數(shù)減1(因?yàn)榍耙惶艘呀?jīng)把前一趟數(shù)的最大值確定下來了)台诗！ **
于是我們可以根據(jù)for循環(huán)和變量將上面的代碼進(jìn)行簡化:

int temp; 
//外層循環(huán)是排序的趟數(shù)
for (int i = 0; i < arrays.length - 1 ; i++) {
//內(nèi)層循環(huán)是當(dāng)前趟數(shù)需要比較的次數(shù)
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位與后一位與前一位比較完箩，如果前一位比后一位要大，那么交換 
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j]; 
arrays[j] = arrays[j + 1]; 
arrays[j + 1] = temp;
} 
}
}

4. 冒泡排序優(yōu)化
   從上面的例子我們可以看出來拉队，如果數(shù)據(jù)足夠亂的情況下是需要經(jīng)過4躺比較才能將數(shù)組完整排好序弊知。

但是我們在第二躺比較后就已經(jīng)得到排好序的數(shù)組了。
但是粱快，我們的程序在第二趟排序后仍會(huì)執(zhí)行第三趟秩彤、第四趟排序。這是沒有必要的事哭，因此我們可以對其 進(jìn)行優(yōu)化一下:

如果在某躺排序中沒有發(fā)生交換位置漫雷，那么我們可以認(rèn)為該數(shù)組已經(jīng)排好序了。 這也不難理解鳍咱，因?yàn)槲覀兠刻伺判虻哪康木褪菍?dāng)前趟最大的數(shù)置換到對應(yīng)的位置上降盹，沒有發(fā)生置換說明就已經(jīng)排好序了。

代碼如下：

//裝載臨時(shí)變量 
int temp;
//記錄是否發(fā)生了置換谤辜， 0 表示沒有發(fā)生置換蓄坏、 1 表示發(fā)生了置換 
int isChange;
//外層循環(huán)是排序的趟數(shù)
for (int i = 0; i < arrays.length - 1; i++) {
    //每比較一趟就重新初始化為0 
    isChange = 0;
    //內(nèi)層循環(huán)是當(dāng)前趟數(shù)需要比較的次數(shù)
    for (int j = 0; j < arrays.length - i - 1; j++) {
    //前一位與后一位與前一位比較仅胞，如果前一位比后一位要大，那么交換 
    if (arrays[j] > arrays[j + 1]) {
            temp = arrays[j]; 
            arrays[j] = arrays[j + 1]; 
            arrays[j + 1] = temp;
            //如果進(jìn)到這里面了剑辫，說明發(fā)生置換了 
            isChange = 1; 
} 
}
    //如果比較完一趟沒有發(fā)生置換干旧，那么說明已經(jīng)排好序了，不需要再執(zhí)行下去了
    if (isChange == 0) {
    break; 
}
}

2. 選擇排序

選擇排序介紹和穩(wěn)定性說明
來源百度百科：

選擇排序(Selection sort)是一種簡單直觀的排序算法妹蔽。它的工作原理是每一次從待排序的數(shù)據(jù)元 素中選出最小(或最大)的一個(gè)元素椎眯，存放在序列的起始(末尾)位置，直到全部待排序的數(shù)據(jù)元素排 完胳岂。選擇排序是不穩(wěn)定的排序方法(比如序列[5编整， 5， 3]第一次就將第一個(gè)[5]與[3]交換乳丰，導(dǎo)致第 一個(gè)5挪動(dòng)到第二個(gè)5后面)掌测。

上面提到了選擇排序是不穩(wěn)定的排序方法，那我們的冒泡排序是不是穩(wěn)定的排序方法呢?穩(wěn)定的意思指的是什么呢?
判斷某排序算法是否穩(wěn)定产园，我們可以簡單理解成：排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同

• 如果相同汞斧，則是穩(wěn)定的排序方法。
• 如果不相同什燕，則是不穩(wěn)定的排序方法

如果排序前的數(shù)組是 [3,3,1] 粘勒，假定我們使用選擇排序的話，那第一趟排序后結(jié)果就是 [1,3,3] 屎即。這 個(gè)數(shù)組有兩個(gè)相同的值庙睡，它倆在 array[0] 和 array[1] ，結(jié)果經(jīng)過排序技俐， array[0] 的跑到了array[2] 上了乘陪。

那么這就導(dǎo)致:2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序不相同，因此雕擂，我們就說它是不穩(wěn)定的

再回到上面的問題啡邑，上一篇說講的冒泡排序是穩(wěn)定的，主要原因是：倆倆比較的時(shí)候捂刺，沒有對相等的數(shù)據(jù)進(jìn)行交換(因?yàn)闆]必要)谣拣。因此它不存在2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序不相同募寨。

那么穩(wěn)定排序的好處是什么?
參考知乎回答@獨(dú)行俠的回答:

如果我們只對一串?dāng)?shù)字排序族展，那么穩(wěn)定與否確實(shí)不重要，因?yàn)橐淮當(dāng)?shù)字的屬性是單一的拔鹰，就是數(shù) 字值的大小仪缸。但是排序的元素往往不只有一個(gè)屬性，例如我們對一群人按年齡排序列肢，但是人除了 年齡屬性還有身高體重屬性恰画，在年齡相同時(shí)如果不想破壞原先身高體重的次序宾茂，就必須用穩(wěn)定排 序算法.
很清晰的指出，只有當(dāng)在“二次”排序時(shí)不想破壞原先次序拴还，穩(wěn)定性才有意義

1. 第一趟排序
   它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素跨晴，存放在序列的起始(末尾)位 置，直到全部待排序的數(shù)據(jù)元素排完

首先片林，我們創(chuàng)建數(shù)組端盆，找到它最大的值(這就很簡單了):

int[] arrays = {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3}; 
//假定max是最大的
int max = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] > max) {
max = arrays[i]; }
}

效果如下:

image.png

隨后這個(gè)最大的數(shù)和數(shù)組末尾的數(shù)進(jìn)行交換:

//使用臨時(shí)變量，讓兩個(gè)數(shù)互換 i
nt temp;
temp = arrays[11]; 
arrays[11] = arrays[13]; 
arrays[13] = temp;

那么經(jīng)過第一趟排序费封，我們的最大值已經(jīng)到了數(shù)組的末尾了焕妙。

image.png

2. 第二趟排序
   再次從數(shù)組獲取最大的數(shù)(除了已經(jīng)排好的那個(gè)):

int max2 = 0;
for (int i = 0; i < (arrays.length - 1); i++) {
if (arrays[i] > max2) { 
max2 = arrays[i];
} 
}
System.out.println(max2);

效果如下:

image.png

再將獲取到的最大值與數(shù)組倒數(shù)第二位交換:

temp = arrays[7]; 
arrays[7] = arrays[12]; 
arrays[12] = temp;

經(jīng)過第二次排序，已經(jīng)能夠?qū)?shù)組最大兩個(gè)數(shù)進(jìn)行排序了

image.png

代碼簡化
從前兩趟排序其實(shí)我們就可以摸出規(guī)律了:

• 一個(gè)數(shù)組是需要 n-1 趟排序的(因?yàn)橹钡绞Ｏ乱粋€(gè)元素時(shí)弓摘，才不需要找最大值)
• 每交換1次焚鹊，再次找最大值時(shí)就將范圍縮小1
• 查詢當(dāng)前趟數(shù)最大值實(shí)際上不用知道最大值是多少(上面我查出最大值，還要我手動(dòng)數(shù)它的?標(biāo))韧献， 知道它的數(shù)組?標(biāo)即可末患，交換也是根據(jù)?標(biāo)來進(jìn)行交換

第一趟:遍歷數(shù)組14個(gè)數(shù)，獲取最大值锤窑，將最大值放到數(shù)組的末尾 [13]
第二趟:遍歷數(shù)組13個(gè)數(shù)阻塑，獲取最大值，將最大值放到數(shù)組倒數(shù)第二位 [12]
....
數(shù)組有14個(gè)數(shù)果复，需要13趟排序陈莽。

//記錄當(dāng)前趟數(shù)的最大值的?標(biāo) 
int pos ;
//交換的變量 
int temp;
//外層循環(huán)控制需要排序的趟數(shù)
for (int i = 0; i < arrays.length - 1; i++) {
//新的趟數(shù)、將?標(biāo)重新賦值為0 
pos = 0;
//內(nèi)層循環(huán)控制遍歷數(shù)組的個(gè)數(shù)并得到最大數(shù)的?標(biāo)
for (int j = 0; j < arrays.length - i; j++) {
if (arrays[j] > arrays[pos]) { 
pos = j;
}
 }
 
//交換
temp = arrays[pos];
arrays[pos] = arrays[arrays.length - 1 - i]; 
arrays[arrays.length - 1 - i] = temp;
}
System.out.println("Arrays" + arrays);

3. 插入排序

插入排序介紹
來源百度百科:

插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中虽抄，從而得到一個(gè)新的走搁、個(gè)數(shù) 加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序迈窟，時(shí)間復(fù)雜度為O(n^2)私植。是穩(wěn)定的排序方法。

將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中

將要排序的是一個(gè)亂的數(shù)組 int[] arrays = {3, 2, 1, 3, 3}; 在未知道數(shù)組元素的情況下车酣，我們只能把數(shù)組的第一個(gè)元素作為已經(jīng)排好序的有序數(shù)據(jù)曲稼，也就是說，把 {3} 看成是已經(jīng)排好序的有序數(shù)據(jù)

1. 第一趟排序
   用數(shù)組的第二個(gè)數(shù)與第一個(gè)數(shù)(看成是已有序的數(shù)據(jù))比較

• 如果比第一個(gè)數(shù)大湖员，那就不管他
• 如果比第一個(gè)數(shù)小贫悄，將第一個(gè)數(shù)往后退一步，將第二個(gè)數(shù)插入第一個(gè)數(shù)去

int temp;
if (arrays[1] > arrays[0]) {
//如果第二個(gè)數(shù)比第一個(gè)數(shù)大娘摔，直接跟上
} else { //如果第二個(gè)數(shù)比第一個(gè)數(shù)小窄坦，將第一個(gè)數(shù)后退一個(gè)位置(將第二個(gè)數(shù)插進(jìn)去) temp = arrays[1];
arrays[1] = arrays[0];
arrays[0] = temp;
}
System.out.println("公眾號(hào)Java3y" + arrays);

效果如下:

image.png

2. 第二趟排序
   用數(shù)組的第三個(gè)數(shù)與已是有序的數(shù)據(jù) {2,3} (剛才在第一趟排的)比較

• 如果比第二位的數(shù)大，那就不管它
• 如果比第二位的數(shù)小，那就將第二的位置退一個(gè)位置鸭津，讓第三個(gè)數(shù)和第一位比較
  如果第三個(gè)數(shù)比第一位大彤侍，那么將第三個(gè)數(shù)插入到第二的位置上 如果第三個(gè)數(shù)比第一位小，那么將第一位后退一步逆趋，將第三個(gè)數(shù)插入到第一的位置上

//第二趟排序-------------------- 
if (arrays[2] > arrays[1]) {
//如果第三個(gè)數(shù)比第二個(gè)數(shù)大盏阶，直接跟上
} else { 
//如果第三個(gè)數(shù)比第二個(gè)數(shù)小，將第二個(gè)數(shù)往后退一個(gè)位置闻书，讓第三個(gè)數(shù)跟第一個(gè)數(shù)比
temp = arrays[2];
arrays[2] = arrays[1];
//如果第三個(gè)數(shù)比第一個(gè)大般哼，那就插入到第二個(gè)數(shù)中 
if (temp > arrays[0]) {
arrays[1] = temp; } else {
//如果第三個(gè)數(shù)比第一個(gè)小，將第三個(gè)數(shù)插入到第一個(gè)數(shù)前面 int swapTemp = arrays[0];
arrays[0] = temp;
arrays[1] = swapTemp;
}
}
System.out.println("公眾號(hào)Java3y" + arrays);

效果如下:

image.png

簡化代碼
從前兩趟排序我們可以摸出的規(guī)律:

• 首先將已排序的數(shù)據(jù)看成一個(gè)整體
• 一個(gè)數(shù)組是需要 n-1 趟排序的惠窄，總是用后一位跟 已排序的數(shù)據(jù)比較(第一趟:第二位跟 已排序的數(shù) 據(jù) 比蒸眠，第二趟:第三位跟 已排序的數(shù)據(jù)比)
• 用第三位和 已排序的數(shù)據(jù) 比，實(shí)際上就是讓第三位數(shù)跟兩個(gè)數(shù)比較杆融，只不過這兩個(gè)數(shù)是已經(jīng)排好序 的而已楞卡。而正是因?yàn)樗藕眯虻模?strong>我們可以使用一個(gè)循環(huán)就可以將我們比較的數(shù)據(jù)插入進(jìn)去

for (int i = 1; i < arrays.length; i++) { 
temp = arrays[i];
//如果前一位(已排序的數(shù)據(jù))比當(dāng)前數(shù)據(jù)要大，那么就進(jìn)入循環(huán)比較[參考第二趟排序] int j = i - 1;
while (j >= 0 && arrays[j] > temp) { 
//往后退一個(gè)位置脾歇，讓當(dāng)前數(shù)據(jù)與之前前位進(jìn)行比較
arrays[j + 1] = arrays[j]; 
//不斷往前蒋腮，直到退出循環(huán)
j--;
}
//退出了循環(huán)說明找到了合適的位置了，將當(dāng)前數(shù)據(jù)插入合適的位置中 
arrays[j + 1] = temp;
}
System.out.println("公眾號(hào)Java3y" + arrays);

4. 快速排序

快速排序的介紹
來源百度百科:

快速排序由C. A. R. Hoare在1962年提出藕各。它的基本思想是:通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成 獨(dú)立的兩部分池摧，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這 兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序激况，整個(gè)排序過程可以遞歸進(jìn)行作彤，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

快速排序是面試出現(xiàn)的可能性比較高的乌逐，也是經(jīng)常會(huì)用到的一種排序竭讳，應(yīng)該重點(diǎn)掌握。 前面一個(gè)章節(jié)已經(jīng)講了遞歸了浙踢，那么現(xiàn)在來看快速排序就非常簡單了.

1. 第一趟快速排序
   通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分绢慢，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小
   百度百科的話并沒有說到重點(diǎn)，更簡單的理解是這樣的：在數(shù)組中找一個(gè)支點(diǎn)(任意),經(jīng)過一趟排序后洛波， 支點(diǎn)左邊的數(shù)都要比支點(diǎn)小胰舆，支點(diǎn)右邊的數(shù)都要比支點(diǎn)大!

現(xiàn)在我們有一個(gè)數(shù)組: int arr[]={1,4,5,67,2,7,8,6,9,44};
經(jīng)過一趟排序之后，如果我選擇數(shù)組中間的數(shù)作為支點(diǎn):7(任意的)蹬挤，那么第一趟排序后的結(jié)果是這樣的: {1,4,5,6,2,7,8,67,9,44}
那么就實(shí)現(xiàn)了支點(diǎn)左邊的數(shù)比支點(diǎn)小缚窿，支點(diǎn)右邊的數(shù)比支點(diǎn)大

2. 遞歸分析與代碼實(shí)現(xiàn)
   現(xiàn)在我們的數(shù)組是這樣的: {1,4,5,6,2,7,8,67,9,44} ，既然我們比7小的在左邊闻伶，比7大的在右邊滨攻， 那么我們只要將”左邊“的排好順序够话，又將”右邊“的排好序蓝翰，那整個(gè)數(shù)組是不是就有序了?想一想光绕，是不是?

又回顧一下遞歸:”左邊“的排好順序，”右邊“的排好序畜份，跟我們第一趟排序的做法是不是一致的?

只不過是參數(shù)不一樣：第一趟排序是任選了一個(gè)支點(diǎn)诞帐，比支點(diǎn)小的在左邊咳燕，比支點(diǎn)大的在右邊憔披。那么，我們想要”左邊“的排好順序雷滚，只要在”左邊“部分找一個(gè)支點(diǎn)钙态，比支點(diǎn)小的在左邊慧起，比支點(diǎn)大的在右邊
..............
在數(shù)組中使用遞歸依照我的慣性，往往定義兩個(gè)變量: L 和 R 册倒， L 指向第一個(gè)數(shù)組元素蚓挤， R 指向在最后 一個(gè)數(shù)組元素

遞歸出口也很容易找到：如果數(shù)組只有一個(gè)元素時(shí)，那么就不用排序了所以驻子，我們可以寫出這樣的代碼:

public static void main(String[] args) {
int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44};
quickSort(arr, 0, 9); 
System.out.println("arr" + arr);
}
/**
* 快速排序
*
* @param arr
* @param L 指向數(shù)組第一個(gè)元素 
* @param R 指向數(shù)組最后一個(gè)元素
*/

public static void quickSort(int[] arr, int L, int R) { 
int i = L;
int j = R; 
//支點(diǎn)
int pivot = arr[(L + R) / 2]; 
//左右兩端進(jìn)行掃描灿意，只要兩端還沒有交替，就一直掃描
while (i <= j) {
//尋找直到比支點(diǎn)大的數(shù) 
while (pivot > arr[i])
          i++;
//尋找直到比支點(diǎn)小的數(shù) 
while (pivot < arr[j])
          j--;
//此時(shí)已經(jīng)分別找到了比支點(diǎn)小的數(shù)(右邊)崇呵、比支點(diǎn)大的數(shù)(左邊)缤剧，它們進(jìn)行交換 
if (i <= j) {
int temp = arr[i]; 
arr[i] = arr[j]; 
arr[j] = temp; 
i++;
j--; 
}
}
//上面一個(gè)while保證了第一趟排序支點(diǎn)的左邊比支點(diǎn)小，支點(diǎn)的右邊比支點(diǎn)大了域慷。
//“左邊”再做排序荒辕，直到左邊剩下一個(gè)數(shù)(遞歸出口) 
if (L < j)
    quickSort(arr, L, j);
//“右邊”再做排序，直到右邊剩下一個(gè)數(shù)(遞歸出口) 
if (i < R)
    quickSort(arr, i, R);
 }

效果如下:

image.png

5. 歸并排序

來源百度百科:

歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法 (Divide and Conquer)的一個(gè)非常典型的應(yīng)用犹褒。將已有序的子序列合并兄纺，得到完全有序的序 列;即先使每個(gè)子序列有序，再使子序列段間有序化漆。若將兩個(gè)有序表合并成一個(gè)有序表估脆，稱為二 路歸并。

過程描述:

歸并過程為:比較a[i]和b[j]的大小座云，若a[i]≤b[j]疙赠，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并 令i和k分別加上1;否則將第二個(gè)有序表中的元素b[j]復(fù)制到r[k]中朦拖，并令j和k分別加上1圃阳，如此循 環(huán)下去，直到其中一個(gè)有序表取完璧帝，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下 標(biāo)t的單元捍岳。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊 子區(qū)間排序锣夹，再把右邊子區(qū)間排序页徐，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間 [s,t]。

原理:
歸并操作的工作原理如下:

• 第一步:申請空間银萍，使其大小為兩個(gè)已經(jīng)排序序列之和变勇，該空間用來存放合并后的序列
• 第二步:設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
• 第三步:比較兩個(gè)指針?biāo)赶虻脑靥剑x擇相對小的元素放入到合并空間搀绣，并移動(dòng)指針到下一位置
• 重復(fù)步驟3直到某一指針超出序列尾
• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

下面我就來做個(gè)小小的總結(jié):
將兩個(gè)已排好序的數(shù)組合并成一個(gè)有序的數(shù)組,稱之為歸并排序
步驟：遍歷兩個(gè)數(shù)組，比較它們的值戳气。誰比較小链患，誰先放入大數(shù)組中，直到數(shù)組遍歷完成

1. 演算歸并排序過程
   現(xiàn)在我有兩個(gè)已經(jīng)排好順序的數(shù)組: int[] arr1 = {2, 7, 8} 和 int[] arr2 = {1, 4, 9} 瓶您，我還 有一個(gè)大數(shù)組來裝載它們 int[] arr = new int[6];
   1.1 第一步
   那么锣险，我將兩個(gè)數(shù)組的值進(jìn)行比較，誰的值比較小览闰，誰就放入大數(shù)組中!
   首先芯肤，拿出 arr1[0] 和 arr2[0] 進(jìn)行比較，顯然是 arr2[0] 比較小压鉴，因此將 arr2[0] 放入大數(shù)組中崖咨， 同時(shí) arr2 指針往后一格
   所以，現(xiàn)在目前為止 arr = {1}

1.2 第二步
隨后油吭，拿 arr1[0] 和 arr2[1] 進(jìn)行比較击蹲，顯然是 arr1[0] 比較小，將 arr1[0] 放入大數(shù)組中婉宰，同時(shí) arr1 指針往后一格
所以歌豺，現(xiàn)在目前為止 arr = {1,2}

1.3 第三步
隨后，拿 arr1[1] 和 arr2[1] 進(jìn)行比較心包，顯然是 arr2[1] 比較小类咧，將 arr2[1] 放入大數(shù)組中，同時(shí) arr2 指針往后一格
所以蟹腾，現(xiàn)在目前為止 arr = {1,2,4}
........
遍歷到最后痕惋，我們會(huì)將兩個(gè)已排好序的數(shù)組變成一個(gè)已排好序的數(shù)組 arr = {1,2,4,7,8,9}

2. 歸并排序前提分析(分治法)
   從上面的演算我們就直到，歸并排序的前提是需要兩個(gè)已經(jīng)排好順序的數(shù)組娃殖，那往往不會(huì)有兩個(gè)已經(jīng)排
   好順序的數(shù)組給我們的呀(一般是雜亂無章的一個(gè)數(shù)組)值戳，那這個(gè)算法是不是很雞肋的呢??

其實(shí)并不是的，首先假設(shè)題目給出的數(shù)組是這樣子的: int[] arr = {2, 7, 8, 1, 4, 9};

當(dāng)我們要做歸并的時(shí)候就以 arr[3] 也就元素為1的那個(gè)地方分開炉爆。是然后用一個(gè) 指針L 指向 arr[0] 堕虹， 一個(gè) 指針M 指向 arr[3] 卧晓，用一個(gè) 指針R 指向 arr[5] (數(shù)組最后一位)。有了指針的幫助赴捞，我們就可以將 這個(gè)數(shù)組切割成是兩個(gè)有序的數(shù)組了(操作的方式就可以和上面一樣了)

可是上面說了逼裆，一般給出的是雜亂無章的一個(gè)數(shù)組，現(xiàn)在還是達(dá)不到要求螟炫。比如給出的是這樣一個(gè)數(shù) 組: int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};

此時(shí)波附，我們就得用到分治的思想了:

那么我們也可以這樣想將 int[] arr = {2, 7, 8, 1, 4, 9}; 數(shù)組分隔成一份一份
的艺晴， arr[0] 它是一個(gè)有序的"數(shù)組", arr[1] 它也是一個(gè)有序的"數(shù)組",利用指針(L,M,R)又可以像操 作兩個(gè)數(shù)組一樣進(jìn)行排序昼钻。最終合成 {2,7} .......再不斷拆分合并，最后又回到了我們的 arr = {1,2,4,7,8,9} 封寞，因此歸并排序是可以排序雜亂無章的數(shù)組的

這就是我們的分治法--->將一個(gè)大問題分成很多個(gè)小問題進(jìn)行解決然评，最后重新組合起來

3. 歸并代碼實(shí)現(xiàn)
   實(shí)現(xiàn)步驟:
4. 拆分
5. 合并 ........

 
public static void main(String[] args) {
int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8}; mergeSort(arrays, 0, arrays.length - 1);
System.out.println("公眾號(hào):Java3y" + arrays); }
/**
* 歸并排序
*
* @param arrays
* @param L
* @param R */
指向數(shù)組第一個(gè)元素 指向數(shù)組最后一個(gè)元素
public static void mergeSort(int[] arrays, int L, int R) {
//如果只有一個(gè)元素，那就不用排序了
 if (L == R) {
        return;
    } else {
//取中間的數(shù)狈究，進(jìn)行拆分 
int M = (L + R) / 2;
//左邊的數(shù)不斷進(jìn)行拆分 
mergeSort(arrays, L, M);
//右邊的數(shù)不斷進(jìn)行拆分 
mergeSort(arrays, M + 1, R);
//合并
merge(arrays, L, M + 1, R);
 }
 }

/**
* 合并數(shù)組
*
* @param arrays
* @param L
* @param M
* @param R */
指向數(shù)組第一個(gè)元素 指向數(shù)組分隔的元素 指向數(shù)組最后的元素
public static void merge(int[] arrays, int L, int M, int R) { //左邊的數(shù)組的大小
int[] leftArray = new int[M - L];
//右邊的數(shù)組大小
int[] rightArray = new int[R - M + 1];
//往這兩個(gè)數(shù)組填充數(shù)據(jù)
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i]; }
for (int i = M; i <= R; i++) { rightArray[i - M] = arrays[i];
}
int i = 0, j = 0;
// arrays數(shù)組的第一個(gè)元素 
int k=L;
//比較這兩個(gè)數(shù)組的值碗淌，哪個(gè)小，就往數(shù)組上放
while (i < leftArray.length && j < rightArray.length) {
//誰比較小抖锥，誰將元素放入大數(shù)組中,移動(dòng)指針亿眠，繼續(xù)比較下一個(gè) if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j]; j++;
k++;
} 
}
 
//如果左邊的數(shù)組還沒比較完，右邊的數(shù)都已經(jīng)完了磅废，那么將左邊的數(shù)抄到大數(shù)組中(剩下的都 是大數(shù)字)
while (i < leftArray.length) { arrays[k] = leftArray[i]; i++;
k++;
}
//如果右邊的數(shù)組還沒比較完纳像，左邊的數(shù)都已經(jīng)完了，那么將右邊的數(shù)抄到大數(shù)組中(剩下的都 是大數(shù)字)
while (j < rightArray.length) { 
arrays[k] = rightArray[j]; 
k++;
j++;
} 
}

6. 希爾排序介紹

來源百度百科:

希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”(Diminishing Increment Sort)拯勉， 是直接插入排序算法的一種更高效的改進(jìn)版本竟趾。希爾排序是非穩(wěn)定排序算法。該方法因D.L.Shell 于1959年提出而得名宫峦。
從上面我們很容易看出來岔帽，它是插入排序的高級版
從直觀上看希爾排序:
就是把數(shù)列進(jìn)行分組(不停使用插入排序)，直至從宏觀上看起來有序导绷，最后插入排序起來就容易了 (無須多次移位或交換)犀勒。*

那么，上面那里說了將一個(gè)序列分成好幾個(gè)序列妥曲，那么到底怎么分呢?比如有10個(gè)元素的序列账蓉，分成幾 個(gè)才合適?每次縮減又是多少呢?

從專業(yè)的?度上講，將一個(gè)序列分成好幾個(gè)序列逾一，用一個(gè)數(shù)來表示:那個(gè)數(shù)稱為增量铸本。顯然的是，增量 是不斷遞減的(直到增量為1)

往往的:如果一個(gè)數(shù)列有10個(gè)元素遵堵，我們第一趟的增量是5箱玷，第二趟的增量是2怨规，第三趟的增量是1。如 果一個(gè)數(shù)列有18個(gè)元素锡足，我們第一趟的增量是9波丰，第二趟的增量是4，第三趟的增量是2舶得，第四趟的增量 是1

很明顯我們可以用一個(gè)序列來表示增量: {n/2,(n/2)/2...1} 掰烟，每次增量都 /2

2. 希爾排序體驗(yàn)
   現(xiàn)在我們有一個(gè)數(shù)組，該數(shù)組有6個(gè)元素

 int[] arrays = {2, 5, 1, 3, 4, 6};

排序前:

• 將該數(shù)組看成三個(gè)(arrays.length/2)數(shù)組沐批，分別是: {2,3} , {5,4} , {1,6}
  第一趟排序:
• 對三個(gè)數(shù)組分別進(jìn)行插入排序纫骑，因此我們?nèi)齻€(gè)數(shù)組得到的結(jié)果為 {2,3} , {4,5} , {1,6} 此時(shí)數(shù)組是這樣子的: {2, 4, 1, 3, 5, 6}

第二趟排序:
增量減少了，上面增量是3九孩，此時(shí)增量應(yīng)該為1了先馆，因此把 {2, 4, 1, 3, 5, 6} 看成一個(gè)數(shù)組(從宏觀上是有序的了)，對其進(jìn)行插入排序躺彬，直至有序

image.png

image.png

image.png

image.png

7. 堆排序

1. 堆排序介紹
   來源百度百科:

堆排序(Heapsort)是指利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法煤墙，它是選擇排序的 一種∠苡担可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素仿野。堆分為大根堆和小根堆，是完全二叉樹她君。

前面我已經(jīng)有二叉樹入?的文章了脚作，當(dāng)時(shí)講解的是二叉查找樹，那上面所說的完全二叉樹是怎么樣的一 種二叉樹呢??還有滿二叉樹又是怎么的一種二叉樹呢??甚至還有完滿二叉樹??

• 完全二叉樹: 除了最后一層之外的其他每一層都被完全填充犁河，并且所有結(jié)點(diǎn)都保持 -向左對?鳖枕。

  
  
  image.png

• 滿二叉樹:除了葉子
  結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，每一層(當(dāng)然包含最后一層)都被完全填充桨螺。

  
  
  image.png

• 完滿二叉樹:除了葉子結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)宾符。

  
  
  image.png

簡單來說:堆排序是將數(shù)據(jù)看成是完全二叉樹、根據(jù)完全二叉樹的特性來進(jìn)行排序的一種算法

• 最大堆要求節(jié)點(diǎn)的元素都要不小于其孩子灭翔，最小堆要求節(jié)點(diǎn)元素都不大于其左右孩子
• 那么處于最大堆的根節(jié)點(diǎn)的元素一定是這個(gè)堆中的最大值

這里我們討論最大堆:當(dāng)前每個(gè)父節(jié)點(diǎn)都大于子節(jié)點(diǎn)

image.png

完全二叉樹有個(gè)特性: 左邊子節(jié)點(diǎn)位置 = 當(dāng)前父節(jié)點(diǎn)的兩倍 + 1 魏烫， 右邊子節(jié)點(diǎn)位置 = 當(dāng)前父節(jié)點(diǎn)的兩倍 +2

image.png

2. 堆排序體驗(yàn)
   現(xiàn)在我們有一個(gè)完全二叉樹:左子樹和右子樹都符合最大堆--> 父>子

   
   
   image.png

但是我們會(huì)發(fā)現(xiàn):根元素所在的數(shù)并不符合，明顯的是:1是小于7的

image.png

我們就對其進(jìn)行交換肝箱，交換完之后我們會(huì)發(fā)現(xiàn):右子樹又不符合了~
因?yàn)楹灏易訕渥兂闪诉@樣:

image.png

最后，我們將右子數(shù)的最大值也交換到右子樹的根元素上

image.png

于是我們第一次的建堆操作就完成了!

image.png

可以發(fā)現(xiàn)的是:一次堆建立完之后煌张，我們的最大值就在了堆的根節(jié)點(diǎn)上 隨后將堆頂最大值和數(shù)組最后的元素進(jìn)行替換呐赡，我們就完成了一趟排序了。

image.png

接下來骏融，剩下的數(shù)不斷進(jìn)行建堆链嘀，交換就可以完成我們的堆排序了

image.png

.........建堆萌狂，交換....建堆，交換...建堆怀泊，交換...建堆茫藏，交換..

3. 堆排序代碼實(shí)現(xiàn)
   比較當(dāng)前父節(jié)點(diǎn)是否大于子節(jié)點(diǎn)，如果大于就交換霹琼，直到一趟建堆完成~

/**
* 建堆 *
* @param arrays 看作是完全二叉樹
* @param currentRootNode 當(dāng)前父節(jié)點(diǎn)位置
* @param size 節(jié)點(diǎn)總數(shù) */
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) { 
//左子樹和右字?jǐn)?shù)的位置
int left = 2 * currentRootNode + 1; 
int right = 2 * currentRootNode + 2;
//把當(dāng)前父節(jié)點(diǎn)位置看成是最大的 
int max = currentRootNode;
if (left < size) { //如果比當(dāng)前根元素要大务傲，記錄它的位置
if (arrays[max] < arrays[left]) {
max = left; 
}
 }
if (right < size) {
//如果比當(dāng)前根元素要大，記錄它的位置
if (arrays[max] < arrays[right]) {
max = right; }
}
//如果最大的不是根元素位置枣申，那么就交換 
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//繼續(xù)比較售葡，直到完成一次建堆
 heapify(arrays, max, size);
        }
} }

值得注意的是:在上面體驗(yàn)堆排序時(shí)，我們是左子樹和右子數(shù)都是已經(jīng)有 父>子 這么一個(gè)條件的了糯而。

• 顯然天通，一個(gè)普通的數(shù)組并不能有這種條件(父>子)泊窘，因此熄驼，我們往往是從數(shù)組最后一個(gè)元素來進(jìn)行 建堆

 
/**
* 完成一次建堆，最大值在堆的頂部(根節(jié)點(diǎn)) */
public static void maxHeapify(int[] arrays, int size) {
// 從數(shù)組的尾部開始烘豹，直到第一個(gè)元素(?標(biāo)為0) 
for (int i = size - 1; i >= 0; i--) {
        heapify(arrays, i, size);
    }
}

完成第一次建堆之后瓜贾，其它下邊的分葉子節(jié)點(diǎn)都在自己該在的位置了，我們會(huì)發(fā)現(xiàn)最大值會(huì)在數(shù)組的首位:

image.png

public static void main(String[] args) {
int[] arrays = {6, 3, 8, 5,2,-1,-5,-2,-6,345,7, 5, 1, 2, 23, 4321,432,3,2,34234,2134,1234, 5, 132423, 234, 4, 2, 4, 1, 5, 2, 5};
// 完成一次建堆..
maxHeapify(arrays, arrays.length - 1); 
int size = arrays.length - 1;
for (int i = 0; i < arrays.length; i++) { 
//交換
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i]; 
arrays[(arrays.length - 1) - i] = temp;
// 調(diào)整位置 heapify(arrays, 0, size); 
size--;
}
System.out.println("Arrays：" + arrays); }
/**
* 完成一次建堆携悯，最大值在堆的頂部(根節(jié)點(diǎn))

*/
public static void maxHeapify(int[] arrays, int size) { for (int i = size - 1; i >= 0; i--) {
       heapify(arrays, i, size);
   }
}
/**
* 建堆 *
* @param arrays
* @param currentRootNode 當(dāng)前父節(jié)點(diǎn)位置
* @param size 節(jié)點(diǎn)總數(shù) */
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) { //左子樹和右字?jǐn)?shù)的位置
int left = 2 * currentRootNode + 1; int right = 2 * currentRootNode + 2;
//把當(dāng)前父節(jié)點(diǎn)位置看成是最大的 int max = currentRootNode;
if (left < size) { //如果比當(dāng)前根元素要大祭芦，記錄它的位置
if (arrays[max] < arrays[left]) {
max = left; }
       }
       if (right < size) {
//如果比當(dāng)前根元素要大，記錄它的位置
if (arrays[max] < arrays[right]) {
max = right; }
}
//如果最大的不是根元素位置憔鬼，那么就交換 if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode]; arrays[currentRootNode] = temp;
//繼續(xù)比較龟劲，直到完成一次建堆
           heapify(arrays, max, size);
       }
}
}

效果如下:

image.png

8. 基數(shù)排序(桶排序)

數(shù)排序不同與其他的7種排序，其他7種排序本 質(zhì)上都是按照交換或者比較來進(jìn)行排序轴或，但是基數(shù)排序并不是昌跌，它是按照分配，回收(分配到不同的位置 上照雁，然后回收)..不斷分配..回收來進(jìn)行排序蚕愤，直到有序..

過程

• 第一趟桶排序?qū)?shù)字的個(gè)位數(shù)分配到桶子里面去，然后回收起來饺蚊，此時(shí)數(shù)組元素的所有個(gè)位數(shù)都已 經(jīng)排好順序了
• 第二趟桶排序?qū)?shù)字的十位數(shù)分別分配到桶子里面去萍诱，然后回收起來，此時(shí)數(shù)組元素的所有個(gè)位數(shù) 和十位數(shù)都已經(jīng)排好順序了(如果沒有十位數(shù)污呼、則補(bǔ)0)
• 第三趟桶排序?qū)?shù)字的百位數(shù)分別分配到桶子里面去裕坊，然后回收起來，此時(shí)數(shù)組元素的所有個(gè)位數(shù) 和十位數(shù)和百位數(shù)都已經(jīng)排好順序了(如果沒有百位數(shù)燕酷、則補(bǔ)0)
• ..................................
• 直至全部數(shù)(個(gè)籍凝、十映企、百、千位...)排好順序静浴，那么這個(gè)數(shù)組就是有序的了堰氓。

image.png

關(guān)于這個(gè)桶我們可以用二維數(shù)組來進(jìn)行存放。 10個(gè)桶子就是10列苹享，如果分配時(shí)有的數(shù)字相同的話双絮，那么就弄成多行~

2. 基數(shù)排序體驗(yàn)
   首先我們有以下這個(gè)數(shù)組:
   int[] arrays = {6, 4322, 432, 344, 55 };
   現(xiàn)在我們有10個(gè)桶子，每個(gè)桶子下能裝載 arrays.length 個(gè)數(shù)字..
   int[][] buckets = new int[arrays.length][10];
   效果如下:

   
   
   image.png

2.1 第一趟分配與回收
將數(shù)組的每個(gè)個(gè)位數(shù)進(jìn)行分配到不同的桶子上:

image.png

分配完之后得问，我們按照順序來進(jìn)行回收:得到的結(jié)果應(yīng)該是這樣子的: {4322,432,344,55,6}

2.2 第二趟分配與回收
將數(shù)組的每個(gè)十位數(shù)進(jìn)行分配到不同的桶子上(像6這樣的數(shù)囤攀，往前邊補(bǔ)0):
于是我們可以得到這樣的排序:

image.png

2.3 第三趟分配與回收
將數(shù)組的每個(gè)百位數(shù)進(jìn)行分配到不同的桶子上(像6、55這樣的數(shù)宫纬，往前邊補(bǔ)0):
于是我們可以得到這樣的排序:

image.png

分配完之后焚挠，我們按照順序來進(jìn)行回收:得到的結(jié)果應(yīng)該是這樣子的: {6,55,4322,344,432}

2.4 第四趟分配與回收
將數(shù)組的每個(gè)百位數(shù)進(jìn)行分配到不同的桶子上(像6、55漓骚，344蝌衔，432這樣的數(shù)，往前邊補(bǔ)0):
于是我們可以得到這樣的排序:

image.png

分配完之后蝌蹂，我們按照順序來進(jìn)行回收:得到的結(jié)果應(yīng)該是這樣子的: {6,55,344,432,4322}
此時(shí)我們的數(shù)組就已經(jīng)可以排好序了~~~過程就是這樣子噩斟，其實(shí)不難就只有兩個(gè)步驟:

• 將數(shù)組的每一位放進(jìn)桶子里
• 回收
• 循環(huán)......

3. 基數(shù)排序代碼編寫
   我們的基數(shù)排序是按照個(gè)、十孤个、百剃允、千位...來進(jìn)行存放的。前面的演示是已經(jīng)知道數(shù)組元素的數(shù)據(jù)的情 況下來進(jìn)行存放齐鲤，但是一般我們是不去理會(huì)數(shù)組內(nèi)元素的值的斥废。那如果位數(shù)很多(萬位)或者都是個(gè)位 數(shù)，這個(gè)條件我們怎么去處理呢?

我們可以這樣做:先求出數(shù)組最大的值给郊，然后不斷/10牡肉，只要它能大于0，那么它的位數(shù)還有~:
3.1 求出數(shù)組最大的值
這個(gè)我在前面寫遞歸的時(shí)候就有這個(gè)代碼了丑罪，我就直接搬去遞歸的代碼過來了荚板，順便復(fù)習(xí)一哈吧:
當(dāng)然了，更好的是直接用for循環(huán)來找出來就行了(易讀性好一些)

/**
* 遞歸吩屹，找出數(shù)組最大的值
* @param arrays 數(shù)組
* @param L 左邊界跪另，第一個(gè)數(shù)
* @param R 右邊界，數(shù)組的?度 * @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果該數(shù)組只有一個(gè)數(shù)煤搜，那么最大的就是該數(shù)組第一個(gè)值了 if (L == R) {
    return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整體的最大值
    if (a > b) {
        return a;
    } else {
        return b;
} }

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

public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍歷的次數(shù)由數(shù)組最大值的位數(shù)來決定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10]; 
//獲取每一位數(shù)字(個(gè)免绿、十、百擦盾、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) { 
int num = (arrays[j] / i) % 10;
//將其放入桶子里
buckets[j][num] = arrays[j]; 
}
//回收桶子里的元素 
int k = 0;
//有10個(gè)桶子
for (int j = 0; j < 10; j++) {
//對每個(gè)桶子里的元素進(jìn)行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(數(shù)據(jù)初始化會(huì)為0) 
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j]; 
}
}
}
}
}

搞了一堆數(shù)測試了一哈:

image.png

桶排序(基數(shù)排序)總結(jié)
基數(shù)排序(桶排序)要理解起來并不困難嘲驾，不過值得注意的是:基數(shù)排序?qū)τ胸?fù)數(shù)和0的數(shù)列難以進(jìn)行排序

• 因此淌哟，往往有0和負(fù)數(shù)的數(shù)組一般我們都不用基數(shù)來進(jìn)行排序
  基數(shù)排序的要點(diǎn)就兩個(gè):
• 分配:按照元素的大小來放入不同的桶子里
• 回收:將桶子里的元素按桶子順序重新放到數(shù)組中
• 重復(fù).....兩個(gè)步驟

image.png