没有堆栈和递归，可以用C实现快速排序吗？

Question

我找到了这篇文章 How to do iterative quicksort without using stack in c?但建议的答案确实使用了内联堆栈数组! (只允许有固定数量的额外空间)

Answer 1

页面中的代码reference提出一个大胆的主张:

STACK My implementation does not use the stack to store data...

然而函数定义有许多自动存储的变量，其中 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 很大，但对于已排序的中等大数组的病态情况来说还不够。对于大小仅为 1000 的此类数组，该函数返回 NO，这是 Not Acceptable 。

对于算法的改进版本，一个低得多的值就足够了，其中较大的范围被插入数组并且循环在较小的范围上迭代。这确保了 N 个条目的数组可以处理一组 2^N 条目。它在排序数组上仍然具有二次时间复杂度，但至少可以对所有可能大小的数组进行排序。

这是一个经过修改和检测的版本:

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

输出:

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

输出:

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 位系统可以处理的数组大得多。