灵光一闪的排序算法与靠谱的计数排序

自己闲来没事乱写的排序算法

假设我们有正要待排序的数组A，它的区间是[0,k],0~k均是有限大小的整数。接下来我们初始化一个k+1长度的数据B，并把它所有的值都初始化为-1（只因为它是负数，可以用来区别将要进行排序的数据，因为要排序的数据都>=0）。
那我们现在就有两个数组了。假设A数组的值是{5,0,2,3,1}:

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数组的值

从B数组我们也就知道了A数组中的信息。第三步，我们需要一个新的数组C，用来保存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}这里我故意加了个重复元素

A与B初始化

2.在A的值对应B的下标加1

对B进行赋值

上图B数组中表示A中0有一个，1有0个，2有两个，3有一个，4有零个,5有一个。

3. B[i]=B[i]+B[i-1]

B数组最终的样子

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

有种在以前上学时打草稿的感觉。