注：以下内容為筆者學習《Java程式員的基本修養》一書的學習筆記
概述：
排序是程式開發中一種非常常見的操作，指對一組任意的資料元素(或記錄)經過排序操作後，将它們變成一組按關鍵字排序的有序序列。
一旦将一組雜亂無章的記錄重排成一組有序記錄，就能快速地從這組記錄中找到目标記錄。
衡量排序算法(sorting algorithm)優劣的三個方面：時間複雜度：主要分析關鍵字的比較次數和記錄的移動次數
空間複雜度：分析排序算法中需要多少輔助記憶體
穩定性：若兩個記錄A和B的關鍵字值相等，但排序後A、B的先後次序保持不變，則稱這種排序算法是穩定的；反之就是不穩定的。
分類：内部排序(整個排序過程不需要借助于外部存儲器(如磁盤等)，所有排序操作都在記憶體中完成)
主要分為：選擇排序
交換排序
插入排序
歸并排序
桶式排序
基數排序
外部排序(參與排序的資料元素非常多，資料量非常大，計算機排序時必須借助于外部存儲器)
常用的算法是多路歸并排序，即将原檔案分解成多個能夠一次性裝入記憶體的部分，分别将每一部分調入記憶體完成排序，接下來再對多個有序的子檔案進行歸并排序。
具體步驟：把兩個檔案中的一組記錄讀入記憶體的排序區，對讀入的記錄按上面講到的内部排序法進行排序，排序之後輸出到外部存儲器。不斷重複這一過程，每次讀取一組記錄，直到源檔案的所有記錄被處理完畢。
将上一步分組排序好的記錄兩組兩組的合并排序。在記憶體容量允許的情況下，每組中包含的記錄越大越好，以減少合并次數。
[選擇排序法]直接選擇排序
該排序算法思路簡單，需要經過n-1趟比較。
第1趟：程式将記錄定位在第一個資料上，拿第1個資料依次和它後面的每一個資料進行比較，如果第1個資料大于後面某個資料，就交換它們......，以此類推。經過第1趟比較，這組資料中最小的資料被選出，被排在第1位。
第2趟：程式将記錄定位在第二個資料上，拿第2個資料依次和它後面的每一個資料進行比較，如果第2個資料大于後面某個資料，就交換它們......，以此類推。經過第2趟比較，這組資料中第二小的資料被選出，被排在第2位。
......
從上面描述可知，直接選擇排序算法的關鍵就是n-1趟比較，每趟比較的目的就是選出本趟比較中最小的資料，并将該資料放在本趟比較的第1位。
示例代碼：
package com.atschool;
import java.util.Arrays;
class DataWrap implements Comparable{
int data;
String flag;
public DataWrap(int data,String flag){
this.data = data;
this.flag = flag;
}
@Override
public String toString() {
return data + flag;
}
@Override
public int compareTo(DataWrap o) {
return this.data > o.data ? 1 : (this.data == o.data ? 0 : -1);
}
}
public class SelectSort {
public static void selectSort(DataWrap[] dataWraps){
System.out.println("開始排序");
int arrayLen = dataWraps.length;
for (int i = 0; i < arrayLen - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arrayLen; j++) {
if (dataWraps[minIndex].compareTo(dataWraps[j]) > 0){
minIndex = j;
}
}
if (minIndex != i){
DataWrap tmp = dataWraps[i];
dataWraps[i] = dataWraps[minIndex];
dataWraps[minIndex] =tmp;
}
System.out.println(Arrays.toString(dataWraps));
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(49,""),
new DataWrap(30,""),
new DataWrap(16,""),
new DataWrap(9,""),
new DataWrap(10,""),
new DataWrap(3,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
selectSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}
直接選擇排序算法：時間複雜度： O(n * n)
空間複雜度： O(1)
穩定性： 不穩定
2. 堆排序
概念：
假設有N個資料元素的序列k0,k1,......,kn-1,當且僅當滿足如下關系時，可以将這組資料稱為小頂堆(小根堆)，将滿足小頂堆的資料序列順序排成一顆完全二叉樹，則此樹所有節點的值都小于其左右子節點的值。此數的根節點的值必定最小。
ki <= k2i + 1 且 ki <= k2i + 2(其中i=0,2,......,(n-1)/2)
或者，滿足如下關系時，可以将這組資料稱為大頂堆(大根堆)，将滿足大頂堆的資料序列順序排成一顆完全二叉樹，則此樹所有節點的值都大于其左右子節點的值。此數的根節點的值必定最大。
ki >= k2i + 1 且 ki >= k2i + 2(其中i=0,2,......,(n-1)/2)
堆排序算法的思路：建堆先将要排序的數組轉換為完全二叉樹。
從完全二叉樹的最後一個非葉子節點開始，保證該節點的值大于等于其左、右子節點的值。如果其子節點的值大于它本身的值，則把它和較大的子節點進行交換。最後一個節點的索引為數組長度-1，即len-1，則最後一個非葉子節點的索引應該為(len-2)/2。
向前處理前一個非葉子節點(索引為(len-2) / 2 - 1)。
向前處理前一個非葉子節點，若某個節點和它的某個子節點交換後，該子節點又有子節點，那麼系統還需要再次對該子節點進行判斷。
2. 拿堆的根節點和最後一個節點交換
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class HeapSort {
public static void heapSort(DataWrap[] dataWraps) {
System.out.println("開始排序");
int arrayLen = dataWraps.length;
for (int i = 0; i < arrayLen - 1; i++) {
buildMaxdHeap(dataWraps,arrayLen - 1 - i);
swap(dataWraps,0,arrayLen - 1 - i);
System.out.println(Arrays.toString(dataWraps));
}
}
private static void swap(DataWrap[] dataWraps, int initialIndex, int newIndex) {
DataWrap tmp = dataWraps[initialIndex];
dataWraps[initialIndex] = dataWraps[newIndex];
dataWraps[newIndex] = tmp;
}
private static void buildMaxdHeap(DataWrap[] dataWraps, int lastIndex) {
for (int i = (lastIndex - 1) / 2; i >= 0 ; i--) {
// 儲存目前正在判斷的節點 int k = i;
while (k * 2 + 1 <= lastIndex){
int biggerIndex = 2 * k + 1;
if (biggerIndex < lastIndex){
if (dataWraps[biggerIndex].compareTo(dataWraps[biggerIndex + 1]) < 0){
biggerIndex++;
}
}
if (dataWraps[k].compareTo(dataWraps[biggerIndex]) < 0){
swap(dataWraps,k,biggerIndex);
k = biggerIndex;
}else {
break;
}
}
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(49,""),
new DataWrap(30,""),
new DataWrap(45,""),
new DataWrap(12,""),
new DataWrap(33,""),
new DataWrap(21,""),
new DataWrap(16,""),
new DataWrap(9,""),
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
heapSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}
對于堆排序算法來說，假設有n個資料，需要進行n-1次建堆，每次建堆本身耗時為log2n，并且需要一個附加程式單元用于交換。是以：時間複雜度：O(n *
)
空間複雜度：O(1)
穩定性： 不穩定
[交換排序法]
交換排序的主體操作是對資料組中的資料不斷地進行交換操作。交換操作主要有冒泡排序和快速排序。冒泡排序
冒泡排序是最廣為人知的交換排序之一，具有算法思路簡單、容易實作的特點。
冒泡排序的執行步驟并不固定。假設對包含n個資料的一組記錄進行排序，在最壞的情況下，需要進行n-1趟比較：依次比較0和1、1和2、2和3、......、n-2和n-1索引處的元素，如果發現第一個資料大于後一個資料，則交換它們。經過第一趟比較，最大的元素排到了最後。
依次比較0和1、1和2、2和3、......、n-3和n-2索引處的元素，如果發現第一個資料大于後一個資料，則交換它們。經過第二趟比較，第二大的元素排到了倒數第2位。
......
第n-1趟依次比較0和1索引處的元素，如果發現第一個資料大于後一個資料，則交換它們。經過第n-1趟比較，第2小(第n-1)大的元素排到了第二位。
實際上，冒泡排序的每趟交換結束後，不僅能将目前最大值擠出最後面位置，還能部分理順前面的其他元素；一旦某趟沒有交換發生，即可提前結束排序。
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(DataWrap[] dataWraps){
System.out.println("開始排序");
int arrayLen = dataWraps.length;
for (int i = 0; i < arrayLen - 1; i++) {
boolean flag = false;
for (int j = 0; j < arrayLen - 1 - i; j++) {
if (dataWraps[j].compareTo(dataWraps[j + 1]) > 0){
DataWrap tmp = dataWraps[j + 1];
dataWraps[j + 1] = dataWraps[j];
dataWraps[j] = tmp;
flag = true;
}
}
System.out.println(Arrays.toString(dataWraps));
if (!flag){
break;
}
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(30,""),
new DataWrap(49,""),
new DataWrap(21,""),
new DataWrap(30,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
bubbleSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}
冒泡排序算法的時間效率是不确定的：在最好的情況下：初始資料序列已經處于有序狀态，執行1趟冒泡即可，做n-1次比較，無須任何交換。
在最壞的情況下：初始資料序列處于完全逆序狀态，算法要執行n-1趟冒泡，第i趟做了n-i次比較，執行n-i-1次對象交換。此時的比較總次數為n * (n -1) / 2，記錄移動總次數為n * (n - 1) * 3 / 2。時間複雜度： 不确定
空間複雜度： O(1)
穩定性： 穩定
2. 快速排序
總體步驟：選出指定的分界的值
将所有比分界值小的資料元素放在左邊
将所有比分界值大的資料元素放在右邊
第2、3步具體步驟：定義一個i變量，i變量從左邊第一個索引開始，找大于分界值的元素的索引，并用i來記錄它。
定義一個j變量，j變量從右邊第一個索引開始，找小于分界值的元素的索引，并用j來記錄它。
如果i < j，則交換i、j兩個索引處的元素。
重複執行以上1~3步，直到i >= j，可以判斷j左邊的資料元素都小于分界值，j右邊的資料元素都大于分界值，最後将分界值和j索引處的元素交換即可。
示例代碼：
package com.atschool.algothrim;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class QuickSort {
private static void swap(DataWrap[] dataWraps, int i, int j){
DataWrap tmp = dataWraps[i];
dataWraps[i] = dataWraps[j];
dataWraps[j] = tmp;
}
private static void subSort(DataWrap[] dataWraps, int start, int end){
if (start < end){
DataWrap base = dataWraps[start];
int i = start;
int j = end + 1;
while (true){
while(i < end && dataWraps[++i].compareTo(base) <= 0);
while(j > start && dataWraps[--j].compareTo(base) >= 0);
if (i < j){
swap(dataWraps,i,j);
}else {
break;
}
}
swap(dataWraps,start,j);
subSort(dataWraps,start,j - 1);
subSort(dataWraps, j + 1, end);
}
}
public static void quickSort(DataWrap[] dataWraps){
subSort(dataWraps,0,dataWraps.length - 1);
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(13,""),
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
quickSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}時間複雜度： 較好
空間複雜度： O(
)
穩定性： 包含跳躍式交換，不穩定
[插入排序法]直接插入排序
思路：
依次将待排序的資料元素按其關鍵字值的大小插入前面的有序序列。
具體步驟：(假設有一個擁有n個元素的資料序列，排序需要進行n-1趟插入操作)将第2個元素插入前面的有序子序列中，此時前面隻有一個元素，當然是有序的
将第3個元素插入前面的有序子序列中，前面兩個元素是有序的
......
n-1. 将第n個元素插入前面的有序子序列中，前面n-1個元素是有序的。
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class InsertSort {
public static void insertSort(DataWrap[] dataWraps){
System.out.println("開始排序：");
int arrayLen = dataWraps.length;
for (int i = 1; i < arrayLen; i++) {
DataWrap tmp = dataWraps[i];
if (dataWraps[i].compareTo(dataWraps[i - 1]) < 0){
int j = i - 1;
for (; j >= 0 && dataWraps[j].compareTo(tmp) > 0 ; j--) {
dataWraps[j+1] = dataWraps[j];
}
dataWraps[j + 1] = tmp;
}
System.out.println(Arrays.toString(dataWraps));
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
insertSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}時間複雜度： O(n * n)
空間複雜度： O(1)
穩定性： 穩定
2. 折半插入排序
是對直接插入排序的簡單改進。對于直接插入排序而言，當第i-1趟需要将第i個元素插入前面的0~i-1個元素的序列中時，它總是從i-1個元素開始，逐個比較每個元素，直到找到它的位置。
排序思路：
當第i-1趟需要将第i個元素插入前面的0~i-1個元素序列中時，它不會直接從i-1個元素開始逐個比較每個元素。而是：計算0~i-1索引的中間點，也就是用i索引處的元素和(0 + i - 1)/2索引處的元素進行比較，如果i索引處的元素大，就直接在(0+i-1) / 2 ~ i-1半個範圍内搜尋；反之，就在0 ~ (0 + i -1)/2半個範圍内搜尋，這就是所謂的折半
在半個範圍内搜尋時，再按第1步方法進行折半搜尋。
總是不斷折半，這樣就可以将搜尋範圍縮小到1/2、1/4、1/8。進而快速确定第i個元素的插入位置
一旦确定了第i個元素的插入位置，程式将該位置以後的元素整體後移一位，然後将第i個元素放入該位置
排序效果和直接插入基本相同，不過速度更快一些。
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class BinaryInsertSort {
public static void binaryInsertSort(DataWrap[] dataWraps){
System.out.println("開始排序：\n");
int arrayLen = dataWraps.length;
for (int i = 1; i < arrayLen; i++) {
DataWrap tmp = dataWraps[i];
int low = 0;
int high = i -1;
while (low <= high){
int mid = (low + high) / 2;
if (tmp.compareTo(dataWraps[mid]) > 0){
low = mid + 1;
}else {
high = mid -1;
}
}
for (int j = i; j > low; j--) {
dataWraps[j] = dataWraps[j-1];
}
dataWraps[low] = tmp;
System.out.println(Arrays.toString(dataWraps));
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,""),
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
binaryInsertSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}時間複雜度： O(n * n)
空間複雜度： O(1)
穩定性： 穩定
3. Shell排序
基本思路：通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進行插入排序，進而使資料項大跨度地移動。這些資料項排過一趟序後，Shell排序算法減少資料項的間隔再進行排序，依次進行下去。這些進行排序的資料項之間的間隔被稱為增量，習慣上用h來表示這個增量。
例如：
假設有一個包含9項資料的序列，當h增量為4時，第1趟将保證索引為0、4、8的資料元素已經有序。第1趟完成後，算法向右移一步，對索引為1、5的資料元素進行排序。這個排序過程持續進行，直到所有的資料項都已經完成了以4為增量的排序。即，所有間隔為4的資料項之間都已經排列有序。接下來應該減少增量，直到完成以1為增量的shell排序，此時資料序列将會變為有序序列。
特點：完成某個增量的排序後，相關元素達到基本有序的狀态
通過建立交錯的内部有序的資料項集合，減少直接插入排序中資料項“整體搬家”的工作量
從上面描述可知：
最終确定Shell排序算法的關鍵就在于确定h序列的值。常用的h序列由Knuth提出，該序列從1開始，通過如下公式産生：
h = 3 * h + 1
比直接插入排序更高效的原因：當h值大的時候，資料項每一趟排序需要移動元素的個數很少，但資料項移動的距離很長
當h減小時，每一趟排序需要移動的元素的個數增多，但此時資料項已經接近于它們排序後最終的位置，資料項移動的距離短。
直接插入排序是以1為增量的Shell排序
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class ShellSort {
public static void shellSort(DataWrap[] dataWraps){
System.out.println("開始排序：");
int arrayLen = dataWraps.length;
int h = 1;
while (h <= arrayLen / 3){
h = h * 3 + 1;
}
while (h > 0){
System.out.println("=======h的值：" + h + "======");
for (int i = h; i < arrayLen; i++) {
DataWrap tmp = dataWraps[i];
if (dataWraps[i].compareTo(dataWraps[i - h]) < 0){
int j = i - h;
for (; j >= 0 && dataWraps[j].compareTo(tmp) > 0 ; j-= h) {
dataWraps[j + h] = dataWraps[j];
}
dataWraps[j + h] = tmp;
}
System.out.println(Arrays.toString(dataWraps));
}
h = (h - 1) / 3;
}
}
public static void main(String[] args) {
DataWrap[] dataWrap = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWrap));
shellSort(dataWrap);
System.out.println("排序之後：\n" + Arrays.toString(dataWrap));
}
}時間複雜度： O(
) ~ O(
)
空間複雜度： O(1)
穩定性： 穩定
[歸并排序法]
思路：
将兩個(或以上)有序的序列合并成一個新的有序序列。
大概步驟：
先将程度為n的無序序列看成是n個長度為1的有序子序列，首先做到兩兩合并，得到n/2個長度為2的有序子序列，再做兩兩合并......，不斷地重複這個過程，最終可以得到一個長度為n的有序序列。也就是說，對于長度為n的資料序列，隻需經過log2n次合并。
具體步驟：定義變量i，i從0開始，依次等于A序列中每個元素的索引
定義變量j，j從0開始，依次等于B序列中每個元素的索引
拿A序列中i索引處的元素和B序列中j索引處的元素進行比較，将較小的複制到一個臨時數組
如果i索引處的元素小，則i++；如果j索引處的元素小，則j++
不斷地重複上面四個步驟，即可将A、B兩個序列中的資料元素複制到臨時數組中，直到其中一個數組中的所有元素都被複制到臨時數組中。最後将另一個數組中剩餘的元素全部複制到臨時數組中，合并即完成，再将臨時數組中的資料複制回去即可。
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(DataWrap[] dataWraps) {
sort(dataWraps,0,dataWraps.length - 1);
}
private static void sort(DataWrap[] dataWraps, int left,int right){
if (left < right){
int center = (left + right) / 2;
sort(dataWraps,left,center);
sort(dataWraps,center + 1, right);
merge(dataWraps,left,center,right);
}
}
private static void merge(DataWrap[] dataWraps, int left, int center, int right) {
DataWrap[] tmpArr = new DataWrap[dataWraps.length];
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right){
if (dataWraps[left].compareTo(dataWraps[mid]) <= 0){
tmpArr[third++] = dataWraps[left++];
}else {
tmpArr[third++] = dataWraps[mid++];
}
}
while(mid <= right){
tmpArr[third++] = dataWraps[mid++];
}
while (left <= center){
tmpArr[third++] = dataWraps[left++];
}
//将中間數組中的内容複制回原數組 while (tmp <= right){
dataWraps[tmp] = tmpArr[tmp++];
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
mergeSort(dataWraps);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}時間複雜度： O(n *
)
空間複雜度： 較高
穩定性： 穩定
[桶式排序法]
該排序法不再是基于比較的排序方法，排序方式非常巧妙，需要待排序序列滿足如下兩個特征：待排序序列的所有值處于一個可枚舉範圍内
待排序序列所在的這個可枚舉範圍不應該太大，否則排序開銷太大
假設有如下待排序序列：
5, 4, 2, 4, 1
這個待排序序列處于0, 1, 2, 3, 4, 5這個可枚舉範圍内，而且這個範圍很小，可使用桶式排序：
具體步驟：對這個可枚舉範圍建構一個buckets數組，用于記錄“落入”每個桶中的元素的個數
按如下公式對上述buckets數組的元素進行重新計算
buckets[i] = buckets[i] + buckets[i-1] (1 <= i <= buckets.length)
示例代碼：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class BucketSort {
public static void bucketSort(DataWrap[] dataWraps, int min, int max){
System.out.println("開始排序：");
int arrayLen = dataWraps.length;
DataWrap[] tmp = new DataWrap[arrayLen];
int[] buckets = new int[max - min];
for (int i = 0; i < arrayLen; i++) {
buckets[dataWraps[i].data - min]++;
}
System.out.println(Arrays.toString(buckets));
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
System.out.println(Arrays.toString(buckets));
System.arraycopy(dataWraps,0,tmp,0,arrayLen);
//根據buckets數組中的資訊将待排序序列的各元素放入相應的位置 for (int k = arrayLen - 1; k >= 0 ; k--) {
dataWraps[--buckets[tmp[k].data - min]] = tmp[k];
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(5,""),
new DataWrap(-1,""),
new DataWrap(8,""),
new DataWrap(5,""),
new DataWrap(7,""),
new DataWrap(3,""),
new DataWrap(-3,""),
new DataWrap(1,""),
new DataWrap(3,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
bucketSort(dataWraps, -3, 10);
System.out.println("排序之後：\n" + Arrays.toString(dataWraps));
}
}時間複雜度： 極低
空間複雜度： 較高
穩定性： 穩定
[基數排序法]
基數排序必須依賴于另外的排序方法。
總體思路：
将待排序資料裡的排序關鍵字拆分成多個排序關鍵字進行排序，然後，根據子關鍵字對待排資料進行排序。
兩種解決方案：最高位優先法MSD(Most Significant Digit first)
最低位優先法LSD(Least Significant Digit first)
例如，對如下資料序列進行排序：
192, 221, 13, 23
該序列中，每個資料至多有3位，是以可以将每個資料拆分成3個關鍵字：百位(高位)、十位、個位(低位)。
使用基數排序法時，計算機會優先選擇最地位優先法，如下所示：第1輪對個位關鍵字排序：221, 192, 12, 23
第2輪對十位關鍵字排序：13, 23, 221, 192
第3輪對百位關鍵字排序：13, 23, 192, 221
要求：對任一子關鍵字排序需要借助另一種排序方法
上述排序方法必須是穩定的
是以桶式排序算法最合适。
示例代碼：
package com.atschool;
import java.util.Arrays;
public class MultiKeyRadixSort {
public static void radixSort(int[] data, int radix, int d){
System.out.println("開始排序：");
int arrayLen = data.length;
int[] tmp = new int[arrayLen];
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
Arrays.fill(buckets,0);
System.arraycopy(data, 0 ,tmp, 0, arrayLen);
for (int j = 0; j < arrayLen; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
for (int m = arrayLen - 1; m >= 0 ; m--) {
int subKey = (tmp[m] / rate) % radix;
data[--buckets[subKey]] = tmp[m];
}
System.out.println("對" + rate + "位上子關鍵字排序：" + Arrays.toString(data));
rate *= radix;
}
}
public static void main(String[] args) {
int[] data = {1100,192,221,12,13};
System.out.println("排序之前：\n" + Arrays.toString(data));
radixSort(data,10,4);
System.out.println("排序之後：\n" + Arrays.toString(data));
}
}