java排序小整数数组的最佳排序算法是什么？

Question

根据问题标题，如果数组长度为奇数，且数组元素编号为1-10

例如

3 6 8 1 3 7 7 9 4 1

我在考虑使用heapsort？由于它是一个数组，合并排序和插入排序需要移位，效率不高

Answer 1

你应该考虑一下复杂度图表Complexity Comparison Chart。

排序算法的比较基于时间和空间复杂度的最佳、平均和最坏情况。根据这个图表，你可以看到Counting Sort方法在空间和时间复杂度上都是最好的。另一种可比较的方法是基数排序

“计数排序”最糟糕的[时间、空间]复杂度是-[O（n+k），O（k）]

“基数排序”的最差[时间、空间]复杂度为-[O（nk），O（n+k）]

Answer 2

这是我的计数排序示例

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;
}

Answer 3

如果只有10个元素，你甚至不值得为此担忧。如果有一百万，它可能开始变得重要