快速排序可以在没有堆栈和递归的C语言中实现吗？

ru9i0ody 于 2022-12-03 发布在其他

关注(0)|答案(5)|浏览(305)

我发现这篇文章How to do iterative quicksort without using stack in c?，但建议的答案确实使用了内联堆栈数组！（只允许常量的额外空间）

来源：https://stackoverflow.com/questions/55008384/can-quicksort-be-implemented-in-c-without-stack-and-recursion

5条答案

按热度按时间

lrpiutwd1#

reference页面中的代码做了一个大胆的声明：

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很大，但对于已经排序的中等大小数组的病态情况来说是不够的。函数只在大小为1000的数组上返回NO，这是不可接受的。
一个更小的值对于算法的改进版本就足够了，在改进版本中，较大的范围被推入数组，循环在较小的范围上迭代。这确保了一个N个条目的数组可以处理一组2N个条目。它在排序数组上仍然具有二次时间复杂度，但至少可以对所有可能大小的数组进行排序。
下面是一个经过修改和检测的版本：

#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位系统所能处理的大得多。

赞(0）回复(0）举报 2022-12-03

r55awzrz2#

显然，可以实现一个非递归的快速排序，只需要恒定的额外空间，如here所述。这是建立在Sedgewick的work之上的，用于快速排序的非递归公式。它本质上不是保留边界值（低和高），而是执行线性扫描来确定这些边界。

赞(0）回复(0）举报 2022-12-03

z9smfwbn3#

快速排序可以在没有堆栈和递归的C语言中实现吗？
快速排序要求从每个非平凡分区向前遵循两条路径：每一个（子）分区的新的分区。关于以前分区的信息（一个结果分区的边界）需要被传递到每一个新的分区。那么问题是，这些信息在哪里？特别是，当程序在一个分区上工作时，关于另一个分区的信息在哪里？
对于串行算法，答案是将信息存储在堆栈、队列或它们的功能等价物中。总是这样，因为这些是我们为所需目的服务的数据结构的名称。特别是，递归是一种特殊情况，而不是替代方案。在递归快速排序中，数据存储在调用栈中。对于迭代实现，你可以实现一个正式意义上的栈，但也可以使用一个简单的、相对较小的数组作为临时栈。
但是，堆栈和队列的等价物可以做得更远，例如，你可以把数据附加到一个文件中，以便以后读回;你可以把它写入一个管道;你可以通过一个通信网络把它异步地传输给你自己。
如果你够聪明的话，你甚至可以让输入数组本身满足堆栈的需要，方法是使用相对元素顺序或其他元素属性对分区边界进行编码，例如Ďurian所描述的。这涉及到空间 * 与速度 * 的权衡，在大多数情况下可能不是一个好主意。然而，它的空间开销（O（1））比典型的快速排序实现（O（log N））要低，并且它不改变算法的O（N log N）渐近时间复杂度。
如果你想疯掉，你甚至可以用嵌套迭代来代替递归。这会对可以处理的数组大小强加一个硬上限，但并不像你想象的那么紧。只要小心一些，再加上一些技巧，你就可以用一个25循环的嵌套来处理十亿元素的数组。这样一个深嵌套会很难看，也很疯狂。但仍然是可以想象的。一个人可以手工编写它。在这种情况下，一系列嵌套的循环作用域，以及它们的块作用域变量，作为一个栈的等价物。
因此，答案取决于“无堆栈”的确切含义：