c - C 中的快速排序递归函数 - 不适用于大量元素

Question

这个函数写得正确吗？

当我尝试运行数组中包含大量元素(例如 1000)的函数时，似乎出现了问题。

然后它似乎停止了。

int quick_sort(int n, int tablica[],int b, int a)
    {   
        if(a==n-1 || n==0) return;
        if(b==n-1) 
        {
            b=0;
            a++;        
        }

        if(tablica[b]>tablica[b+1])
        {
            bufor=tablica[b];
            tablica[b]=tablica[b+1];
            tablica[b+1]=bufor;
        }
        b++;
        return quick_sort(n,tablica,b,a);
    }

Answer 1

上面的代码即使对于小数组也不起作用，除非小数组以特定方式未排序。它将一个元素与下一个元素进行比较。如果数组是 {4,3,8,7,1} ，排序将会失败，因为它没有机制将 1 推到数组的开头。

对于较大的数组，递归次数过多，程序会达到堆栈限制并直接失败。

您可以在快速排序中使用递归，但必须控制递归的数量。例如，对于大小为 1000 的数组，您不希望递归超过 1000 次。示例:

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

void quicksort(int arr[], int low, int high)
{
    if(low < high)
    {
        int pivot = arr[high];    
        int i = (low - 1);  
        for(int j = low; j <= high - 1; j++)
        {
            if(arr[j] <= pivot)
            {
                i++;    
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[i + 1], &arr[high]);
        int pi = i + 1;

        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

int main()
{
    int arr[] = { 7,3,6,1,4,8,9,2 };
    int arrsize = sizeof(arr) / sizeof(*arr);
    quicksort(arr, 0, arrsize - 1);
    for(int i = 0; i < arrsize; i++)
        printf("%d\n", arr[i]);
    return 0;
}