C语言——快速排序

Question

我试图用 c 编写一个快速排序程序，但我的递归函数处于无限循环中。

问题是：

你得到了一个数组尺寸A N.This 数组包含的整数范围从 1至 10^9。您需要按值对这个数组的内容进行排序，然后打印它的内容。

输入格式：

第一行包含一个整数N，表示数组的大小。下一行包含 N space 个分隔的整数，表示数组的内容。

输出格式：

打印N个space个分隔的整数，即最终排序的数组。

约束条件：

1≤N≤10^6

1≤A[i]≤10^9

void fill_vet(unsigned int a[], unsigned int n){
    int i;
    for(i=0; i<n; i++)
        scanf("%u", &a[i]);
}

void print_vet(unsigned int a[], unsigned int n){
    int i;
    for(i=0; i<n; i++)
        printf("%u ", a[i]);
}

int partition(unsigned int a[], int start, int end){
    int i, j;
    unsigned int pivot, n_swap;
    i = start + 1;
    pivot = a[start];
    for(j = start+1; j<=end; j++){
        if(a[j] < pivot){
            n_swap = a[j];
            a[j] = a[i];
            a[i] = n_swap;
            i++;
        }
    } 
    n_swap = a[i-1];
    a[i-1] = a[start];
    a[start] = n_swap;
    return i-1;
}

void sort_array(unsigned int a[], int start, int end){
    while(start < end){
        int pos_piv = partition(a, start, end);
        sort_array(a, start, pos_piv-1);
        sort_array(a, pos_piv+1, end);
    }
}

int main()
{
    unsigned int n, a[100000];
    scanf("%u", &n);
    fill_vet(a, n);
    sort_array(a, 0, n-1);
    print_vet(a, n);
    return 0;
}

你能告诉我错误在哪里吗！

Answer 1

您正在使用递归，因此不需要循环：

void sort_array(unsigned int a[], int start, int end){
  if(start < end){
    int pos_piv = partition(a, start, end);
    sort_array(a, start, pos_piv-1);
    sort_array(a, pos_piv+1, end);
  }
}

C语言——快速排序

Language C - QuickSort

c

quicksort

infinite-loop