c - 如何在我的实现 QuickSort 中防止堆栈溢出？

Question

我的快速排序有问题。当我尝试按降序对数字数组进行排序时，我的指针不会穿过数组，并且堆栈溢出。也许问题不在指针中，但我没有看到这个问题的解决方案。

我的代码:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>
#include <stdbool.h>
#include <assert.h>
int Icmp(void* x, void* y);
bool SpecTest(int (*cmp)(const void*, const void*), int (*dcmp)(const void*, const void*));
int Dcmp(void* x, void* y);
void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*));

int main(void)
{
    int (*cmp)(void* x, void* y) = Icmp;
    int (*dcp)(void* x, void* y) = Dcmp;
    assert(SpecTest(cmp, dcp));
    return 0;
}

bool SpecTest(int (*cmp)(const void*, const void*), int (*dcmp)(const void*, const void*))
{
    typedef struct testArr {
        int* arr;
        size_t size;
    }testArr;
    testArr s3;//Back sorted array struct
    s3.size = 100;
    if ((s3.arr = (int*)malloc(sizeof(int) * s3.size)) == NULL) {
        return false;
    }
    for (int i = 0; i < s3.size; i++) {
        s3.arr[i] = s3.size - i;
    }
    my_qsort(s3.arr, s3.size, sizeof(s3.arr[0]), cmp);
    return checksortInt(s3.arr, s3.size, cmp);
}
int Icmp(void* x, void* y)
{
    return (*(int*)x > * (int*)y) - (*(int*)x < *(int*)y);
}

int Dcmp(void* x, void* y)
{
    return (*(double*)x > * (double*)y) - (*(double*)x < *(double*)y);
}

void Swapper(void* x, void* y, size_t size)
{
    for (size_t i = 0; i < size; i++) {
        char tmp = ((char*)x)[i];
        ((char*)x)[i] = ((char*)y)[i];
        ((char*)y)[i] = tmp;
    }
}

bool checksortInt(int* parray, size_t size)
{
    for (size_t i = 0; i < size - 1; i++)
        if (parray[i] > parray[i + 1])
            return false;
    return true;
}

void my_qsort(const void* ptr, size_t count, size_t size, int (*cmp)(const void*, const void*))
{
    Quick_Sort(ptr, 0, count - 1, size, cmp);
}

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i = low;
    int j = high;
    char* pivot = (char*)ptr + low * size;
    while (i <= j)
    {
        while (i < high && (cmp((char*)ptr + i * size, pivot) == -1))
            i++;
        while (j > low && cmp((char*)ptr + j * size, pivot) == 1)
            j--;
        if (i <= j) {
            Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
            i++;
            j--;
        }
    }
    if (j > low)
        Quick_Sort(ptr, low, j, size, cmp);
    if (i < high)
        Quick_Sort(ptr, i, high, size, cmp);
}

示例:

输入[]:按降序排列的数字数组

输出[]:QuickSout.exe 中 0x005D1889 处未处理的异常:0xC00000FD:堆栈溢出(参数:0x00000001、0x008A2F24)。

Answer 1

如果您需要对大型数组进行排序，并且担心最坏情况下的数据模式会导致堆栈溢出，快速排序可以在较小的分区上递归并在较大的分区上循环，这将避免堆栈溢出，但最坏情况下的时间复杂度将仍然是 O(n^2)。

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i;
    int j;
    char *pivot;
    while(low < high){
        i = low;
        j = high;
        pivot = (char*)ptr + ((low+high)/2) * size;
        while (i <= j)
        {
            while (cmp((char*)ptr + i * size, pivot) == -1)
                i++;
            while (cmp((char*)ptr + j * size, pivot) ==  1)
                j--;
            if (i <= j) {
                Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
                i++;
                j--;
            }
        }
        if (j < low)                  // adjust so low <= j <= i <= high
            j = low;
        if (i > high)
            i = high;
        if(j - low <= high - i){
                Quick_Sort(ptr, low, j, size, cmp);
            low = j + 1;
        } else {
            if (i < high)
                Quick_Sort(ptr, i, high, size, cmp);
            high = i - 1;
        }
    }
}

<小时/>

这个替代版本稍微简单一些。

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i;
    int j;
    char *pivot;
    while(low < high){
        i = low-1;
        j = high+1;
        pivot = (char*)ptr + ((low+high)/2) * size;
        while (1)
        {
            while (cmp((char*)ptr + ++i * size, pivot) == -1);
            while (cmp((char*)ptr + --j * size, pivot) ==  1);
            if (i >= j)
                break;
            Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
        }
        if(j - low <= high - j){
            Quick_Sort(ptr, low, j, size, cmp);
            low = j+1;
        } else {
            Quick_Sort(ptr, j+1, high, size, cmp);
            high = j;
        }
    }
}

<小时/>

没有堆栈溢出防护的替代版本:

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i;
    int j;
    char *pivot;
    if(low >= high)
        return;
    i = low-1;
    j = high+1;
    pivot = (char*)ptr + ((low+high)/2) * size;
    while (1)
    {
        while (cmp((char*)ptr + ++i * size, pivot) == -1);
        while (cmp((char*)ptr + --j * size, pivot) ==  1);
        if (i >= j)
            break;
        Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
    }
    Quick_Sort(ptr, low, j, size, cmp);
    Quick_Sort(ptr, j+1, high, size, cmp);
}