请允许我使用一个示例(Java 语言)来更具体一些。
假设你想对这个数组进行排序:
[10, 20, 30, 40, 50, 60, 70, 80, 90]
假设基准值为 30。排序后应该如下所示:
[40, 50, 60, 70, 80, 90, 30, 10, 20]
大于 30 的数字在 30 的左侧结束(仍按从小到大排序)，小于 30 的数字在 30 的右侧(但仍按从小到大排序)。
注意:假设数据集很大，不一定非要这个数组集合。
现在这是我想出的算法(伪代码):
1). Count how many values are more than 30, call this count value 'X'. Swap the value of 30 at index X.
2). Have 2 "movers" that start on both ends, each moving towards the pivot and determining which numbers should go on what side
3). Use bubble sort on both sides of the pivot to finish the algorithm.
现在，这是我自己算法的问题。它是 O(n)，直到我进入冒泡排序，这使得它成为 O(n^2)。
我的具体问题是:什么是更好的方法，并且仍然保持 O(n)？或者如果可能的话 O(log n) ？答案可以是伪代码，但您选择为答案编写代码，我更喜欢用 Java。
注意:该数组是整型数组。都具有独特的值(value)。
编辑:归并排序显然是比冒泡排序好得多的解决方案。我的问题实际上是为了寻找 O(n) 或 O(log n) 的解决方案。
最佳答案
首先，如果您担心时间问题，为什么要使用冒泡排序？您可以做的第一件事是用类似 Merge Sort 的算法替换冒泡排序。 ，其复杂度为 O(n log n)。
现在我告诉你不可能用O(n)或O(log n)找到更好的解决方案，假设您找到了 O(n) 甚至 O(log n) 算法解决方案。现在您可以使用 O(n) 对每个数组进行排序!因为一开始你用O(n)找到数组的最小值，然后用它作为主元然后使用你的算法，现在你有一个排序数组，它的复杂度是O( n) 这还不可能。有关 O(n log n) 的更多信息，请查看 What are the rules for the "Ω(n log n) barrier" for sorting algorithms?
您可以找到排序算法的 java 实现 here .
关于java - 我可以使用什么算法来使用 use pivots 对数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28600732/