排序小整数数组的最佳排序算法是什么？
根据问题标题，如果数组的长度为奇数，则数组元素的编号为1 – 10。
例，
3 6 8 1 3 7 7 9 4 1
我在考虑使用heapsort ？ 由于它是一个数组，因此合并排序和插入排序需要移位，并且不会那么高效。
数组元素的数字是1-10。
有了这个限制， 计数排序将比任何通用排序算法更有效 – 它是O（n）
这是我的计数排序示例
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; }
如果只有10个元素，那么即使担心它也是不值得的。 如果有一百万，它可能会开始变得重要。
编辑：计算排序可能是最佳的，因为约束条件的元素范围仅为1-10。 应用于此问题的计数排序将在O（n）时间内运行。 合并排序（我在下面推荐）的运行时间不会超过O（nlogn）时间。 并行计数排序可能很有趣。 只需为每个处理器分配一个带有n / p元素的子arrays。 每个处理器都有自己的大小为9的计数数组。这一步应该花费O（n / p）时间。 然后将所有计数数组合并为一个数组，这应该花费O（p）时间。 我没有完全考虑计数排序的最后一步，元素按顺序排列，但似乎只要count数组的元素是primefaces的，你可以将原始数组的n / p部分分配给个体处理器并实现一些并行化。 然而，计数数组的各个元素会存在争用，可能会大大降低并发性。 您可能能够将计数数组的子部分分配给p个处理器，并且如果元素分布相当均匀，则返回到O（n / p）运行时，但是您将限制为10个处理器。 如果元素不均匀分布，则一个或多个处理器可以执行更大比例的工作。 这是一个很好的问题; 你可以在O（n / p）时间进行计数排序吗？
Quicksort是一种很好的就地排序算法，可以快速运行并节省内存。 但是，如果元素的范围仅为1-10，那么如果要对大量元素进行排序，则最终会在初始时或在排序期间的中间时间进行相同数字的大量运行。 有序数组或子数组可能会让Quicksort的性能陷入困境。
如果你不关心记忆，一个简单的Mergesort就足够了。 Mergesort采用最快的标准排序算法。
Java 7中的默认Collections.sort（）实现是一个改编自’TimSort’的Mergesort算法。 Java 7中的默认Arrays.sort（）实现是双枢轴Quicksort。
如果你想并行，Parallel Quicksort可以在具有少量处理器的大型arrays上获得良好的结果，但是具有与顺序Quicksort相同的限制。 PSRS可以帮助扩展到更大数量的处理器。
您应该考虑复杂性图表复杂性比较图表 。
排序算法的比较基于时间和空间复杂度的最佳，平均，最差情况。基于此图表，您可以看到计数排序方法在空间和时间复杂性方面最佳。 其他可比方法是Radix Sort。
最糟糕的[时间，空间]“计数排序”的复杂性： – [O（n + k），O（k）]。
最差[时间，空间]“基数排序”的复杂性： – [O（nk），O（n + k）]。
这是一个简单排序的例子（插入排序）
private static void insertionSort(int[] a) { // [230, 23, 45, 34, 98] for (int j = 2; j < a.length; j++) { int key = a[j]; int i = j - 1; while (i > 0 && a[i] > key) { a[i + 1] = a[i]; i--; } a[i + 1] = key; } System.out.println("sorted array: " + Arrays.toString(a)); }
在这种情况下，计数排序将是最好的。
假设数据是整数，范围为0-k。 创建一个大小为K的数组，以跟踪显示的项目数（3个值为0的项目，4个值为1的项目等）。 根据这个计数，你可以告诉一个项目的位置 – 所有的1必须在0之后，其中有3个。因此，1从项目＃4开始。 因此，我们可以扫描物品并将它们插入正确的位置。
创建计数数组是O（N）将项目插入到它们的正确位置是O（N）我在这里过分简化了 – 计数的总和，以及保持排序稳定的最大到最小排序。