计数排序的思想，时间空间复杂度细致分析以及java源代码实现

本文主要是介绍计数排序的思想，时间空间复杂度细致分析以及java源代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考文章：http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html

京东笔试的时候问了很多计数排序相关的东西，因为自己只了解了一些常用的排序，对于计数排序并没有深入研究导致答得不好，特别补上。

1. 计数排序的思想

计数排序是基于非比较排序，主要用于对于一定范围内的整数进行排序。采用的是空间换时间的方法。

假设序列中小于a的整数有n个，则应该把a放在n+1的位置，同时对于相同的整数要做调整不能把所有的整数都放在一个位置。

2.算法步骤

1.首先统计每一位上元素的个数

2,统计小于等于该位元素的个数

3.从后往前，将每个元素放到应该放置的位置。

3. java源代码实现

public class CountSort {public static void main(String args[]){int[] a={3,4,5,3,3,5,4,7,6,8,5,6};int[] b=sort(a);for(int i=0;i<b.length;i++){System.out.println(b[i]);}}public static int[] sort(int[] a){int len=a.length;if(len<=1) return a;int min=a[0];int max=a[0];for(int i=0;i<len;i++){if(a[i]<min) min=a[i];if(a[i]>max) max=a[i];}//辅助数组的长度int k=max-min+1;//辅助数组cint[] c=new int[k];//统计某一位的元素的个数for(int i=0;i<len;i++){c[a[i]-min]++;}//统计小于等于该位的元素个数for(int i=1;i<k;i++){c[i]=c[i]+c[i-1];}//把每一位放到应该的位置上int[] b=new int[len];for(int i=len-1;i>=0;i--){int value=a[i];//找到该值应该放置的位置int pos=c[value-min];b[pos-1]=value;c[value-min]--;}return b;}
}