正确划分 QuickSort 数组

Question

我是 C 的初学者，我一直在尝试编写一个快速排序程序，该程序可以将随机生成的实数数组及其大小作为参数，然后按升序对元素进行排序。我无法弄清楚在函数 QuickSort 的第一次递归调用中要在数组大小字段中放入什么，这意味着子数组 A[0...q-1]。据我所知，其余代码很好，因为当链接到生成随机数的驱动程序时，程序 returns 元素，尽管顺序不正确。我感谢任何 help/suggestions.

int Partition(float *,int);

int QuickSort(float *A,int n)
{
  int q;

  if(n>1){
    q = Partition(A,n);
    QuickSort(&A[],q); //Trying to figure out what to put in here.
    QuickSort(&A[q+1],(n-1)-q); //This recursion sends the subarray A[q+1...n-1] to QuickSort, I think it works fine.
  }
}

int Partition(float *A,int n){
  int i,j;
  float x;

  x = A[n-1];
  i=0;
  for(j=0;j<=n-2;j++){
    if(A[j] <= x){
      A[i]=A[j];
      i = i+1;
    }
  }
  A[i]=A[n-1];
  return i;
}

Answer 1

你唯一的问题是你似乎混淆了：

A[i]=something;

交换 A[i] 和 something。添加一个辅助tmp，或者写一个swap函数：

#include<stdio.h>
int Partition(float *,int);

void QuickSort(float *A,int n) {
  int q;

  if(n>1){
    q = Partition(A,n);
    QuickSort(A,q); //Trying to figure out what to put in here.
    QuickSort(A+q+1,(n-q-1)); //This recursion sends the subarray A[q+1...n-1] to QuickSort, I think it works fine.
  }
}

int Partition(float *A,int n){
  int i,j;
  float x;
  float tmp;
  x = A[n-1];
  i=0;
  for(j=0;j<=n-2;j++){
    if(A[j] <= x){
      tmp = A[i];
      A[i]=A[j];
      A[j]=tmp;
      i = i+1;
    }
  }
  tmp = A[i];
  A[i]=A[n-1];
  A[n-1]=tmp;
  return i;
}

int main() {
    float A[] = {3, 4, -5, 10, 21, -9, -1, 7, 8, 10};
    QuickSort(A,10);
    for(int i = 0; i < 10; i ++)
        printf("%f ",A[i]);
    return 0;
}

正确划分 QuickSort 数组

Properly Partitioning QuickSort Array

c

arrays

recursion

quicksort

sub-array