计算排序算法
本帖最后由 影-死神 于 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;
int maxValue = array;
//遍历数组寻找最大值和最小值
for (int i=1;i<array.length;i++) {
if (array < minValue) {
minValue = array;
}
if (array > maxValue) {
maxValue = array;
}
}
//新的数组并计数
int[] countList = new int;
for (int i=0;i<array.length;i++) {
countList++;
}
//输出到原数组
int index = 0;
for (int i=0;i<countList.length;i++) {
for (int j=0;j<countList;j++) {
array = 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 + " ");
}
}
}
二. 计数排序的适用场景
由于计数排序是根据下标进行排序的所以只能排序整数，而如果最大值和最小值之间的差值太大时，又过于浪费内存空间，所以适用于一定范围内差值不太大的整数的排序，此时，排序速度甚至超过快速排序。
页:
[1]