5. 其他非基于比較的排序
5.1 計(jì)數(shù)排序
有n個(gè)數(shù)，取值范圍是 0~n，寫出一個(gè)排序算法，要求時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n)的
我們知道，前面介紹的基于比較的排序算法中，最好的算法，其平均時(shí)間復(fù)雜度都在O(N)，達(dá)到線性的時(shí)間復(fù)雜度就要使用新的排序算法，而這種方法，就稱為是計(jì)數(shù)排序。
計(jì)數(shù)排序的思路：對(duì)于每一待排序元素a，如果知道了待排序數(shù)組中有多少比它小的數(shù)，就可以直接知道排序后的數(shù)組中，a在什么位置上。比如，如果一個(gè)數(shù)組中有三個(gè)數(shù)比a小，那么排序后的數(shù)組中，a一定會(huì)出現(xiàn)在第4位。
那么現(xiàn)在問題轉(zhuǎn)化成，堆排序數(shù)組里的數(shù)，如何能快速的指導(dǎo)比它小的數(shù)字有多少。要解決這個(gè)問題，我們不能用比較的辦法，因?yàn)闀r(shí)間復(fù)雜度會(huì)高于O(N)，只有一個(gè)思路，就是用空間來換取時(shí)間。不妨設(shè)一個(gè)大小為(max - min + 1)的數(shù)組（其中max是數(shù)組中的最大值，min是數(shù)組中的最小值）來統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)。這就類似于直方圖，因此計(jì)數(shù)排序被稱作是基于統(tǒng)計(jì)的排序。
假設(shè)計(jì)數(shù)排序算法的輸入是數(shù)組arr，大小為n，而存放排序結(jié)果的數(shù)組為B，還需要一個(gè) 存放臨時(shí)結(jié)果，也就是我們上面提到的直方圖結(jié)果的數(shù)組count。那么計(jì)算排序的步驟如下：
-
在C中記錄A中各值元素的數(shù)目
for (int i = 0; i < len; i++) { count[arr[i]]++; } -
將count[i]轉(zhuǎn)換成小于等于i的元素個(gè)數(shù)
for (int i = 1; i < max + 1; i++) { count[i] += count[i-1]; } -
為A數(shù)組從后向前的每個(gè)元素找到對(duì)應(yīng)的B中的位置。每次從A中復(fù)制一個(gè)元素到B中，C中相應(yīng)的數(shù)-1。
for (int i = len - 1; i >= 0; i--) { int n = count[arr[i]]; b[n - 1] = arr[i]; count[arr[i]]--; } -
當(dāng)A中的元素都復(fù)制到B中后，B就是排好序的結(jié)果。然后再將結(jié)果賦值給A。
下面為完整代碼
public void countSort(int[] arr) {
int len = arr.length;
int max = arr[0];
for(int i = 1; i < len; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
int[] count = new int[max + 1];//以數(shù)據(jù)的范圍作為計(jì)數(shù)數(shù)組的大小
int[] b = new int[len];
for (int i = 0; i < len; i++) {
count[arr[i]]++;
}
for (int i = 1; i < max + 1; i++) {
count[i] += count[i-1];
}
for (int i = len - 1; i >= 0; i--) {
int n = count[arr[i]];
b[n - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < len; i++) {
arr[i] = b[i];
}
}
需要注意的是,出現(xiàn)多個(gè)元素相同的情況時(shí)，每當(dāng)arr[i]放入b中，count[arr[i]]都要減一，這樣，下一個(gè)與arr[i]相等的元素出現(xiàn)的時(shí)候，被放在arr[i]的前面，從而保證了數(shù)組的穩(wěn)定性。
總結(jié)：
- 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場景有限。
- 時(shí)間復(fù)雜度：O(N)
- 空間復(fù)雜度：O(N)
- 穩(wěn)定。
計(jì)數(shù)排序還有另外一種做法：只需要一個(gè)待排數(shù)組和一個(gè)計(jì)數(shù)數(shù)組就能做。
大體思路就是：
-
找出待排序元素中的最大值和最小值，確定待排序元素的數(shù)據(jù)范圍，然后根據(jù)范圍確定計(jì)數(shù)數(shù)組的大小。
int min = arr[0]; int max = arr[0]; for (int i = 0; i < arr.length; i++) { if(arr[i] < min) { min = arr[i]; } if (arr[i] > max) { max = arr[i]; } } int len = max - min + 1; int[] count = new int[len]; -
遍歷arr數(shù)組，記錄每個(gè)待排序元素出現(xiàn)的次數(shù)。這里要注意的是，怎么將count數(shù)組下標(biāo)和arr[i]的之聯(lián)系起來。
舉個(gè)例子：
arr = [91,92,99,92,93,92,99,98，94], max = 99, min = 91我們應(yīng)該這樣進(jìn)行計(jì)數(shù)：
我現(xiàn)在要記錄
91出現(xiàn)的次數(shù)，91應(yīng)該放在計(jì)數(shù)數(shù)組的0下標(biāo)，也就是count[0]，91 - min = 0，所以我們可以推出來一個(gè)等式，設(shè)count下標(biāo)為n，設(shè)當(dāng)前待排序元素的數(shù)值為val，n + min = valfor (int i = 0; i < arr.length; i++) { count[arr[i] - min]++; } -
上述循環(huán)走完，計(jì)數(shù)數(shù)組已經(jīng)存好了對(duì)應(yīng)關(guān)系，遍歷計(jì)數(shù)數(shù)組，給arr數(shù)組重新賦值。
int k = 0; for (int i = 0; i < len; i++) { int n = count[i];//記錄元素出現(xiàn)的次數(shù) while (n != 0) { arr[k++] = i + min;//運(yùn)用等式關(guān)系 n--; } }
下面為完整代碼：
public static void countArray(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if(arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
int len = max - min + 1;
int[] count = new int[len];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
int k = 0;
for (int i = 0; i < len; i++) {
int n = count[i];
while (n != 0) {
arr[k++] = i + min;
n--;
}
}
}
這個(gè)方法寫出來的排序不一定是穩(wěn)定的，但是計(jì)數(shù)排序一定是穩(wěn)定的。
5.2 桶排序
桶排序的思想就是：劃分成多個(gè)范圍相同的區(qū)間，將待排序元素放入對(duì)應(yīng)的區(qū)間，每個(gè)區(qū)間內(nèi)部進(jìn)行排序，最后合并。
桶排序可以看成計(jì)數(shù)排序的擴(kuò)展版本，計(jì)數(shù)排序可以看作每個(gè)桶放相同的元素，而桶排序中每個(gè)桶儲(chǔ)存一定范圍內(nèi)的元素。
知道了思想，我們就可以寫出相應(yīng)代碼：
-
得出最大值和最小值。
int max = arr[0]; int min = arr[0]; for(int i = 1; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } -
計(jì)算桶的數(shù)量，桶可以用ArrayList來表示。
int count = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(count); for(int i = 0; i < count; i++){ bucketArr.add(new ArrayList<>());//分配內(nèi)存 } -
將每個(gè)元素放入相應(yīng)桶內(nèi)
for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } -
對(duì)每個(gè)桶進(jìn)行排序
for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); //這個(gè)方法是專門對(duì)實(shí)現(xiàn)List接口的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序 } -
將桶中的元素賦值給原數(shù)組
int index = 0; for(int i = 0; i < bucketArr.size(); i++){ for(int j = 0; j < bucketArr.get(i).size(); j++){ arr[index++] = bucketArr.get(i).get(j); } }
完整代碼：
public static void bucketSort(int[] arr){
int max = arr[0];
int min = arr[0];
for(int i = 1; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int count = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(count);
for(int i = 0; i < count; i++){
bucketArr.add(new ArrayList<>());//分配內(nèi)存
}
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
//這個(gè)方法是專門對(duì)實(shí)現(xiàn)List接口的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序
}
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
arr[index++] = bucketArr.get(i).get(j);
}
}
}
總結(jié)
-
時(shí)間復(fù)雜度：O(N*(log(N/M)+1))
設(shè)數(shù)組元素有N個(gè)，桶有M個(gè)，平均每個(gè)桶有N/M個(gè)元素。
主要步驟有
- 每個(gè)元素放入桶中O(N)
- 對(duì)每個(gè)桶進(jìn)行排序，一共有M次，每次復(fù)雜度為O((N/M)*log(N/M))，所以為O(M*(N/M)*log(N/M))
O(N) + O(M*(N/M)*log(N/M)) = O(N*(log(N/M)+1))
當(dāng)N == M時(shí)，復(fù)雜度為O(N)
-
空間復(fù)雜度：O(M + N)
-
穩(wěn)定性：取決于桶內(nèi)排序的算法
5.3 基數(shù)排序
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
基數(shù)排序也運(yùn)用到了桶，根據(jù)元素的每位數(shù)字來分配桶
下面是具體步驟：
-
獲得待排序元素中，最大元素的位數(shù)
int maxDigit = getMaxDigit(arr); private static int getMaxDigit(int[] arr) { int maxValue = getMaxValue(arr);//獲取最大元素 return getNumLength(maxValue);//獲取最高位數(shù) } private static int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) { if (maxValue < value) { maxValue = value; } } return maxValue; } private static int getNumLength(long num) { if (num == 0) { return 1; } int length = 0; for (long temp = num; temp != 0; temp /= 10) { length++; } return length; } -
根據(jù)元素的每一位數(shù)字，對(duì)其進(jìn)行排序。
1.怎么遍歷元素的每一位數(shù)字呢？
我們可以創(chuàng)建一個(gè)循環(huán)，循環(huán)的次數(shù)是最大位數(shù)，在每一次循環(huán)中遍歷元素的每位數(shù)字。
2.那如何得到元素的每位數(shù)字呢？
舉個(gè)例子，假如我們要得到361這個(gè)數(shù)字的個(gè)位數(shù)字1，先%10，得到1，再/1；要得到十位數(shù)字6，先%100，得到61，再/10，得到6；要得到百位數(shù)字3，先%1000，得到361，再/100，得到3。
發(fā)現(xiàn)規(guī)律了嗎？隨著位數(shù)從個(gè)位到百位，我們%的數(shù)字和/的數(shù)字也以10倍增長，這樣我們便可以利用循環(huán)，在每次循環(huán)中，對(duì)此進(jìn)行*10操作。
3.現(xiàn)在我們得到了每位數(shù)字，如何對(duì)他進(jìn)行排序呢？
就如同上面的動(dòng)圖，我們可以創(chuàng)建一個(gè)二維數(shù)組arr[10][]，分別對(duì)應(yīng)0~9，然后把相應(yīng)的數(shù)字放入數(shù)組中，然后再從arr[0][]開始，將數(shù)組中的元素一個(gè)個(gè)放回到原數(shù)組，就完成了本輪排序。
現(xiàn)在我們把比較重要的3步都已經(jīng)理解清楚了，下面就是實(shí)現(xiàn)代碼：
private static int[] sort(int[] arr, int maxDigit) { int mod = 10; int dev = 1; for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { int[][] counter = new int[20][0]; //這里設(shè)定成20，是因?yàn)榭紤]到了負(fù)數(shù)，[0,10)存儲(chǔ)負(fù)數(shù)，[10,20)存儲(chǔ)正數(shù) for (int j = 0; j < arr.length; j++) { int bucket = ((arr[j] % mod) / dev) + 10; //(arr[j] % mod) / dev：得到每位數(shù)字 //+10是因?yàn)榭紤]了負(fù)數(shù)，比如說得到的該位數(shù)字為-1，就把他存儲(chǔ)到arr[9]中。 counter[bucket] = arrayAppend(counter[bucket], arr[j]); //給數(shù)組擴(kuò)容，因?yàn)橐婚_始創(chuàng)建沒有分配內(nèi)存。然后添加元素 } int pos = 0; for (int[] bucket : counter) { for (int value : bucket) { arr[pos++] = value;//重新賦值 } } } return arr; } private static int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; }
完整代碼如下：
public static void radixSort (int[] arr){
int maxDigit = getMaxDigit(arr);
sort(arr, maxDigit);
}
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLength(maxValue);
}
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected static int getNumLength(long num) {
if (num == 0) {
return 1;
}
int length = 0;
for (long temp = num; temp != 0; temp /= 10) {
length++;
}
return length;
}
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
private static int[] sort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
int[][] counter = new int[20][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + 10;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;//重新賦值
}
}
}
return arr;
}
總結(jié)
-
時(shí)間復(fù)雜度：O(k*N)
設(shè)最大位數(shù)為k位
外層循環(huán)O(k)，內(nèi)層循環(huán)O(N)，整體是O(k*N)
-
空間復(fù)雜度：O(N)
-
穩(wěn)定性：穩(wěn)定
十大排序算法已經(jīng)全部更新完啦！??累鼠了累鼠了??
如果想了解其他的排序算法，可以移步到我的前兩篇文章呦文章來源：http://www.zghlxwxcb.cn/news/detail-454327.html
- 十大排序算法（上）直接插入排序、希爾排序、直接選擇排序、堆排序
- 十大排序算法（中）：冒泡排序，快速排序（遞歸和非遞歸）、歸并排序（遞歸和非遞歸）
如果有什么疑問，歡迎在評(píng)論區(qū)給我留言，或者是私信我~文章來源地址http://www.zghlxwxcb.cn/news/detail-454327.html
到了這里，關(guān)于十大排序算法(下)：計(jì)數(shù)排序，基數(shù)排序，桶排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
