自己閑來沒事亂寫的排序算法
假設(shè)我們有正要待排序的數(shù)組A，它的區(qū)間是[0,k],0~k均是有限大小的整數(shù)撑螺。接下來我們初始化一個k+1長度的數(shù)據(jù)B吏砂，并把它所有的值都初始化為-1（只因為它是負數(shù)蝇恶，可以用來區(qū)別將要進行排序的數(shù)據(jù)拳魁，因為要排序的數(shù)據(jù)都>=0）。
那我們現(xiàn)在就有兩個數(shù)組了撮弧。假設(shè)A數(shù)組的值是{5,0,2,3,1}:
原諒我自己手畫的潘懊，工作時間擠出來，見諒見諒贿衍。
因為A數(shù)組中最大的為5授舟，那B數(shù)組中數(shù)組長度為(5+1)，為6贸辈，初始化之后B數(shù)組的初始值為-1释树。
接下來就是給B數(shù)組賦值了。我們把A數(shù)組中的值對應(yīng)B數(shù)組的下標擎淤，把A數(shù)組中的下標對應(yīng)B數(shù)組的值奢啥，比如:A[0]=5->B[5]=0,A[1]=0->B[0]=1;這樣我們就可根據(jù)B數(shù)組知道:A中的5存儲在下標為0，也就是第一個位置上嘴拢，A中的0保存在下標為1也就是第二個位置上桩盲。這樣操作了之后如下圖:
從B數(shù)組我們也就知道了A數(shù)組中的信息。第三步席吴，我們需要一個新的數(shù)組C赌结，用來保存A數(shù)組中的信息。
如下：
這個C數(shù)組會在接下來說明抢腐。接下來我們我們將一個一個的從B數(shù)組中取出數(shù)據(jù)用來當(dāng)C數(shù)組的下標取出重新賦值給A數(shù)組姑曙。按前面的我們知道襟交，從B數(shù)組我們知道迈倍，A數(shù)組中最小的是下標為1的位置。接下來是下標為4的位置捣域，最大的數(shù)據(jù)在下標為0 的位置啼染。處理之后,A數(shù)組就變成了:
java實現(xiàn)代碼:
public void sort(int[] aDatas) {
//根據(jù)A數(shù)組中的最大值得到B數(shù)組中長度
int bDataLength = getMaxNum(aDatas)+1;
//得到A與C數(shù)組的長度
int cLength = aDatas.length;
//接下來初始化C數(shù)組
int[] cDatas = new int[cLength];
for (int i = 0; i < cLength; i++) {
cDatas[i] = aDatas[i];
}
//接下來處理B數(shù)組中的值
int[] bDatas = new int[bDataLength];
for (int i = 0; i < bDataLength; i++) {
bDatas[i] = -1;
}
//根據(jù)A數(shù)組賦值給B數(shù)組
for (int i = 0; i < cLength; i++) {
bDatas[aDatas[i]] = i; }
//用于記錄A數(shù)組中的有效位置
int numberLeng = 0;
//進行大小位置正確放置
for (int i = 0; i < bDataLength; i++) {
if (bDatas[i] != -1) {
int index = bDatas[i];
int temp = cDatas[index];
aDatas[numberLeng] = temp;
numberLeng++;
}
}
}
public int getMaxNum(int[] datas) {
int max = 0;
int length = datas.length;
for (int i = 0; i < length; i++) {
if (datas[i] > max) {
max = datas[i];
}
}
return max ;
}
public static void main(String[] args) {
int[] datas = new int[]{5,0,2,3,1};
new BucketSort().sort(datas);
for (int i = 0; i < datas.length; i++) {
System.out.println(datas[i]);
}}
來看看結(jié)果
0
1
2
3
5
然后覺得不對宴合，我這樣寫如果有重復(fù)的元素，肯定排序就不正確迹鹅。當(dāng)然可以再用一個數(shù)組D來記錄下重復(fù)的元素卦洽。可是這樣就太麻煩了斜棚，太復(fù)雜了阀蒂，并且要排序的數(shù)據(jù)不要太大，要不然B數(shù)組太大弟蚀，效率也不高蚤霞。后來回家翻了下算法導(dǎo)論發(fā)現(xiàn)計數(shù)排序和我這個非常相似。書是好東西义钉，得經(jīng)常翻翻昧绣。
計數(shù)排序
現(xiàn)在可以進入正題了。
應(yīng)該都知道冒泡排序捶闸，快速排序夜畴，選擇排序等等都是通過比較兩個數(shù)據(jù)大小來進行排序的。而它們的時間復(fù)雜度以及穩(wěn)定性如下 :
計數(shù)排序是時間效率為O(n)的計數(shù)排序删壮。所謂排序算法贪绘，無非就是把正確的元素放到正確的位置，計數(shù)排序就是計算相同key的元素各有多少個央碟，然后根據(jù)出現(xiàn)的次數(shù)累加而獲得最終的位置信息兔簇。但是計數(shù)排序有兩個限制條件，那就是存在一個正整數(shù)K硬耍，使得數(shù)組里面的所有元素的key值都不大于N垄琐，且key值都是非負整數(shù)。
計數(shù)排序算法步驟大概有三個步驟：
- 建一個長度為K+1的的數(shù)組B经柴，里面的每一個元素初始都置為0(Java里面默認就是0)狸窘。我自己寫的是將B數(shù)組初始化為一個固定負數(shù)，如-1
- 遍歷待排序的數(shù)組坯认，計算其中的每一個元素出現(xiàn)的次數(shù)翻擒，比如一個key為i的元素出現(xiàn)了3次，那么C[i]=3牛哺。這里是記錄元素出現(xiàn)的次數(shù)陋气，我只是記錄下標，所以我不能處理重復(fù)數(shù)據(jù)引润，而計數(shù)法可以
- 累加B數(shù)組巩趁，獲得元素的排位，從0開始遍歷B, B[i+1]=B[i]+B[i-1]
- 建一個臨時數(shù)組C淳附，長度與待排序數(shù)組一樣议慰。從數(shù)組末尾遍歷待排序數(shù)組蠢古，把元素都安排到C里面，直接從B里面就可以得到元素的具體位置别凹， 不過記得每處理過一個元素之后都要把B里面對應(yīng)位置的計數(shù)減1草讶。為什么要從末尾開始遍歷呢，是為保證排序算法的穩(wěn)定性炉菲。
現(xiàn)在又用的我手工圖給大家講解一下：
1.假設(shè)A數(shù)組內(nèi)容為{5,0,2,3,2}這里我故意加了個重復(fù)元素
2.在A的值對應(yīng)B的下標加1
上圖B數(shù)組中表示A中0有一個堕战，1有0個，2有兩個拍霜，3有一個践啄，4有零個,5有一個。
- B[i]=B[i]+B[i-1]
4.新建一個數(shù)組C與A有相同的值,從數(shù)組末尾遍歷A數(shù)組沉御，直接從B里面就可以得到元素的具體位置屿讽， 不過記得每處理過一個元素之后都要把B里面對應(yīng)位置的計數(shù)減1。
這里圖顯示一下前兩次循環(huán)的結(jié)果：
下面是java的實現(xiàn)代碼：
public static void countSort(int[] aDatas) throws Exception {
if (aDatas.length <= 1) {
return;
}
int range = getMaxNum(aDatas);
int[] bDatas = new int[range + 1];
for (int i = 0; i < aDatas.length; i++) {
int value = aDatas[i];
bDatas[value] += 1;
}
for (int i = 1; i < bDatas.length; i++) {
bDatas[i] += bDatas[i - 1];
}
int[] cDatas = new int[aDatas.length];
for (int i = aDatas.length - 1; i >= 0; i--) {
int value = aDatas[i];
int position = bDatas[value] - 1;
cDatas[position] = value;
bDatas[value] -= 1;
}
for (int i = 0; i < aDatas.length; i++) {
aDatas[i] = cDatas[i];
}
}
public static int getMaxNum(int[] datas) {
int max = 0;
int length = datas.length;
for (int i = 0; i < length; i++) {
if (datas[i] > max) {
max = datas[i];
}
}
return max;}
public static void main(String[] args) throws Exception {
int[] array = {5, 0, 2, 3, 2};
countSort(array);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}}
0
2
2
3
5
有種在以前上學(xué)時打草稿的感覺吠裆。
