快速排序算法问题

Question

我的快速排序算法有问题。代码编译时没有任何错误，但当我尝试运行程序时，我得到的唯一输出是"The random numbers are：“，然后表现出它想要用户输入的样子，然后我不得不终止程序。现在，当我在主程序中删除对快速排序函数的调用时，程序会打印出数字，但不能使用对快速排序函数的调用。我不确定是我使用的参数有问题，还是函数本身有问题。

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <stack>
#include <queue>
using namespace std;

void quicksort(int arr[], int left, int right) {
  int l = left;
  int r = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  while (l <= r) {
    while (arr[l] < pivot)
      l++;
    while (arr[l] > pivot)
      r--;
    if (l <= r) {
      tmp = arr[l];
      arr[l] = arr[r];
      arr[r] = tmp;
      l++;
      r--;
    }
  }

  if (left < r)
    quicksort(arr, left, r);
  if (l < right)
    quicksort(arr, r, right);

}

int main() {
  int n = 20;
  int testlist[n];

 for (int i = 0; i<n; i++) {
   testlist[i] = rand()%100;
 }

 cout << "The random numbers are: " << endl;
 for (int i = 0; i < n; i++) cout << testlist[i] << " ";


 quicksort(testlist, 0, n - 1);

 cout << " " << endl;

 cout << "The sorted numbers are: " << endl;
 for (int i = 0; i < n; i++) {
   cout << testlist[i] << " ";
 }

 return 0;

}

Answer 1

您的quicksort函数中有一个无限循环。由于此函数从不返回，因此不会打印"The random numbers are:“行之后的任何内容，因为quicksort调用从不返回。(如果您在打印数字的std::endl循环之后向cout写入了一个for，则可能会打印这些数字。)

我怀疑这就是问题所在：

while (arr[l] > pivot)
    r--;

语句while (arr[l] > pivot)实际上应该是while (arr[r] > pivot)。

Answer 2

发生这种情况的原因是，在没有std::endl！std::endl！的情况下，quicksort()内部出现了问题，您打印出了数字

您可以看到，如果没有std::endl，数字将写入输出缓冲区，但不会刷新。他们最终会没有std::endl，但是你的代码不会到那个时候。

专业提示:在调试代码时，请始终使用std::endl ！

我不会调试你的quicksort()，因为你应该这样做，为了练习！如果您需要参考，您可以随时使用我的小示例：Quicksort (C++)，它是用c-like的方式编写的，这样c和c++的人就可以很容易地学习！:)

直觉:你使用了递归，你的程序没有terminate...Infinite循环可能是原因…;)

顺便说一句，如果我是你，没有任何重要的理由使用：

#if __INCLUDE_LEVEL__ < 1

我会丢弃它(以及附带的#endif)。