c - C 语言的快速排序算法

Question

我正在尝试为快速排序算法编写递归程序。到目前为止，这是我的代码:

void QuickSort(int *array, int first, int last){
  int q;
  if (first<last){
    q = partition(array,first,last);
    QuickSort(array,first,q-1);
    QuickSort(array,q+1,last);
  }
}

void partition(int *A, int p, int r){
  int value = A[r];
  i = p-1;
  int tmp;
  for (j = p; j<=r; j++){
    if (A[j] <= value) {
      i++;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
return(i);
}

int main(){                                                                            
  int numArray[8] = {30,15,11,40,75,80,70,60};
  int i;

  printf("Before sorting: \n");
  for (i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);

  int first = 0;
  int last = sizeof(numArray)/sizeof(numArray[0]);
  QuickSort(numArray,first,last-1);

  printf("After sorting: \n");
  for (i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);
}

我的问题是，当我运行这个程序时，当我到达第一个递归调用(就在分区之后)时，我陷入了无限循环。另外，我注意到递归调用是在 A[0] - A[5] 的数组值上运行的，即使它应该在 A[0]-A[3] 上运行。我并不期望得到完整的答案，但也许暗示程序为何陷入无限状态将非常有帮助。

Answer 1

这就是我对你的大纲所做的，它似乎工作和排序都很好。 我用 int 替换了 void，并根据需要声明了 int

#include<iostream>
using namespace std;


int partition(int *A, int p, int r){
    int value = A[r];
    int i = p-1;
    int tmp;
    for (int j = p; j<=r; j++){
        if (A[j] <= value) {
        i++;
        tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
        }
   }
return(i);
}
void QuickSort(int *array, int first, int last){
    int q;
    if (first<last){
        q = partition(array,first,last);
        QuickSort(array,first,q-1);
        QuickSort(array,q+1,last);
    }
}



int main(){
    int numArray[8] = {30,15,11,40,75,80,70,60};

    printf("Before sorting: \n");
    for (int i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);

    int first = 0;
    int last = sizeof(numArray)/sizeof(numArray[0]);
    QuickSort(numArray,first,last-1);

    printf("After sorting: \n");
    for (int i = 0; i<8; i++) printf("numArray[%d] = %d\n", i, numArray[i]);
}