排序算法可以分為內(nèi)部排序和外部排序.
內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序
外部排序是因排序的數(shù)據(jù)很大菩浙，一次不能容納全部的排序記錄，在排序過程中需要訪問外存
常見的內(nèi)部排序算法有：插入排序芦劣、希爾排序鸽捻、選擇排序旧烧、冒泡排序、歸并排序蒋纬、快速排序猎荠、堆排序坚弱、基數(shù)排序等。用一張圖概括：
關(guān)于時間復雜度：
平方階 (O(n2)) 排序 各類簡單排序：直接插入关摇、直接選擇和冒泡排序荒叶。
線性對數(shù)階 (O(nlog2n)) 排序: 快速排序、堆排序和歸并排序输虱。
O(n1+§)) 排序些楣，§ 是介于 0 和 1 之間的常數(shù):希爾排序。
線性階 (O(n)) 排序 :基數(shù)排序宪睹，此外還有桶愁茁、箱排序。
關(guān)于穩(wěn)定性：
穩(wěn)定的排序算法：冒泡排序亭病、插入排序鹅很、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序罪帖、快速排序促煮、希爾排序、堆排序整袁。
名詞解釋：
n：數(shù)據(jù)規(guī)模
k：“桶”的個數(shù)
In-place：占用常數(shù)內(nèi)存菠齿，不占用額外內(nèi)存
Out-place：占用額外內(nèi)存
穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同
1、冒泡排序
冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法坐昙。它重復地走訪過要排序的數(shù)列绳匀，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來炸客。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換疾棵，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端痹仙。
作為最簡單的排序算法之一陋桂。冒泡排序還有一種優(yōu)化算法，就是立一個 flag蝶溶，當在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序宣渗。但這種改進對于提升性能來說并沒有什么太大作用抖所。
1. 算法步驟
1.比較相鄰的元素。如果第一個比第二個大痕囱，就交換他們兩個田轧。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對鞍恢。這步做完后傻粘，最后的元素會是最大的數(shù)每窖。
3.針對所有的元素重復以上的步驟，除了最后一個弦悉。
4.持續(xù)每次對越來越少的元素重復上面的步驟窒典，直到?jīng)]有任何一對數(shù)字需要比較。
2. 動圖演示
3. 什么時候最快
當輸入的數(shù)據(jù)已經(jīng)是正序時（都已經(jīng)是正序了稽莉，我還要你冒泡排序有何用捌僦尽）。
4. 什么時候最慢
當輸入的數(shù)據(jù)是反序時（寫一個 for 循環(huán)反序輸出數(shù)據(jù)不就行了污秆，干嘛要用你冒泡排序呢劈猪，我是閑的嗎）。
5. Java 代碼實現(xiàn)
public class BubbleSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝良拼，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
for (int i = 1; i < arr.length; i++) {
// 設(shè)定一個標記战得，若為true，則表示此次循環(huán)沒有進行交換庸推，也就是待排序列已經(jīng)有序常侦，排序已經(jīng)完成。
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) {
break;
}
}
return arr;
}
}
2予弧、選擇排序
選擇排序是一種簡單直觀的排序算法刮吧，無論什么數(shù)據(jù)進去都是 O(n2) 的時間復雜度。所以用到它的時候掖蛤，數(shù)據(jù)規(guī)模越小越好杀捻。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。
1. 算法步驟
首先在未排序序列中找到最序就ァ（大）元素致讥，存放到排序序列的起始位置
再從剩余未排序元素中繼續(xù)尋找最小（大）元素器赞，然后放到已排序序列的末尾垢袱。
重復第二步，直到所有元素均排序完畢港柜。
2. 動圖演示
3. Java 代碼實現(xiàn)
public class SelectionSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 總共要經(jīng)過 N-1 輪比較
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每輪需要比較的次數(shù) N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 記錄目前能找到的最小值元素的下標
min = j;
}
}
// 將找到的最小值和i位置所在的值進行交換
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
}
3请契、插入排序
插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了夏醉，因為只要打過撲克牌的人都應(yīng)該能夠秒懂爽锥。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列畔柔，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描靶擦，找到相應(yīng)位置并插入雇毫。
插入排序和冒泡排序一樣，也有一種優(yōu)化算法踩蔚，叫做拆半插入棚放。
1. 算法步驟
將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列寂纪。
從頭到尾依次掃描未排序序列席吴，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等捞蛋，則將待插入元素插入到相等元素的后面孝冒。）
2. 動圖演示
3. Java 代碼實現(xiàn)
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 從下標為1的元素開始選擇合適的位置插入拟杉，因為下標為0的只有一個元素庄涡，默認是有序的
for (int i = 1; i < arr.length; i++) {
// 記錄要插入的數(shù)據(jù)
int tmp = arr[i];
// 從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的數(shù)搬设，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
4穴店、希爾排序
希爾排序，也稱遞減增量排序算法拿穴，是插入排序的一種更高效的改進版本泣洞。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時默色，效率高球凰，即可以達到線性排序的效率；
但插入排序一般來說是低效的腿宰，因為插入排序每次只能將數(shù)據(jù)移動一位呕诉；
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時吃度，再對全體記錄進行依次直接插入排序甩挫。
1. 算法步驟
選擇一個增量序列 t1椿每，t2，……删壮，tk兑牡，其中 ti > tj, tk = 1均函；
按增量序列個數(shù) k，對序列進行 k 趟排序洛勉；
每趟排序收毫，根據(jù)對應(yīng)的增量 ti殷勘，將待排序列分割成若干長度為 m 的子序列玲销，分別對各子表進行直接插入排序贤斜。僅增量因子為 1 時，整個序列作為一個表來處理猴抹，表長度即為整個序列的長度蟀给。
2. Java 代碼實現(xiàn)
public class ShellSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝坤溃，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
return arr;
}
}
5薪介、歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法汁政。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用记劈。
作為一種典型的分而治之思想的算法應(yīng)用并巍，歸并排序的實現(xiàn)由兩種方法：
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫懊渡，所以就有了第 2 種方法）；
自下而上的迭代誓禁；
在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中摹恰，作者給出了自下而上的迭代方法。但是對于遞歸法姑宽，作者卻認為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而低千，在 JavaScript 中這種方式不太可行示血，因為這個算法的遞歸深度對它來講太深了难审。
說實話亿絮，我不太理解這句話派昧。意思是 JavaScript 編譯器內(nèi)存太小蒂萎，遞歸太深容易造成內(nèi)存溢出嗎？還望有大神能夠指教纳寂。
和選擇排序一樣毙芜，歸并排序的性能不受輸入數(shù)據(jù)的影響腋粥，但表現(xiàn)比選擇排序好的多灯抛，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內(nèi)存空間。
1. 算法步驟
申請空間纵竖，使其大小為兩個已經(jīng)排序序列之和靡砌，該空間用來存放合并后的序列通殃；
設(shè)定兩個指針厕宗，最初位置分別為兩個已經(jīng)排序序列的起始位置已慢；
比較兩個指針所指向的元素佑惠，選擇相對小的元素放入到合并空間膜楷，并移動指針到下一位置；
重復步驟 3 直到某一指針達到序列尾穷绵；
將另一序列剩下的所有元素直接復制到合并序列尾请垛。
2. 動圖演示
3. Java 代碼實現(xiàn)
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝宗收，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
6、快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下礼旅，排序 n 個項目要 Ο(nlogn) 次比較痘系。在最壞狀況下則需要 Ο(n2) 次比較汰翠，但這種狀況并不常見昭雌。事實上烛卧，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來呈宇。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）攒盈。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用型豁。本質(zhì)上來看尚蝌，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法飘言。
快速排序的名字起的是簡單粗暴姿鸿，因為一聽到這個名字你就知道它存在的意義，就是快句狼，而且效率高腻菇！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復雜度達到了 O(n2)糖耸，但是人家就是優(yōu)秀嘉竟，在大多數(shù)情況下都比平均時間復雜度為 O(n logn) 的排序算法表現(xiàn)要更好周拐，可是這是為什么呢，我也不知道审丘。好在我的強迫癥又犯了滩报，查了 N 多資料終于在《算法藝術(shù)與信息學競賽》上找到了滿意的答案：
快速排序的最壞運行情況是 O(n2)，比如說順序數(shù)列的快排售睹。但它的平攤期望時間是 O(nlogn)昌妹，且 O(nlogn) 記號中隱含的常數(shù)因子很小飞崖，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多固歪。所以胯努，對絕大多數(shù)順序性較弱的隨機數(shù)列而言叶沛，快速排序總是優(yōu)于歸并排序恬汁。
1. 算法步驟
1.從數(shù)列中挑出一個元素，稱為 “基準”（pivot）;
2.重新排序數(shù)列脊另，所有元素比基準值小的擺放在基準前面偎痛，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后枚赡，該基準就處于數(shù)列的中間位置贫橙。這個稱為分區(qū)（partition）操作卢肃；
3.遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序莫湘；
遞歸的最底部情形幅垮，是數(shù)列的大小是零或一忙芒，也就是永遠都已經(jīng)被排序好了演怎。雖然一直遞歸下去爷耀，但是這個算法總會退出歹叮，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去德谅。
2. 動圖演示
3. Java 代碼實現(xiàn)
public class QuickSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝窄做，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return quickSort(arr, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
// 設(shè)定基準值（pivot）
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
7组砚、堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法掏颊。堆積是一個近似完全二叉樹的結(jié)構(gòu)乌叶，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點准浴。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
1.大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值句旱，在堆排序算法中用于升序排列；
2.小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值匾南，在堆排序算法中用于降序排列蛆楞；
堆排序的平均時間復雜度為 Ο(nlogn)夹厌。
1. 算法步驟
1.創(chuàng)建一個堆 H[0……n-1]矛纹；
2.把堆首（最大值）和堆尾互換；
3.把堆的尺寸縮小 1孩等，并調(diào)用 shift_down(0)肄方，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置权她；
4.重復步驟 2，直到堆的尺寸為 1蝴罪。
2. 動圖演示
3. Java 代碼實現(xiàn)
public class HeapSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝靠娱，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
8、計數(shù)排序
計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復雜度的排序栽烂，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)书聚。
1. 動圖演示
2. Java 代碼實現(xiàn)
public class CountingSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝雌续，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
}
9受啥、桶排序
桶排序是計數(shù)排序的升級版滚局。它利用了函數(shù)的映射關(guān)系顽频，高效與否的關(guān)鍵就在于這個映射函數(shù)的確定糯景。為了使桶排序更加高效，我們需要做到這兩點：
1.在額外空間充足的情況下丑孩，盡量增大桶的數(shù)量
2.使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中
同時温学，對于桶中元素的排序仗岖，選擇何種比較排序算法對于性能的影響至關(guān)重要。
1. 什么時候最快
當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中揽祥。
2. 什么時候最慢
當輸入的數(shù)據(jù)被分配到了同一個桶中拄丰。
3. Java 代碼實現(xiàn)
public class BucketSort implements IArraySort {
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝料按，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 對每個桶進行排序载矿，這里使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 自動擴容烹卒，并保存數(shù)據(jù)
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
10旅急、基數(shù)排序
基數(shù)排序是一種非比較型整數(shù)排序算法藐吮，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)秋泳，所以基數(shù)排序也不是只能使用于整數(shù)迫皱。
1. 基數(shù)排序 vs 計數(shù)排序 vs 桶排序
基數(shù)排序有兩種方法：
這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶和敬；
計數(shù)排序：每個桶只存儲單一鍵值昼弟；
桶排序：每個桶存儲一定范圍的數(shù)值舱痘；
2. LSD 基數(shù)排序動圖演示
3. Java 代碼實現(xiàn)
/**
* 基數(shù)排序
* 考慮負數(shù)的情況還可以參考：https://code.i-harness.com/zh-CN/q/e98fa9
*/
public class RadixSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 獲取最高位數(shù)
*/
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考慮負數(shù)的情況塌碌，這里擴展一倍隊列數(shù)台妆，其中 [0-9]對應(yīng)負數(shù)接剩，[10-19]對應(yīng)正數(shù) (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自動擴容搂漠，并保存數(shù)據(jù)
*
* @param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
這篇文章很不錯,美中不足的是沒有實例,因為一些個人原因,我也不敢擅自加一些實例,不過我會繼續(xù)學習,爭取有一天將實例加上以便更好的理解.
