我了解了快速排序以及如何在递归和迭代方法中实现它。
迭代法：
- 将范围
(0...n)推入堆栈 - 用枢轴对给定数组进行分区
- 弹出顶部元素
- 如果分区(索引范围)包含多个元素，则将其推送到堆栈上
- 执行以上3个步骤，直到堆栈为空
递归版本是wiki中定义的正常版本。
我了解到递归算法总是比迭代算法慢。
那么，就时间复杂性而言，哪种方法是首选的(内存不是一个问题)
哪一个足够快，可以在编程竞赛中使用
C++STLsort()是否使用递归方法？
就(渐近)时间复杂性而言，它们都是相同的
"递归比迭代慢"-该语句背后的合理性是因为递归堆栈的开销(在调用之间保存和恢复环境)。
然而，这些是恒定数量的操作，而不改变"；迭代"；。
递归和迭代快速排序都是O(nlogn)平均情况和O(n^2)最坏情况。
编辑：
为了好玩，我运行了一个带有(java)代码的基准测试，然后我运行了wilcoxon统计测试，以检查运行时间确实不同的概率是多少
结果可能是决定性的(p_ VALUE＝2.6e-34，https://en.wikipedia.org/wiki/P-value.记住P_VALUE是P(T>=T|H)，其中T是检验统计量，H是零假设)。但答案并不是你所期望的。
迭代解的平均值为408.86ms，而递归解的平均为236.81ms
(注意-我使用了Integer而不是int作为recursiveQsort()的参数-否则递归会取得更好的效果，因为它不必装箱很多整数，这也很耗时-我这样做是因为迭代解决方案别无选择，只能这样做。
因此，您的假设是不正确的，递归解决方案比p_VALUE=2.6e-34的迭代解决方案更快(至少对我的机器和java来说)。
public static void recursiveQsort(int[] arr,Integer start, Integer end) {
if (end - start < 2) return; //stop clause
int p = start + ((end-start)/2);
p = partition(arr,p,start,end);
recursiveQsort(arr, start, p);
recursiveQsort(arr, p+1, end);
}
public static void iterativeQsort(int[] arr) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
stack.push(arr.length);
while (!stack.isEmpty()) {
int end = stack.pop();
int start = stack.pop();
if (end - start < 2) continue;
int p = start + ((end-start)/2);
p = partition(arr,p,start,end);
stack.push(p+1);
stack.push(end);
stack.push(start);
stack.push(p);
}
}
private static int partition(int[] arr, int p, int start, int end) {
int l = start;
int h = end - 2;
int piv = arr[p];
swap(arr,p,end-1);
while (l < h) {
if (arr[l] < piv) {
l++;
} else if (arr[h] >= piv) {
h--;
} else {
swap(arr,l,h);
}
}
int idx = h;
if (arr[h] < piv) idx++;
swap(arr,end-1,idx);
return idx;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String... args) throws Exception {
Random r = new Random(1);
int SIZE = 1000000;
int N = 100;
int[] arr = new int[SIZE];
int[] millisRecursive = new int[N];
int[] millisIterative = new int[N];
for (int t = 0; t < N; t++) {
for (int i = 0; i < SIZE; i++) {
arr[i] = r.nextInt(SIZE);
}
int[] tempArr = Arrays.copyOf(arr, arr.length);
long start = System.currentTimeMillis();
iterativeQsort(tempArr);
millisIterative[t] = (int)(System.currentTimeMillis()-start);
tempArr = Arrays.copyOf(arr, arr.length);
start = System.currentTimeMillis();
recursvieQsort(tempArr,0,arr.length);
millisRecursive[t] = (int)(System.currentTimeMillis()-start);
}
int sum = 0;
for (int x : millisRecursive) {
System.out.println(x);
sum += x;
}
System.out.println("end of recursive. AVG = " + ((double)sum)/millisRecursive.length);
sum = 0;
for (int x : millisIterative) {
System.out.println(x);
sum += x;
}
System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length);
}
这就是我在Javascript中提出的解决方案。我认为它有效。
const myArr = [33, 103, 3, 726, 200, 984, 198, 764, 9]
document.write('initial order :', JSON.stringify(myArr), '<br><br>')
qs_iter(myArr)
document.write('_Final order :', JSON.stringify(myArr))
function qs_iter(items) {
if (!items || items.length <= 1) {
return items
}
var stack = []
var low = 0
var high = items.length - 1
stack.push([low, high])
while (stack.length) {
var range = stack.pop()
low = range[0]
high = range[1]
if (low < high) {
var pivot = Math.floor((low + high) / 2)
stack.push([low, pivot])
stack.push([pivot + 1, high])
while (low < high) {
while (low < pivot && items[low] <= items[pivot]) low++
while (high > pivot && items[high] > items[pivot]) high--
if (low < high) {
var tmp = items[low]
items[low] = items[high]
items[high] = tmp
}
}
}
}
return items
}如果你发现错误，请告诉我：)
Mister Jojo UPDATE：
这段代码只是混合了在极少数情况下可以导致排序的值，换句话说，永远不会。对于那些有疑问的人，我把它放在摘录中。
那么，首选哪种方法
两者都不存在，即两者同时存在。根据amit的回答修改recursiveQsort函数，它就是
public static void recIterQsort(int[] arr, int start, int end) {
while (end - start >= 2) { // iteratively,
int p = start + ((end-start)/2);
p = partition(arr,p,start,end);
if( p-start < end-p) // sort shorter part, recursively
{
recIterQsort(arr, start, p);
start = p+1; // "call" recIterQsort(arr, p+1, end);
}
else
{
recIterQsort(arr, p+1, end);
end = p; // "call" recIterQsort(arr, start, p);
}
}
}
递归地对一个部分进行排序，我们继续对循环中的其余部分进行排序。这种转换相当于执行尾调用优化，消除了递归调用，这是递归函数中的最后一个操作。
首先对较短的部分进行排序，递归的深度保证不大于log(n)，因此递归不是问题。并且迭代不必在没有Stack的情况下手动记账，所以可以只使用int索引。