排序演算法
回顧
我們前面已經介紹了 3 種最常見的排序演算法：
java 實現冒泡排序講解
QuickSort 快速排序到底快在哪裡？
SelectionSort 選擇排序演算法詳解（java 實現）
然而天下排序千千萬，今天老馬就和大家一起把最常見的幾種都學習一遍。
堆排序
堆排序（英語：Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。
堆是一個近似完全二叉樹的結構，並同時滿足堆的性質：即子節點的鍵值或索引總是小於（或者大於）它的父節點。
基礎知識 JCIP-11-二叉堆
最大堆
若以升序排序說明，把數組轉換成最大堆(Max-Heap Heap)，這是一種滿足最大堆性質(Max-Heap Property)的二叉樹：對於除了根之外的每個節點i, A[parent(i)] ≥ A[i]。
堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。如下圖：
重複從最大堆取出數值最大的結點(把根結點和最後一個結點交換，把交換後的最後一個結點移出堆)，並讓殘餘的堆維持最大堆性質。
輸入圖片說明
同時，我們對堆中的結點按層進行編號，將這種邏輯結構映射到數組中就是下面這個樣子:
輸入圖片說明
堆節點的訪問
通常堆是通過一維數組來實現的。
在數組起始位置為0的情形中：
則父節點和子節點的位置關係如下：
(01) 索引為i的左孩子的索引是 (2*i+1);
(02) 索引為i的左孩子的索引是 (2*i+2);
(03) 索引為i的父結點的索引是 floor((i-1)/2);
堆節點的訪問
堆的操作
在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。
堆中定義以下幾種操作：
最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
創建最大堆（Build Max Heap）：將堆中的所有數據重新排序
堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算
堆排序演算法圖解
這個圖解來自 圖解排序演算法(三)之堆排序，畫的非常漂亮。
基本思想
將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。
將其與末尾元素進行交換，此時末尾就為最大值。
然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反覆執行，便能得到一個有序序列了。
步驟
步驟一 構造初始堆
將給定無序序列構造成一個大頂堆（一般升序採用大頂堆，降序採用小頂堆)。
a. 假設給定無序序列結構如下
輸入圖片說明
b. 此時我們從最後一個非葉子結點開始（葉子結點自然不用調整，第一個非葉子結點 arr.length/2-1=5/2-1=1，也就是下面的6結點），從左至右，從下至上進行調整。
輸入圖片說明
c. 找到第二個非葉節點4，由於[4,9,8]中9元素最大，4和9交換。
輸入圖片說明
d. 這時，交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中6最大，交換4和6。
輸入圖片說明
此時，我們就將一個無序的序列構造成了一個大頂堆。
步驟二 調整堆
將堆頂元素與末尾元素進行交換，使末尾元素最大。
然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反覆進行交換、重建、交換。
a. 將堆頂元素9和末尾元素4進行交換
輸入圖片說明
b. 重新調整結構，使其繼續滿足堆定義
輸入圖片說明
c. 再將堆頂元素8與末尾元素5進行交換，得到第二大元素8.
輸入圖片說明
後續過程，繼續進行調整，交換，如此反覆進行，最終使得整個序列有序
輸入圖片說明
簡單總結
再簡單總結下堆排序的基本思路：
a. 將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
b. 將堆頂元素與末尾元素交換，將最大元素”沉”到數組末端;
c. 重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，直到整個序列有序。
java 實現
說明
為了和前面的邏輯保持一致，我們暫時依然使用 list 去實現這個堆排序。
實現
package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/**
* 堆排序
*
* @author binbin.hou
* @since 0.0.4
*/
public class HeapSort extends AbstractSort {
private static final Log log = LogFactory.getLog(HeapSort.class);
@Override
@SuppressWarnings("all")
protected void doSort(List<?> original) {
final int maxIndex = original.size() - 1;
/*
* 第一步：將數組堆化
* beginIndex = 第一個非葉子節點。
* 從第一個非葉子節點開始即可。無需從最後一個葉子節點開始。
* 葉子節點可以看作已符合堆要求的節點，根節點就是它自己且自己以下值為最大。
*/
int beginIndex = original.size() / 2 - 1;
for (int i = beginIndex; i >= 0; i--) {
maxHeapify(original, i, maxIndex);
}
/*
* 第二步：對堆化數據排序
* 每次都是移出最頂層的根節點A[0]，與最尾部節點位置調換，同時遍歷長度 - 1。
* 然後從新整理被換到根節點的末尾元素，使其符合堆的特性。
* 直至未排序的堆長度為 0。
*/
for (int i = maxIndex; i > 0; i--) {
InnerSortUtil.swap(original, 0, i);
maxHeapify(original, 0, i - 1);
}
}
/**
* 調整索引為 index 處的數據，使其符合堆的特性。
*
* @param list 列表
* @param index 需要堆化處理的數據的索引
* @param len 未排序的堆（數組）的長度
* @since 0.0.4
*/
@SuppressWarnings("all")
private void maxHeapify(final List list, int index, int len) {
int li = (index * 2) + 1; // 左子節點索引
int ri = li + 1; // 右子節點索引
int cMax = li; // 子節點值最大索引，默認左子節點。
// 左子節點索引超出計算範圍，直接返回。
if (li > len) {
return;
}
// 先判斷左右子節點，哪個較大。
if (ri <= len && InnerSortUtil.gt(list, ri, li)) {
cMax = ri;
}
if (InnerSortUtil.gt(list, cMax, index)) {
InnerSortUtil.swap(list, cMax, index); // 如果父節點被子節點調換，
maxHeapify(list, cMax, len); // 則需要繼續判斷換下後的父節點是否符合堆的特性。
}
}
}
插入排序
插入排序（英語：Insertion Sort）是一種簡單直觀的排序演算法。
它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
插入排序在實現上，通常採用in-place排序（即只需用到 O(1) 的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。
演算法步驟
一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：
- 從第一個元素開始，該元素可以認為已經被排序
- 取出下一個元素，在已經排序的元素序列中從後向前掃描
- 如果該元素（已排序）大於新元素，將該元素移到下一位置
- 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
- 將新元素插入到該位置後
- 重複步驟2~5
排序
java 實現
java 實現
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/**
* 冒泡排序
* @author binbin.hou
* @since 0.0.5
*/
@ThreadSafe
public class InsertSort extends AbstractSort {
private static final Log log = LogFactory.getLog(InsertSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
for(int i = 1; i < original.size(); i++) {
Comparable current = (Comparable) original.get(i);
int j = i-1;
// 從後向前遍歷，把大於當前元素的信息全部向後移動。
while (j >= 0 && InnerSortUtil.gt(original, j, current)) {
// 元素向後移動一位
original.set(j+1, original.get(j));
j--;
}
// 將元素插入到對應的位置
original.set(j+1, current);
}
}
}
希爾排序（Shellsort）
也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。
希爾排序是非穩定排序演算法。
希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
- 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率
- 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位
演算法實現
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。
這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用複雜度為O(n^2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。
而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。
一個更好理解的希爾排序實現：將數組列在一個表中並對列排序（用插入排序）。重複這過程，不過每次用更長的列來進行。最後整個表就只有一列了。
將數組轉換至表是為了更好地理解這演算法，演算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。
例子
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述演算法，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然後我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。
這時10已經移至正確位置了，然後再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之後變為：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最後以1步長進行排序（此時就是簡單的插入排序了）。
步長序列如何選擇？
Donald Shell 最初建議步長選擇為 n/2 並且對步長取半直到步長達到1。
雖然這樣取可以比 O(n^2) 類的演算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的餘地。
已知的最好步長序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…)，
另一個在大數組中表現優異的步長序列是（斐波那契數列除去0和1將剩餘的數以黃金分割比的兩倍的冪進行運算得到的數列）：
(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)
java 代碼實現
實現
這裡為了簡單，我們步長直接選擇列表長度的一半，並且依次折半。
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.List;
/**
* 希爾排序
*
* @author binbin.hou
* @since 0.0.6
*/
public class ShellSort extends AbstractSort {
private static final Log log = LogFactory.getLog(ShellSort.class);
@Override
@SuppressWarnings("all")
protected void doSort(List<?> original) {
// 步長從大到小
for(int step = original.size()/2; step > 0; step /= 2) {
// 從第 step 個元素，逐個執行插入排序
for(int i = step; i < original.size(); i++) {
int j = i;
while ((j-step >= 0) && InnerSortUtil.lt(original, j, j-step)) {
// 執行交換
InnerSortUtil.swap(original, j, j-step);
if(log.isDebugEnabled()) {
log.debug("step: {}, j: {}, j-step: {}, list: {}",
step, j, j-step, original);
}
// 更新步長
j -= step;
}
}
}
}
}
整體實現也不難，大家可以回顧下 插入排序
這裡為了便於大家理解，我們特意添加了日誌。
歸併排序（英語：Merge sort，或mergesort）
是創建在歸併操作上的一種有效的排序演算法，效率為 O(nlogn)（大O符號）。1945年由約翰·馮·諾伊曼首次提出。
該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
概述
採用分治法:
分割：遞歸地把當前序列平均分割成兩半。
集成：在保持元素順序的同時將上一步得到的子序列集成到一起（歸併）。
java 實現遞歸法
遞歸法（Top-down）
- 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
- 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
- 重複步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接複製到合併序列尾
java 實現
實際上代碼實現也不難，不過遞歸多多少少讓人看起來不太習慣。
我們後面會結合測試日誌，再進行講解。
package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.ArrayList;
import java.util.List;
/**
* 歸併排序-遞歸實現
*
* @author binbin.hou
* @since 0.0.7
*/
public class MergeRecursiveSort extends AbstractSort {
private static final Log log = LogFactory.getLog(MergeRecursiveSort.class);
@Override
@SuppressWarnings("all")
protected void doSort(List<?> original) {
// 存放歸併的結果
// 直接將數組填滿，避免 set 出現越界
List<?> resultList = new ArrayList<>(original);
sortRecursive(original, resultList, 0, original.size()-1);
}
/**
* 遞歸排序
* @param originalList 原始列表
* @param resultList 存放結果的列表
* @param startIx 開始
* @param endIx 結果
* @since 0.0.7
*/
@SuppressWarnings("all")
private void sortRecursive(List originalList,
List resultList,
int startIx,
int endIx) {
// 循環結束
if(startIx >= endIx) {
return;
}
// 找到中間位置，將列表一分為二
int midIx = (startIx+endIx) / 2;
int leftStart = startIx;
int leftEnd = midIx;
int rightStart = midIx+1;
int rightEnd = endIx;
if(log.isDebugEnabled()) {
log.debug("拆分：ls: {}, le: {}, rs: {}, re: {}",
leftStart, leftEnd, rightStart, rightEnd);
}
// 遞歸調用
sortRecursive(originalList, resultList, leftStart, leftEnd);
sortRecursive(originalList, resultList, rightStart, rightEnd);
if(log.isDebugEnabled()) {
log.debug("操作：ls: {}, le: {}, rs: {}, re: {}",
leftStart, leftEnd, rightStart, rightEnd);
}
// 這裡需要通過 k 記錄一下開始的位置
int k = startIx;
while (leftStart <= leftEnd && rightStart <= rightEnd) {
//相對小的元素放入到合併空間，並移動指針到下一位置
Comparable left = (Comparable) originalList.get(leftStart);
Comparable right = (Comparable) originalList.get(rightStart);
// 左邊較小，則放入合併空間
if(left.compareTo(right) < 0) {
resultList.set(k++, left);
leftStart++;
} else {
resultList.set(k++, right);
rightStart++;
}
}
// 如果列表比較結束，將剩下的元素，全部放入到隊列中。
while (leftStart <= leftEnd) {
resultList.set(k++, originalList.get(leftStart++));
}
while (rightStart <= rightEnd) {
resultList.set(k++, originalList.get(rightStart++));
}
// 將結果統一拷貝到原始集合中
for(int i = startIx; i <= endIx; i++) {
originalList.set(i, resultList.get(i));
}
}
}
java 迭代實現
相信很多小夥伴都知道迭代可以使得代碼變得簡潔，但是會讓調試和理解變得複雜。
我們來一起學習一下迭代的實現方式。
迭代法（Bottom-up）
原理如下（假設序列共有 n 個元素）：
- 將序列每相鄰兩個數字進行歸併操作，形成 ceil(n/2) 個序列，排序後每個序列包含兩/一個元素
- 若此時序列數不是1個則將上述序列再次歸併，形成 ceil(n/4) 個序列，每個序列包含四/三個元素
- 重複步驟2，直到所有元素排序完畢，即序列數為1
迭代實現
相對遞歸，這個代碼就要顯得複雜很多。
不過這種迭代的方式性能更好，實現如下。
package com.github.houbb.sort.core.api;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.ArrayList;
import java.util.List;
/**
* 歸併排序-迭代實現
*
* @author binbin.hou
* @since 0.0.7
*/
public class MergeSort extends AbstractSort {
private static final Log log = LogFactory.getLog(MergeSort.class);
@Override
protected void doSort(List<?> original) {
// 存放歸併的結果
// 直接將數組填滿，避免 set 出現越界
List<?> resultList = new ArrayList<>(original);
//起始，子序列長度為1。對長度為1的序列進行兩兩合併
int k = 1;
final int length = original.size();
while (k < length) {
mergePass(original, resultList, k, length);//將原先無序的數據兩兩歸併入歸併數組
k = 2 * k;//子序列長度加倍
mergePass(resultList, original, k, length);//將歸併數組中已經兩兩歸併的有序序列再歸併回數組 original
k = 2 * k;//子序列長度加倍
}
}
/**
* 負責將數組中的相鄰的有k個元素的字序列進行歸併
*
* @param original 原始列表
* @param results 結果列表
* @param s 子序列長度
* @param len 長度
* @since 0.0.7
*/
@SuppressWarnings("all")
private static void mergePass(List original, List results, int s, int len) {
int i = 0;
// 寫成(i + 2 * k - 1 < len)，就會把（i+2*k-1）當做一個整體看待
// 從前往後,將2個長度為k的子序列合併為1個。
// 對於序列{3, 4, 2, 5, 7, 0, 9, 8, 1, 6}，當k=8的時候，因為i>(len-2*k+1),所以根本沒有進入while循環
while (i < len - 2 * s + 1) {
merge(original, results, i, i + s - 1, i + 2 * s - 1);//兩兩歸併
i = i + 2 * s;
}
// 將那些「落單的」長度不足兩兩merge的部分和前面merge起來。
// (連接起來之前也是要進行排序的，因此有了下面的merge操作)
if (i < len - s + 1) {
merge(original, results, i, i + s - 1, len - 1);//歸併最後兩個序列
} else {
for (int j = i; j < len; j++) {//若最後只剩下單個子序列
results.set(j, original.get(j));
}
}
}
/**
* 將兩個有序數組合併成一個有序數組
* @param original 原始
* @param result 結果
* @param low 開始
* @param mid 中間
* @param high 結束
* @since 0.0.7
*/
@SuppressWarnings("all")
private static void merge(List original, List result, int low, int mid, int high) {
int j, k, l;
// 將記錄由小到大地放進temp數組
for (j = mid + 1, k = low; low <= mid && j <= high; k++) {
if (InnerSortUtil.lt(original, low, j)) {
result.set(k, original.get(low++));
} else {
result.set(k, original.get(j++));
}
}
//接下來兩循環是為了將剩餘的（比另一邊多出來的個數）放到temp數組中
if (low <= mid) {
for (l = 0; l <= mid - low; l++) {
result.set(k + l, original.get(low + l));
}
}
if (j <= high) {
for (l = 0; l <= high - j; l++) {
result.set(k + l, original.get(j + l));
}
}
}
}
counting sort 計數排序
計數排序（Counting sort）是一種穩定的線性時間排序演算法。
該演算法於1954年由 Harold H. Seward 提出。
通過計數將時間複雜度降到了 O(N)。
基礎版
演算法步驟
- 找出原數組中元素值最大的，記為max。
- 創建一個新數組count，其長度是max加1，其元素默認值都為0。
- 遍歷原數組中的元素，以原數組中的元素作為count數組的索引，以原數組中的元素出現次數作為count數組的元素值。
- 創建結果數組result，起始索引index。
- 遍歷count數組，找出其中元素值大於0的元素，將其對應的索引作為元素值填充到result數組中去，每處理一次，count中的該元素值減1，直到該元素值不大於0，依次處理count中剩下的元素。
- 返回結果數組 result。
java 實現
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 計數排序
*
* @author binbin.hou
* @since 0.0.8
*/
@ThreadSafe
public class CountingSortBasic extends AbstractSort {
private static final Log log = LogFactory.getLog(CountingSortBasic.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
//1. 獲取最大的元素
int max = Integer.MIN_VALUE;
for (Object object : original) {
Integer integer = (Integer) object;
max = Math.max(max, integer);
}
//2. 構建 count 列表
int[] counts = new int[max + 1];
//3.遍歷原數組中的元素，以原數組中的元素作為count數組的索引，以原數組中的元素出現次數作為count數組的元素值。
for (Object object : original) {
Integer integer = (Integer) object;
counts[integer]++;
}
//4. 結果構建
int index = 0;
// 遍歷計數數組，將計數數組的索引填充到結果數組中
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
// i 實際上就是元素的值
// 從左到右遍歷，元素自然也就排序好了。
// 相同的元素會出現多次，所以才需要循環。
original.set(index++, i);
counts[i]--;
if(log.isDebugEnabled()) {
log.debug("結果數組：{}", original);
}
}
}
}
}
改良版
空間浪費
實際上我們創建一個比最大元素還要大1的數組，只是為了放下所有的元素而已。
但是它有一個缺陷，那就是存在空間浪費的問題。
比如一組數據{101,109,102,110}，其中最大值為110，按照基礎版的思路，我們需要創建一個長度為111的計數數組，但是我們可以發現，它前面的[0,100]的空間完全浪費了，那怎樣優化呢？
將數組長度定為 max-min+1，即不僅要找出最大值，還要找出最小值，根據兩者的差來確定計數數組的長度。
改良版本實現
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.Arrays;
import java.util.List;
/**
* 計數排序
*
* @author binbin.hou
* @since 0.0.8
*/
@ThreadSafe
public class CountingSort extends AbstractSort {
private static final Log log = LogFactory.getLog(CountingSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
//1. 獲取最大、最小的元素
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (Object object : original) {
Integer integer = (Integer) object;
max = Math.max(max, integer);
min = Math.min(min, integer);
}
//2. 構建 count 列表
int[] counts = new int[max-min + 1];
//3.遍歷原數組中的元素，以原數組中的元素作為count數組的索引，以原數組中的元素出現次數作為count數組的元素值。
for (Object object : original) {
Integer integer = (Integer) object;
// 元素要減去最小值，再作為新索引
counts[integer-min]++;
}
if(log.isDebugEnabled()) {
log.debug("counts.length: {}", counts.length);
}
//4. 結果構建
int index = 0;
// 遍歷計數數組，將計數數組的索引填充到結果數組中
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
// i 實際上就是元素的值
// 從左到右遍歷，元素自然也就排序好了。
// 相同的元素會出現多次，所以才需要循環。
// 這裡將減去的最小值統一加上
original.set(index++, i+min);
counts[i]--;
if(log.isDebugEnabled()) {
log.debug("結果數組：{}", original);
}
}
}
}
}
自己的思考
演算法的本質
這個演算法的本質是什麼呢？
個人理解只需要保證兩點：
（1）每一個元素，都有自己的一個元素位置
（2）相同的元素，次數會增加。
演算法的巧妙之處在於直接利用數值本身所謂索引，直接跳過了排序比較；利用技數，解決了重複數值的問題。
演算法的不足
這個演算法的巧妙之處，同時也是對應的限制：那就是只能直接比較數字。如果是字元串呢？
一點想法
我最初的想法就是可以使用類似於 HashMap 的數據結構。這樣可以解決元素過濾，次數統計的問題。
但是無法解決排序問題。
當然了，如果使用 TreeMap 就太賴皮了，因為本身就是利用了樹進行排序。
TreeMap 版本
我們這裡使用 TreeMap 主要有下面的目的：
（1）讓排序不局限於數字。
（2）大幅度降低內存的浪費，不多一個元素，也不少一個元素。
思想實際上依然是技術排序的思想。
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/**
* 計數排序-TreeMap
*
* @author binbin.hou
* @since 0.0.8
*/
@ThreadSafe
public class CountingSortTreeMap extends AbstractSort {
private static final Log log = LogFactory.getLog(CountingSortTreeMap.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
TreeMap<Comparable, Integer> countMap = new TreeMap<>();
// 初始化次數
for (Object object : original) {
Comparable comparable = (Comparable) object;
Integer count = countMap.get(comparable);
if(count == null) {
count = 0;
}
count++;
countMap.put(comparable, count);
}
//4. 結果構建
int index = 0;
// 遍歷計數數組，將計數數組的索引填充到結果數組中
for (Map.Entry<Comparable, Integer> entry : countMap.entrySet()) {
int count = entry.getValue();
Comparable key = entry.getKey();
while (count > 0) {
// i 實際上就是元素的值
// 從左到右遍歷，元素自然也就排序好了。
// 相同的元素會出現多次，所以才需要循環。
original.set(index++, key);
count--;
}
}
}
}
桶排序（Bucket sort）
或所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶里。
每個桶再個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。
桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間 O(n)。
桶排序是計數排序的擴展版本，計數排序可以看成每個桶只存儲相同元素，而桶排序每個桶存儲一定範圍的元素，通過映射函數，將待排序數組中的元素映射到各個對應的桶中，對每個桶中的元素進行排序，最後將非空桶中的元素逐個放入原序列中。
桶排序需要盡量保證元素分散均勻，否則當所有數據集中在同一個桶中時，桶排序失效。
演算法流程
桶排序以下列程序進行：
- 設置一個定量的數組當作空桶子。
- 尋訪序列，並且把項目一個一個放到對應的桶子去。
- 對每個不是空的桶子進行排序。
- 從不是空的桶子里把項目再放回原來的序列中。
演算法
java 實現
實現
package com.github.houbb.sort.core.api;
import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 桶排序
*
* @author binbin.hou
* @since 0.0.9
*/
@ThreadSafe
public class BucketSort extends AbstractSort {
private static final Log log = LogFactory.getLog(BucketSort.class);
@Override
@SuppressWarnings("all")
public void doSort(List original) {
final int step = 10;
// 計算最小值
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(Object object : original) {
Integer integer = (Integer) object;
min = Math.min(min, integer);
max = Math.max(max, integer);
}
//2. 計算桶的個數
int bucketNum = (max-min) / step + 1;;
//2.1 初始化臨時列表
List<List<Integer>> tempList = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++) {
tempList.add(new ArrayList<Integer>());
}
//3. 將元素放入桶中
// 這裡有一個限制：要求元素必須一個左邊的桶元素，要小於右邊的桶。
// 這就限制了只能是數字類的比較，不然沒有範圍的概念
for(Object o : original) {
Integer integer = (Integer) o;
int index = (integer-min) / step;
tempList.get(index).add(integer);
}
// 4. 針對單個桶進行排序
// 可以選擇任意你喜歡的演算法
for(int i = 0; i < bucketNum; i++) {
Collections.sort(tempList.get(i));
}
//5. 設置結果
int index = 0;
for(int i = 0; i < bucketNum; i++) {
List<Integer> integers = tempList.get(i);
for(Integer val : integers) {
original.set(index++, val);
}
}
}
}
原創文章，作者：投稿專員，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/323615.html
微信掃一掃 
支付寶掃一掃 