页面中的代码参考 http://alienryderflex.com/quicksort/提出一个大胆的主张：
STACK我的实现不使用堆栈来存储数据......
然而函数定义中有许多自动存储的变量，其中有 2 个具有 1000 个条目的数组，它们最终将使用固定但大量的堆栈空间：
// quickSort
//
// This public-domain C implementation by Darel Rex Finley.
//
// * Returns YES if sort was successful, or NO if the nested
// pivots went too deep, in which case your array will have
// been re-ordered, but probably not sorted correctly.
//
// * This function assumes it is called with valid parameters.
//
// * Example calls:
// quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4
// quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7
bool quickSort(int *arr, int elements) {
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ;
beg[0]=0; end[0]=elements;
while (i>=0) {
L=beg[i]; R=end[i]-1;
if (L<R) {
piv=arr[L]; if (i==MAX_LEVELS-1) return NO;
while (L<R) {
while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R];
while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; }
arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; }
else {
i--; }}
return YES; }
缩进样式非常混乱。这是重新格式化的版本：
#define MAX_LEVELS 1000
bool quickSort(int *arr, int elements) {
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;
beg[0] = 0;
end[0] = elements;
while (i >= 0) {
L = beg[i];
R = end[i] - 1;
if (L < R) {
piv = arr[L];
if (i == MAX_LEVELS - 1)
return NO;
while (L < R) {
while (arr[R] >= piv && L < R)
R--;
if (L < R)
arr[L++] = arr[R];
while (arr[L] <= piv && L < R)
L++;
if (L < R)
arr[R--] = arr[L];
}
arr[L] = piv;
beg[i + 1] = L + 1;
end[i + 1] = end[i];
end[i++] = L;
} else {
i--;
}
}
return YES;
}
注意1000很大，但对于已排序的中等大型数组上的病理情况来说还不够。函数返回NO对于大小仅为 1000 的数组，这是不可接受的。
A much lower value would suffice with an improved version of the algorithm where the larger range is pushed into the array and the loop iterates on the smaller range. This ensures that an array of N entries can handle a set of 2N entries. It still has quadratic time complexity on sorted arrays but at least would sort arrays of all possible sizes.
这是经过修改和检测的版本：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_LEVELS 64
int quickSort(int *arr, size_t elements) {
size_t beg[MAX_LEVELS], end[MAX_LEVELS], L, R;
int i = 0;
beg[0] = 0;
end[0] = elements;
while (i >= 0) {
L = beg[i];
R = end[i];
if (L + 1 < R--) {
int piv = arr[L];
if (i == MAX_LEVELS - 1)
return -1;
while (L < R) {
while (arr[R] >= piv && L < R)
R--;
if (L < R)
arr[L++] = arr[R];
while (arr[L] <= piv && L < R)
L++;
if (L < R)
arr[R--] = arr[L];
}
arr[L] = piv;
if (L - beg[i] > end[i] - R) {
beg[i + 1] = L + 1;
end[i + 1] = end[i];
end[i++] = L;
} else {
beg[i + 1] = beg[i];
end[i + 1] = L;
beg[i++] = L + 1;
}
} else {
i--;
}
}
return 0;
}
int testsort(int *a, size_t size, const char *desc) {
clock_t t = clock();
size_t i;
if (quickSort(a, size)) {
printf("%s: quickSort failure\n", desc);
return 1;
}
for (i = 1; i < size; i++) {
if (a[i - 1] > a[i]) {
printf("%s: sorting error: a[%zu]=%d > a[%zu]=%d\n",
desc, i - 1, a[i - 1], i, a[i]);
return 2;
}
}
t = clock() - t;
printf("%s: %zu elements sorted in %.3fms\n",
desc, size, t * 1000.0 / CLOCKS_PER_SEC);
return 0;
}
int main(int argc, char *argv[]) {
size_t i, size = argc > 1 ? strtoull(argv[1], NULL, 0) : 1000;
int *a = malloc(sizeof(*a) * size);
if (a != NULL) {
for (i = 0; i < size; i++)
a[i] = rand();
testsort(a, size, "random");
for (i = 0; i < size; i++)
a[i] = i;
testsort(a, size, "sorted");
for (i = 0; i < size; i++)
a[i] = size - i;
testsort(a, size, "reverse sorted");
for (i = 0; i < size; i++)
a[i] = 0;
testsort(a, size, "constant");
free(a);
}
return 0;
}
Output:
random: 100000 elements sorted in 7.379ms
sorted: 100000 elements sorted in 2799.752ms
reverse sorted: 100000 elements sorted in 2768.844ms
constant: 100000 elements sorted in 2786.612ms
这是一个稍微修改过的版本，对病理情况更具抵抗力：
#define MAX_LEVELS 48
int quickSort(int *arr, size_t elements) {
size_t beg[MAX_LEVELS], end[MAX_LEVELS], L, R;
int i = 0;
beg[0] = 0;
end[0] = elements;
while (i >= 0) {
L = beg[i];
R = end[i];
if (R - L > 1) {
size_t M = L + ((R - L) >> 1);
int piv = arr[M];
arr[M] = arr[L];
if (i == MAX_LEVELS - 1)
return -1;
R--;
while (L < R) {
while (arr[R] >= piv && L < R)
R--;
if (L < R)
arr[L++] = arr[R];
while (arr[L] <= piv && L < R)
L++;
if (L < R)
arr[R--] = arr[L];
}
arr[L] = piv;
M = L + 1;
while (L > beg[i] && arr[L - 1] == piv)
L--;
while (M < end[i] && arr[M] == piv)
M++;
if (L - beg[i] > end[i] - M) {
beg[i + 1] = M;
end[i + 1] = end[i];
end[i++] = L;
} else {
beg[i + 1] = beg[i];
end[i + 1] = L;
beg[i++] = M;
}
} else {
i--;
}
}
return 0;
}
Output:
random: 10000000 elements sorted in 963.973ms
sorted: 10000000 elements sorted in 167.621ms
reverse sorted: 10000000 elements sorted in 167.375ms
constant: 10000000 elements sorted in 9.335ms
作为结论：
- 是的，无需递归即可实现快速排序，
- 不，如果没有任何本地自动存储，就无法实现，
- 是的，只需要恒定数量的额外空间，但这只是因为我们生活在一个小世界中，数组的最大大小受可用内存的限制。本地对象的大小为 64，可以处理比 Internet 大小更大的数组，比当前 64 位系统可以寻址的数组大得多。
