這一篇我們來(lái)看三種時(shí)間復(fù)雜度為O(n)的排序算法：桶排序只怎、計(jì)數(shù)排序、基數(shù)排序怜俐。我們把這類(lèi)時(shí)間復(fù)雜度為O(n)的排序算法叫做線(xiàn)性排序身堡。這類(lèi)排序算法之所以能夠做到線(xiàn)性時(shí)間，其實(shí)是因?yàn)樗鼈兌疾皇腔诒容^來(lái)實(shí)現(xiàn)排序的拍鲤。
1. 桶排序
1.1 什么是桶排序
桶排序的基本思想就是將數(shù)據(jù)拆分到多個(gè)有大小區(qū)分的桶里面贴谎，然后分別對(duì)每個(gè)桶里面的數(shù)據(jù)進(jìn)行排序汞扎，完成每個(gè)桶里面的數(shù)據(jù)的排序之后，按照桶與桶之間的數(shù)據(jù)的大小關(guān)系擅这，依次合并數(shù)據(jù)就得到了所要的有序序列
1.2 桶排序的性能分析
假設(shè)我們要將n條數(shù)據(jù)進(jìn)行排序澈魄，如果我們有m個(gè)桶，我們把這n條數(shù)據(jù)均勻的劃分到這m個(gè)桶里面蕾哟，每個(gè)桶里的數(shù)據(jù)就是k=n/m一忱。然后我們對(duì)每個(gè)桶使用快速排序進(jìn)行排序，時(shí)間復(fù)雜度就是O(klogk)谭确。m個(gè)桶總的時(shí)間復(fù)雜度就是O(mklogk)帘营。因?yàn)閗=n/m。所以整個(gè)事件復(fù)雜度就是O(nlog(n/m))逐哈。當(dāng)m接近n的時(shí)候芬迄，log(n/m)就是一個(gè)非常小的常數(shù)，整個(gè)桶排序的時(shí)間復(fù)雜度就接近O(n)昂秃。
它的空間復(fù)雜度O(n)禀梳，但是并不是需要兩倍的數(shù)據(jù)內(nèi)存才能進(jìn)行排序，因?yàn)榕判蜻^(guò)程中存儲(chǔ)的只是實(shí)際數(shù)據(jù)的索引
桶內(nèi)排序時(shí)選用穩(wěn)定排序算法肠骆，則它就能做到穩(wěn)定排序
1.3 桶排序?qū)?shù)據(jù)的特殊要求
桶排序看起來(lái)很快算途，但是要達(dá)到O(n)的時(shí)間復(fù)雜度，它對(duì)待排序的數(shù)據(jù)是有要求的
- 首先蚀腿，待排序的數(shù)據(jù)需要能很容易的劃分成m個(gè)桶嘴瓤，并且桶與桶之間要有天然的大小關(guān)系。
- 其次莉钙，數(shù)據(jù)在各個(gè)桶之間的分布要是比較均勻的廓脆。如果數(shù)據(jù)經(jīng)過(guò)劃分之后，有些桶里面的數(shù)據(jù)非常多磁玉，有些非常少停忿，那桶內(nèi)排序的時(shí)間復(fù)雜度就不是常量級(jí)的。極端情況下蚊伞，如果數(shù)據(jù)全部在一個(gè)桶里面的話(huà)席赂，算法的復(fù)雜度就退化成了O(nlogn)
1.4 桶排序的算法實(shí)現(xiàn)
桶排序的實(shí)現(xiàn)思路
- 根據(jù)數(shù)據(jù)范圍和預(yù)估的桶的數(shù)據(jù)容量計(jì)算桶的個(gè)數(shù)，申請(qǐng)桶空間
- 將待排序的數(shù)據(jù)劃分到各個(gè)桶中
- 對(duì)每個(gè)桶進(jìn)行排序
- 合并排序之后的桶中的數(shù)據(jù)
完整代碼如下
public static void sort(int[] array, int bucketSize) {
if (array == null || array.length < 2) {
return;
}
//計(jì)算用多少個(gè)桶來(lái)裝數(shù)據(jù)
int min = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] < min) {
min = array[i];
} else if (array[i] > max) {
max = array[i];
}
}
System.out.println("min:" + min);
System.out.println("max:" + max);
int bucketCount = (max - min) / bucketSize + 1;
System.out.println("bucketCount:" + bucketCount);
//申請(qǐng)桶空間
int[][] buckets = new int[bucketCount][bucketSize];
int[] indexArray = new int[bucketCount];
//將數(shù)據(jù)裝入桶里面
for (int i = 0; i < array.length; i++) {
int bucketIndex = (array[i] - min) / bucketSize;
if (indexArray[bucketIndex] == buckets[bucketIndex].length) {// buckets[bucketIndex]滿(mǎn)了厚柳，需要擴(kuò)容
ensureCapacity(buckets, bucketIndex);
}
buckets[bucketIndex][indexArray[bucketIndex]] = array[i];
indexArray[bucketIndex]++;
}
//對(duì)每個(gè)桶進(jìn)行排序
int k = 0;
for (int i = 0; i < bucketCount; i++) {
sort(buckets[i], 0, indexArray[i] - 1);
//合并桶中的數(shù)據(jù)
for (int j = 0; j < indexArray[i]; j++) {
array[k++] = buckets[i][j];
}
}
}
private static void sort(int[] a, int left, int right) {
if (left < right) {
int low = left;
int hight = right;
int pivot = a[low];
//找到分區(qū)點(diǎn)的位置
while (low < hight) {//有元素之間的位置交換氧枣，所以不是穩(wěn)定排序
while (low < hight && a[hight] >= pivot) {
hight--;
}
a[low] = a[hight];
while (low < hight && a[low] <= pivot) {
low++;
}
a[hight] = a[low];
}
a[low] = pivot;
//對(duì)左右兩個(gè)分區(qū)進(jìn)行排序
if (left + 1 < low) {
sort(a, left, low - 1);
}
if (right - 1 > low) {
sort(a, low + 1, right);
}
}
}
private static void ensureCapacity(int[][] buckets, int bucketIndex) {
int[] tempArr = buckets[bucketIndex];
int[] newArr = new int[tempArr.length * 2];
for (int j = 0; j < tempArr.length; j++) {
newArr[j] = tempArr[j];
}
buckets[bucketIndex] = newArr;
}
1.5 桶排序的實(shí)際應(yīng)用
桶排序比較適合用在外部排序中。比如說(shuō)有10GB的訂單數(shù)據(jù)需要按照訂單金額進(jìn)行排序别垮，但是能夠使用的內(nèi)容只有1GB便监，沒(méi)有辦法一次把所有數(shù)據(jù)都加載到內(nèi)存中來(lái)，這個(gè)時(shí)候就可以使用桶排序
具體怎么做呢？
- 先掃描一遍記錄烧董，查看訂單金額的數(shù)據(jù)范圍毁靶。假設(shè)訂單的金額范圍是1-10萬(wàn)元，我們可以把數(shù)據(jù)劃分到100個(gè)桶里面逊移，第一個(gè)桶存儲(chǔ)1元-1000元之間的訂單预吆，第二個(gè)桶存儲(chǔ)1001-2000之間的訂單，依次內(nèi)推胳泉。
- 然后我們?cè)俅伪闅v訂單記錄拐叉，開(kāi)始加載我們第一個(gè)桶需要的數(shù)據(jù)進(jìn)行排序，排好序之后寫(xiě)入到編號(hào)為001的桶中扇商。然后在加載第二個(gè)桶的數(shù)據(jù)排序凤瘦，依次類(lèi)推。
- 待所有桶中的數(shù)據(jù)都排序好了之后案铺，依次讀取這排序好的100個(gè)文件中的訂單數(shù)據(jù)蔬芥，寫(xiě)入到一個(gè)文件中，這樣文件中存儲(chǔ)的就是金額從小到大排序的訂單數(shù)據(jù)了
如果某個(gè)桶的數(shù)據(jù)規(guī)模過(guò)大控汉，依然無(wú)法用1GB的內(nèi)存排序如何處理笔诵？
再次對(duì)這個(gè)桶中的數(shù)據(jù)進(jìn)行拆分處理。比如訂單在1-1000元的記錄特別多姑子，我們可以繼續(xù)將它劃分為1-100,101-200乎婿，……901-1000。然后以同樣的方式去排序
什么是外部排序
外部排序指的是大文件的排序街佑，即待排序的記錄存儲(chǔ)在外存儲(chǔ)器上次酌，待排序的文件無(wú)法一次裝入內(nèi)存，需要在內(nèi)存和外部存儲(chǔ)器之間進(jìn)行多次數(shù)據(jù)交換舆乔，以達(dá)到排序整個(gè)文件的目的。
1.6 簡(jiǎn)單示例
使用桶排序給交易記錄按照價(jià)格來(lái)進(jìn)行排序剂公，我們把加一記錄簡(jiǎn)化成只有價(jià)格和編號(hào)id的方式
交易記錄
public static class Record {
private int money;
private String id;
...
}
桶排序算法
public static void sort(Record[] array, int bucketSize) {
if (array == null || array.length < 2) {
return;
}
//計(jì)算用多少個(gè)桶來(lái)裝數(shù)據(jù)
int min = array[0].money;
int max = array[0].money;
for (int i = 1; i < array.length; i++) {
if (array[i].money < min) {
min = array[i].money;
} else if (array[i].money > max) {
max = array[i].money;
}
}
System.out.println("min:" + min);
System.out.println("max:" + max);
int bucketCount = (max - min) / bucketSize + 1;
System.out.println("bucketCount:" + bucketCount);
//申請(qǐng)桶空間
Record[][] buckets = new Record[bucketCount][bucketSize];
int[] indexArray = new int[bucketCount];
//將數(shù)據(jù)裝入桶里面
for (int i = 0; i < array.length; i++) {
int bucketIndex = (array[i].money - min) / bucketSize;
if (indexArray[bucketIndex] == buckets[bucketIndex].length) {// buckets[bucketIndex]滿(mǎn)了希俩，需要擴(kuò)容
ensureCapacity(buckets, bucketIndex);
}
buckets[bucketIndex][indexArray[bucketIndex]] = array[i];
indexArray[bucketIndex]++;
}
//對(duì)每個(gè)桶進(jìn)行排序
int k = 0;
for (int i = 0; i < bucketCount; i++) {
// sort(buckets[i], 0, indexArray[i] - 1);//快排，不穩(wěn)定
sort2(buckets[i], indexArray[i]);//冒泡纲辽，穩(wěn)定排序
//合并桶中的數(shù)據(jù)
for (int j = 0; j < indexArray[i]; j++) {
array[k++] = buckets[i][j];
}
}
}
/**
* 冒泡
*
* @param array
*/
private static void sort2(Record[] array, int size) {
if (array == null || array.length == 1) {
return;
}
for (int i = 0; i < size; i++) {
boolean isExchanged = false;
for (int j = 0; j < size - i - 1; j++) {//這里的i表示經(jīng)過(guò)了幾次冒泡排序了颜武，經(jīng)過(guò)一次有在最后面多了一位已經(jīng)排好序的元素，所以下一次要比較的范圍也較少1
if (array[j].money > array[j + 1].money) {//只有在后面的元素大于前面的元素的時(shí)候才交互拖吼，可以保證排序的穩(wěn)定性
Record temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
isExchanged = true;
}
}
if (!isExchanged) {//當(dāng)某一趟冒泡排序中沒(méi)有交換發(fā)送的時(shí)候鳞上，說(shuō)明序列已經(jīng)有序了
break;
}
}
}
這里我們注意使用穩(wěn)定排序來(lái)做桶內(nèi)排序，保證排序的穩(wěn)定性
測(cè)試用例
@Test
public void test() {
int size = 10;
BucketSortRecord.Record[] array = new BucketSortRecord.Record[size];
for (int i = 0; i < size; i++) {
BucketSortRecord.Record person = new BucketSortRecord.Record();
person.setMoney(10 + new Random().nextInt(size));
person.setId("record_" + i);
array[i] = person;
}
print(array, " org:");
BucketSortRecord.sort(array, 2);
print(array, "sorted:");
}
測(cè)試結(jié)果
org:{money=13, name='record_0'},{money=14, name='record_1'},{money=14, name='record_2'},{money=12, name='record_3'},{money=14, name='record_4'},
sorted:{money=12, name='record_3'},{money=13, name='record_0'},{money=14, name='record_1'},{money=14, name='record_2'},{money=14, name='record_4'},
我們可以看到排序結(jié)果是穩(wěn)定的
2. 計(jì)數(shù)排序
2.1 什么是計(jì)數(shù)排序
計(jì)數(shù)排序可以看做一種特殊的桶排序吊档，每個(gè)桶里面的數(shù)據(jù)都是相同的篙议，也就不用進(jìn)行同類(lèi)排序了。當(dāng)我們要對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序的時(shí)候，我們先計(jì)算一下它的數(shù)據(jù)區(qū)間鬼贱，比如最小值是1移怯，最大值是K，則數(shù)據(jù)區(qū)間就是看这难，然后將這些數(shù)據(jù)拆分到這k個(gè)桶里面舟误，由于每個(gè)桶里面的數(shù)據(jù)都是相同的，所以我們不用進(jìn)行桶內(nèi)排序姻乓，拆分完成之后嵌溢，我們?cè)俅伪闅v每個(gè)桶，合并數(shù)據(jù)就得到了要排序的有序序列
2.2 計(jì)算排序的性能分析
計(jì)算排序在桶排序的基礎(chǔ)上省去了桶內(nèi)排序蹋岩，所以它的時(shí)間復(fù)雜度就是O(n)
它的空間復(fù)雜度O(n)
它是穩(wěn)定排序
2.3 計(jì)數(shù)排序?qū)?shù)據(jù)的特殊要求
計(jì)數(shù)排序只能用在數(shù)據(jù)范圍不大的場(chǎng)景中赖草，如果數(shù)據(jù)范圍K很大，就不適合使用計(jì)數(shù)排序了星澳。因?yàn)樗枰暾?qǐng)與范圍同樣大小的空間來(lái)進(jìn)行計(jì)數(shù)疚顷，范圍太大，內(nèi)存就可能不夠了禁偎。
2.4 計(jì)數(shù)排序的算法實(shí)現(xiàn)
計(jì)數(shù)排序算法實(shí)現(xiàn)思路
- 計(jì)算數(shù)據(jù)之間的區(qū)間腿堤，申請(qǐng)計(jì)數(shù)數(shù)組
- 遍歷待排序數(shù)組，計(jì)算每個(gè)元素的個(gè)數(shù)如暖，存入計(jì)數(shù)數(shù)組的對(duì)應(yīng)位置
- 計(jì)算計(jì)數(shù)數(shù)組中元素在將來(lái)排好序的序列中的位置
- 遍歷待排序數(shù)組笆檀，結(jié)合計(jì)數(shù)數(shù)組，將待排序數(shù)據(jù)存入到存放有序序列的數(shù)組的對(duì)應(yīng)位置
算法實(shí)現(xiàn)
public static void sort(int[] array) {
/**
* 計(jì)數(shù)排序的的步驟
* 1. 計(jì)算數(shù)據(jù)之間的區(qū)間盒至，申請(qǐng)計(jì)數(shù)數(shù)組
* 2. 遍歷待排序數(shù)組酗洒，計(jì)算每個(gè)元素的個(gè)數(shù)，存入計(jì)數(shù)數(shù)組的對(duì)應(yīng)位置
* 3. 計(jì)算計(jì)算數(shù)組中元素在將來(lái)排好序的序列中的位置
* 4. 遍歷待排序數(shù)組枷遂，結(jié)合計(jì)數(shù)數(shù)組樱衷，將待排序數(shù)據(jù)存入到存放有序序列的數(shù)組的對(duì)應(yīng)位置
*/
if (array == null || array.length < 2) {
return;
}
//1. 計(jì)算數(shù)據(jù)分別的區(qū)間，申請(qǐng)計(jì)數(shù)數(shù)組
int min = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] < min) {
min = array[i];
} else if (array[i] > max) {
max = array[i];
}
}
System.out.println("min:" + min);
System.out.println("max:" + max);
int interval = max - min;
System.out.println("interval:" + interval);
int[] c = new int[interval + 1];
//2. 遍歷待排序數(shù)組酒唉，計(jì)算每個(gè)元素的個(gè)數(shù)矩桂，存入計(jì)數(shù)數(shù)組的對(duì)應(yīng)位置
for (int i = 0; i < array.length; i++) {
c[array[i] - min]++;
}
//3. 計(jì)算計(jì)算數(shù)組中元素在將來(lái)排好序的序列中的位置
for (int i = 1; i < c.length; i++) {
c[i] = c[i - 1] + c[i];
}
//4. 遍歷待排序數(shù)組，結(jié)合計(jì)數(shù)數(shù)組痪伦，將待排序數(shù)據(jù)存入到存放有序序列的數(shù)組的對(duì)應(yīng)位置
int[] temp = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {//倒序保證穩(wěn)定性
int index = c[array[i] - min] - 1;
temp[index] = array[i];
c[array[i] - min]--;
}
for (int i = array.length - 1; i >= 0; i--) {
array[i] = temp[i];
}
}
2.5 計(jì)數(shù)排序的實(shí)際應(yīng)用
計(jì)數(shù)排序可以應(yīng)用在考試成績(jī)的排名上侄榴，比如高考成績(jī)的快速排名。
假如高考總分是900分网沾，最小分時(shí)0分癞蚕，總共有50萬(wàn)名考生，我們就可以將這些學(xué)生劃分到901個(gè)桶里面辉哥，由于桶里面的分?jǐn)?shù)相同桦山，所以不同再進(jìn)行排序，我們只要一次掃描每個(gè)桶，將桶內(nèi)的考生依次輸出到一個(gè)數(shù)組中度苔，就能實(shí)現(xiàn)對(duì)50萬(wàn)名考生的成績(jī)的排序了匆篓。
2.6 簡(jiǎn)單實(shí)例
我們簡(jiǎn)單的實(shí)現(xiàn)一些對(duì)考生成績(jī)的排序，這里我們將考生信息簡(jiǎn)化成只有總成績(jī)和名字兩個(gè)部分
考生信息
public static class Person {
private int age;
private String name;
...
}
計(jì)數(shù)排序算法
public static void sort(Person[] array) {
/**
* 計(jì)數(shù)排序的的步驟
* 1. 計(jì)算數(shù)據(jù)分別的區(qū)間寇窑，申請(qǐng)計(jì)數(shù)數(shù)組
* 2. 遍歷待排序數(shù)組鸦概，計(jì)算每個(gè)元素的個(gè)數(shù)，存入計(jì)數(shù)數(shù)組的對(duì)應(yīng)位置
* 3. 計(jì)算計(jì)算數(shù)組中元素在將來(lái)排好序的序列中的位置
* 4. 遍歷待排序數(shù)組甩骏，結(jié)合計(jì)數(shù)數(shù)組窗市，將待排序數(shù)據(jù)存入到存放有序序列的數(shù)組的對(duì)應(yīng)位置
*/
if (array == null || array.length < 2) {
return;
}
//1. 計(jì)算數(shù)據(jù)分別的區(qū)間，申請(qǐng)計(jì)數(shù)數(shù)組
int min = array[0].age;
int max = array[0].age;
for (int i = 1; i < array.length; i++) {
if (array[i].age < min) {
min = array[i].age;
} else if (array[i].age > max) {
max = array[i].age;
}
}
System.out.println("min:" + min);
System.out.println("max:" + max);
int interval = max - min;
System.out.println("interval:" + interval);
int[] c = new int[interval + 1];
//2. 遍歷待排序數(shù)組饮笛，計(jì)算每個(gè)元素的個(gè)數(shù)咨察，存入計(jì)數(shù)數(shù)組的對(duì)應(yīng)位置
for (int i = 0; i < array.length; i++) {
c[array[i].age - min]++;
}
//3. 計(jì)算計(jì)算數(shù)組中元素在將來(lái)排好序的序列中的位置
for (int i = 1; i < c.length; i++) {
c[i] = c[i - 1] + c[i];
}
//4. 遍歷待排序數(shù)組，結(jié)合計(jì)數(shù)數(shù)組福青，將待排序數(shù)據(jù)存入到存放有序序列的數(shù)組的對(duì)應(yīng)位置
Person[] temp = new Person[array.length];
for (int i = array.length - 1; i >= 0; i--) {
int index = c[array[i].age - min] - 1;
temp[index] = array[i];
c[array[i].age - min]--;
}
for (int i = array.length - 1; i >= 0; i--) {
array[i] = temp[i];
}
}
測(cè)試代碼
@Test
public void test() {
int size = 5;
CountingSortPerson.Person[] array = new CountingSortPerson.Person[size];
for (int i = 0; i < size; i++) {
CountingSortPerson.Person person = new CountingSortPerson.Person();
person.setAge(10 + new Random().nextInt(5));
person.setName("name_" + i);
array[i] = person;
}
print(array, " org:");
CountingSortPerson.sort(array);
print(array, "sorted:");
}
測(cè)試結(jié)果
org:{age=10, name='name_0'},{age=13, name='name_1'},{age=12, name='name_2'},{age=11, name='name_3'},{age=11, name='name_4'},
sorted:{age=10, name='name_0'},{age=11, name='name_3'},{age=11, name='name_4'},{age=12, name='name_2'},{age=13, name='name_1'},
3. 基數(shù)排序
3.1 什么是基數(shù)排序
基數(shù)排序是一種多關(guān)鍵字的排序算法摄狱，其中每個(gè)關(guān)鍵字可以使用線(xiàn)性排序算法來(lái)完成排序，通過(guò)依次對(duì)每個(gè)關(guān)鍵字進(jìn)行排序之后无午，就得到了要的有序序列媒役。這里要求每個(gè)關(guān)鍵字使用的線(xiàn)性排序要能保證穩(wěn)定性。
3.2 基數(shù)排序的性能分析
基數(shù)排序使用其他線(xiàn)性排序來(lái)完成關(guān)鍵字的排序宪迟，所以它的時(shí)間復(fù)雜度也是O(n)酣衷，空間復(fù)雜度O(n)，它是穩(wěn)定排序
3.3 基數(shù)排序?qū)?shù)據(jù)的特殊要求
基數(shù)排序?qū)?shù)據(jù)的要求:
- 待排序的數(shù)據(jù)必須能夠分割成多個(gè)關(guān)鍵字來(lái)比較次泽，且關(guān)鍵字之間有遞進(jìn)關(guān)系穿仪，比如a的高位比b的高位大，則a必定大于b意荤。
- 關(guān)鍵字的范圍不能太大啊片，要可以使用線(xiàn)性排序算法來(lái)排序。
3.4 基數(shù)排序的算法實(shí)現(xiàn)
這里直接編寫(xiě)一個(gè)對(duì)手機(jī)號(hào)碼進(jìn)行排序的算法
算法實(shí)現(xiàn)思路
- 拆分關(guān)鍵字
- 分別對(duì)每個(gè)關(guān)鍵字進(jìn)行線(xiàn)性排序
代碼實(shí)現(xiàn)
public static void sort(int[] array) {
// 從個(gè)位開(kāi)始玖像，對(duì)數(shù)組arr按"指數(shù)"進(jìn)行排序
for (int exp = 1; array[0] / exp > 0; exp *= 10) {
countingSort(array, exp);
}
}
private static void countingSort(int[] array, int exp) {
if (array == null || array.length < 2) {
return;
}
//1. 計(jì)算數(shù)據(jù)分別的區(qū)間钠龙，申請(qǐng)計(jì)數(shù)數(shù)組
int[] c = new int[10];
//2. 遍歷待排序數(shù)組，計(jì)算每個(gè)元素的個(gè)數(shù)御铃，存入計(jì)數(shù)數(shù)組的對(duì)應(yīng)位置
for (int i = 0; i < array.length; i++) {
c[(array[i] / exp) % 10]++;
}
//3. 計(jì)算計(jì)算數(shù)組中元素在將來(lái)排好序的序列中的位置
for (int i = 1; i < c.length; i++) {
c[i] = c[i - 1] + c[i];
}
//4. 遍歷待排序數(shù)組，結(jié)合計(jì)數(shù)數(shù)組沈矿，將待排序數(shù)據(jù)存入到存放有序序列的數(shù)組的對(duì)應(yīng)位置
int[] temp = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {//倒序保證穩(wěn)定性
int cindex = (array[i] / exp) % 10;
temp[c[cindex] - 1] = array[i];
c[cindex]--;
}
for (int i = array.length - 1; i >= 0; i--) {
array[i] = temp[i];
}
}
測(cè)試用例
@Test
public void test1() {
int size = 10;
int[] array = new int[size];
int[] array2 = new int[size];
for (int i = 0; i < size; i++) {
int num = 1;
for (int j = 0; j < 5; j++) {
num = num * 10 + new Random().nextInt(10);
}
array[i] = num;
array2[i] = num;
}
print(array, " org:");
print(array2, " org:");
RadixSort.sort(array);
MergeSort.sort(array2);
print(array, "sorted:");
print(array2, "sorted:");
}
測(cè)試結(jié)果
org:186402,159502,111311,107840,111943,191059,181161,147774,143482,199457,
org:186402,159502,111311,107840,111943,191059,181161,147774,143482,199457,
sorted:107840,111311,111943,143482,147774,159502,181161,186402,191059,199457,
sorted:107840,111311,111943,143482,147774,159502,181161,186402,191059,199457,
這里我們采用歸并排序來(lái)做一個(gè)結(jié)果對(duì)比上真，驗(yàn)證排序的正確性
3.5 基數(shù)排序的實(shí)際應(yīng)用
基數(shù)排序還可以用在單詞的排序中等場(chǎng)景
源碼
完整源碼和測(cè)試用例，請(qǐng)查看github之排序
- 桶排序：BucketSort.java羹膳、BucketSortTest.java睡互、BucketSortRecord.java、BucketSortRecordTest.java
- 計(jì)數(shù)排序：CountingSort.java、CountingSortTest.java就珠、CountingSortPerson.java寇壳、CountingSortPersonTest.java
- 基數(shù)排序：RadixSort.java、RadixSortTest.java
說(shuō)明
算法示意圖來(lái)源：算法動(dòng)畫(huà)演示網(wǎng)站
