|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 影-死神 于 2018-10-18 21:03 编辑
一. 计数排序算法基本思路
1. 遍历数组,找出最大值maxValue和最小值minValue,新建一个长度为maxValue-minValue+1的数组,并初始化为0
2. 遍历数组,每个整数按照其值,对应新数组的下标(value-minvalue)加一
3. 遍历新数组,每次输出新数组的下标值加minValue的值到原数组以更新原数组,对应的值是几就输出几次
算法的时间复杂度:
由于遍历了两遍原数组和一遍新数组,所以时间复杂度为 O(2N+M) = O(n)
算法的空间复杂度:
由于新建了一个数组,所以空间复杂度为 O(N+M) = O(n)
Java代码实现:
- public class CountSort {
- public static void sort(int[] array) {
- int minValue = array[0];
- int maxValue = array[0];
-
- //遍历数组寻找最大值和最小值
- for (int i=1;i<array.length;i++) {
- if (array < minValue) {
- minValue = array;
- }
- if (array > maxValue) {
- maxValue = array;
- }
- }
-
- //新的数组并计数
- int[] countList = new int[maxValue-minValue+1];
-
- for (int i=0;i<array.length;i++) {
- countList[array-minValue]++;
- }
-
- //输出到原数组
- int index = 0;
- for (int i=0;i<countList.length;i++) {
- for (int j=0;j<countList;j++) {
- array[index] = minValue + i;
- index++;
- }
- }
- }
-
- public static void main(String[] args) {
- int[] list = {5, 8, 6, 3, 9, 2, 1, 7, 4};
-
- sort(list);
-
- for (int i=0;i<list.length;i++) {
- System.out.print(list + " ");
- }
- }
- }
复制代码
二. 计数排序的适用场景
由于计数排序是根据下标进行排序的所以只能排序整数,而如果最大值和最小值之间的差值太大时,又过于浪费内存空间,所以适用于一定范围内差值不太大的整数的排序,此时,排序速度甚至超过快速排序。 |
|