static int[] countingSort(int[] numbers) {
int max = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] > max)
max = numbers[i];
}
int[] sortedNumbers = new int[max+1];
for (int i = 0; i < numbers.length; i++) {
sortedNumbers[numbers[i]]++;
}
int insertPosition = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < sortedNumbers[i]; j++) {
numbers[insertPosition] = i;
insertPosition++;
}
}
return numbers;
}
# 1 楼答案
你应该考虑一下复杂度图表Complexity Comparison Chart。
排序算法的比较基于时间和空间复杂度的最佳、平均和最坏情况。根据这个图表,你可以看到Counting Sort方法在空间和时间复杂度上都是最好的。另一种可比较的方法是基数排序
“计数排序”最糟糕的[时间、空间]复杂度是-[O(n+k),O(k)]
“基数排序”的最差[时间、空间]复杂度为-[O(nk),O(n+k)]
# 2 楼答案
这是我的计数排序示例
# 3 楼答案
如果只有10个元素,你甚至不值得为此担忧。如果有一百万,它可能开始变得重要