自己闲来没事乱写的排序算法
假设我们有正要待排序的数组A，它的区间是[0,k],0~k均是有限大小的整数。接下来我们初始化一个k+1长度的数据B，并把它所有的值都初始化为-1（只因为它是负数，可以用来区别将要进行排序的数据，因为要排序的数据都>=0）。
那我们现在就有两个数组了。假设A数组的值是{5,0,2,3,1}:
原谅我自己手画的，工作时间挤出来，见谅见谅。
因为A数组中最大的为5，那B数组中数组长度为(5+1)，为6，初始化之后B数组的初始值为-1。
接下来就是给B数组赋值了。我们把A数组中的值对应B数组的下标，把A数组中的下标对应B数组的值，比如:A[0]=5->B[5]=0,A[1]=0->B[0]=1;这样我们就可根据B数组知道:A中的5存储在下标为0，也就是第一个位置上，A中的0保存在下标为1也就是第二个位置上。这样操作了之后如下图:
从B数组我们也就知道了A数组中的信息。第三步，我们需要一个新的数组C，用来保存A数组中的信息。
如下：
这个C数组会在接下来说明。接下来我们我们将一个一个的从B数组中取出数据用来当C数组的下标取出重新赋值给A数组。按前面的我们知道，从B数组我们知道，A数组中最小的是下标为1的位置。接下来是下标为4的位置，最大的数据在下标为0 的位置。处理之后,A数组就变成了:
java实现代码:
public void sort(int[] aDatas) {
//根据A数组中的最大值得到B数组中长度
int bDataLength = getMaxNum(aDatas)+1;
//得到A与C数组的长度
int cLength = aDatas.length;
//接下来初始化C数组
int[] cDatas = new int[cLength];
for (int i = 0; i < cLength; i++) {
cDatas[i] = aDatas[i];
}
//接下来处理B数组中的值
int[] bDatas = new int[bDataLength];
for (int i = 0; i < bDataLength; i++) {
bDatas[i] = -1;
}
//根据A数组赋值给B数组
for (int i = 0; i < cLength; i++) {
bDatas[aDatas[i]] = i; }
//用于记录A数组中的有效位置
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]);
}}
来看看结果
0
1
2
3
5
然后觉得不对，我这样写如果有重复的元素，肯定排序就不正确。当然可以再用一个数组D来记录下重复的元素。可是这样就太麻烦了，太复杂了，并且要排序的数据不要太大，要不然B数组太大，效率也不高。后来回家翻了下算法导论发现计数排序和我这个非常相似。书是好东西，得经常翻翻。
计数排序
现在可以进入正题了。
应该都知道冒泡排序，快速排序，选择排序等等都是通过比较两个数据大小来进行排序的。而它们的时间复杂度以及稳定性如下 :
计数排序是时间效率为O(n)的计数排序。所谓排序算法，无非就是把正确的元素放到正确的位置，计数排序就是计算相同key的元素各有多少个，然后根据出现的次数累加而获得最终的位置信息。但是计数排序有两个限制条件，那就是存在一个正整数K，使得数组里面的所有元素的key值都不大于N，且key值都是非负整数。
计数排序算法步骤大概有三个步骤：
- 建一个长度为K+1的的数组B，里面的每一个元素初始都置为0(Java里面默认就是0)。我自己写的是将B数组初始化为一个固定负数，如-1
- 遍历待排序的数组，计算其中的每一个元素出现的次数，比如一个key为i的元素出现了3次，那么C[i]=3。这里是记录元素出现的次数，我只是记录下标，所以我不能处理重复数据，而计数法可以
- 累加B数组，获得元素的排位，从0开始遍历B, B[i+1]=B[i]+B[i-1]
- 建一个临时数组C，长度与待排序数组一样。从数组末尾遍历待排序数组，把元素都安排到C里面，直接从B里面就可以得到元素的具体位置， 不过记得每处理过一个元素之后都要把B里面对应位置的计数减1。为什么要从末尾开始遍历呢，是为保证排序算法的稳定性。
现在又用的我手工图给大家讲解一下：
1.假设A数组内容为{5,0,2,3,2}这里我故意加了个重复元素
2.在A的值对应B的下标加1
上图B数组中表示A中0有一个，1有0个，2有两个，3有一个，4有零个,5有一个。
- B[i]=B[i]+B[i-1]
4.新建一个数组C与A有相同的值,从数组末尾遍历A数组，直接从B里面就可以得到元素的具体位置， 不过记得每处理过一个元素之后都要把B里面对应位置的计数减1。
这里图显示一下前两次循环的结果：
下面是java的实现代码：
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
有种在以前上学时打草稿的感觉。
