c - 我的快速排序分区函数

Question

我编写了这个 lomuto 类型的函数用于快速排序，但它不起作用。运行时发生段错误。我的错误在哪里？

int partition(int *a, int low, int high)
{
    int pos = low, i, pivot = a[low], temp;

    for (i = low + 1; i <= high; i++)
        if(a[i] <= pivot) {
            pos++;
            temp = a[pos];
            a[pos] = a[i];
            a[i] = temp;
        }

    return pos;
}

void quickS(int *a, int low, int high)
{
    while (low < high) {
        int pivot =  partition(a, low, high);
        quickS(a, low, pivot - 1);
        low = pivot + 1;
    }
}

Answer 1

pivot(a[low]) 看来有必要交换一下。

验证码:

#include<stdio.h>

int partition(int *a, int low, int high){
    int pos = low, i, pivot = a[low], temp;
    for (i = low + 1; i <= high; i++)
        if(a[i] <= pivot) {
            pos++;
            temp = a[pos];
            a[pos] = a[i];
            a[i] = temp;
        }
    return pos;
}

int main(){
    int data[] = { 10, 1, 2, 3 };
    int i, retvalue;
    retvalue = partition(data, 0, 4-1);
    printf("%d\n", retvalue);
    for(i = 0; i< 4; ++i)
        printf("%d ", data[i]);//10 1 2 3 : N/C 
    printf("\n");
    return 0;
}

据信，如果此类分区函数怀疑导致堆栈溢出，则重复调用将无法正常工作。