搞不懂的算法-排序篇<2>

　　上一篇排序算法<1>中，排序算法的时间复杂度从N²到NlgN变化，但他们都有一个共同的特点，基于比较和交换数组中的元素来实现排序，我们称这些排序算法为比较排序算法。对于比较排序算法，所有的算法都可以表达成一个决策树的模型（参看MIT算法课），数的叶子节点表示比较排序的一种可能结果，树的深度为得到排序结果经过的决策次数。可以证明：N个元素最少要经过NlgN次决策才能得到排序结果。所以基于比较的排序算法时间复杂度最优情况下为NlgN，由此可知：快排(平均情况下)，归并，堆排序三者都是渐进最优的。工程上较多使用快排的原因时它的优点：1、虽然它时间复杂度是从NlgN到N²变化的，但平均状况下它是NlgN的；2、相比于归并，空间复杂度更低；3、相比于堆排序，更高效的利用了计算机缓存。另外：实际应用中的排序算法，多数是综合了的排序算法，比如在N较小时使用插入排序，N较大时使用快排。因为N较小时，快排递归调用占用了排序时间的很大成本。

　　如果突破比较排序模型的限制，有没有更快的算法呢，比如时间复杂度为N的算法？有的，下面要介绍三种时间复杂度为N的算法：计数排序、基数排序、桶排序。

1、计数排序/count sort

　　计数排序的模型是这样的，假设数组中所有元素都是[0,k]的整数，我们可以建立一个常为k+1的计数数组，统计原数组中各元素出现的次数，将信息整合到计数数组中，计数数组索引为原数组的元素，计数数组的元素为原数组对应元素的出现次数。如int[] a=[5,4,3,6,2,1,7,0,6,3]，计数数组为int[] count=[1,1,1,2,1,1,2,1]，计数数组已经完全可以包含元素的信息。1个0，1个1，2个3等等，从前往后遍历计数数组，即可得到原数组的排序。代码如下：

 1 import java.util.Arrays;
 2 public class Test{
 3     public static int[] countSort(int[] a){
 4         //找出数组中最大元素k
 5         int k=a[0];
 6         for(int i=0;i<a.length;i++)
 7             if(a[i]>k) k=a[i];
 8         //辅助数组
 9         int[] b=countSort(a,k);
10         return b;
11     }
12     
13     private static int[] countSort(int[] a,int k){
14         int[] count=new int[k+1];//计数数组
15         
16         //更新计数数组，排序数组信息存储在计数数组中
17         for(int i=0;i<a.length;i++)
18             count[a[i]]++;
19         
20         //更新计数数组中信息表达方式
21         for(int i=1;i<=k;i++)
22             count[i]+=count[i-1];
23         
24         //根据计数数组和原数组更新排序后数组
25         int[] b=new int[a.length];
26         for(int i=a.length-1;i>=0;i--){
27             b[count[a[i]]-1]=a[i];
28             count[a[i]]--;
29         }
30         return b;
31     }
32     
33     public static void main(String[] args){
34         int[] a={5,4,3,6,2,1,7,0,6,3};
35         a=countSort(a);
36         System.out.println(Arrays.toString(a));         
37     }
38 }

View Code

　　这段代码有几个要注意的点：1，前面我们的排序函数都是没有返回值的，这里排序函数返回了一个数组，这是由于这里排序后的数组是新创建的一个数组，基于java引用数据参数传递的机制，所以返回了一个数组。2，在更新完计数数组后，计数数组中已经包含了原数组所有的信息，所以可以直接根据计数数组更改原数组，这样空间利用率更高。3，好像计数数组并不需要一定是k+1长的，保证原数组所有元素可以在计数数组中表示即可，比如原数组中数为9900-10000的元素。计数数组成为101即可。下面给出更新后的代码：

 1 import java.util.Arrays;
 2 public class Test{
 3     public static void countSort(int[] a){
 4         //找出a中元素最大值和最小值
 5         int hi=a[0],lo=a[0];
 6         for(int i=0;i<a.length;i++){
 7             if(a[i]>hi) hi=a[i];
 8             else if(a[i]<lo) lo=a[i];
 9         }
10         
11         //构建计数数组,更新计数数组信息
12         int[] count=new int[hi-lo+1];
13         for(int i=0;i<a.length;i++)
14             count[a[i]-lo]++;
15         
16         //根据计数数组信息，更新原数组，原数组即为排序后数组
17         int k=0; //更新原数组的索引
18         for(int i=0;i<=hi-lo;i++)
19             while(count[i]>0){
20                 a[k++]=lo+i;
21                 count[i]--;
22             }                
23     }
24     
25     public static void main(String[] args){
26         int[] a={5,4,3,6,2,1,7,0,6,3};
27         countSort(a);
28         System.out.println(Arrays.toString(a));         
29     }
30 }

View Code

　　这段代码是非常好的计数排序的实现。下面来分析下计数排序的局限性及性能：

性能：计数排序的性能是与数组元素的范围k相关的，N+k，可以看到当k很小时，计数排序的时间复杂度是线性的，~cN，当k远大于N时，时间复杂度可以变得很高。

局限：计数排序尽管当k值不大时，能达到线性的时间复杂度，但当数组中元素波动很大，导致k值很大，时间复杂度很高，更阔怕的是空间复杂度会变得很高。另外，由于计数排序是使用计数数组的索引表示元素值，用值表示原数组元素出现次数，所以就要求排序对象是[0,k]的整数（负数做下转换也是可以的）。这大大降低了这种算法的通用性。尽管如此，计数排序算法在很多地方还是很有用的，比如统计排序全国高考生的数学成绩，比如统计排序全国人民的年龄等。

搞不懂的算法-排序篇<2>

相关推荐