c++ - C++ 中的 QuickSelect 实现，无需额外的内存分配

Question

如果你不介意的话，我可以帮你做一些功课。基本上，我的想法是对一组值执行快速选择，但是我们得到了一个模板，但我似乎无法弄清楚如何让这些函数与提供的内容一起工作。

问题是这些值不会正确排列，或者如果它们排列正确，每次输入相同的值时它们都会改变。

这是我正在使用的函数，我将在代码之后用/**/表示我编写的代码，任何其他行都是为我提供的模板的一部分。

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int partition(int *A, int len, int pivot_index)
{
   int pivot_value = A[pivot_index]; /**/

   int left = 0; /**/
   int l = left; /**/
   int right = len - 1; /**/
   while(left < right)  /**/
   { /**/
      while(A[left] < pivot_value) /**/
      { /**/
         left++; /**/
      } /**/

      while(A[right] > pivot_value) /**/
      { /**/
         right--; /**/
      } /**/

      if(A[left] < pivot_value) /**/
      { /**/
         swap(A[left], A[right]); /**/
      } /**/
  } /**/

  return left; /**/
}


int select (int *A, int len, int rank)
{
      if (len==1) return A[0];
      int pivot_index = rand() % len;
      int pivot_rank = partition(A, len, pivot_index);  

      if (rank == pivot_rank) return A[rank];
      if (rank < pivot_rank) return select(A, pivot_rank, rank);
      return select(A, len - pivot_rank, rank - pivot_rank ); /**/
}

int main(void)
{
   int N, *A;

   ifstream fin("test.txt");
   fin >> N;
   A = new int[N];
   for (int i=0; i<N; i++) fin >> A[i];
   fin.close();

   int r;
   cout << "Enter rank (0.." << N-1 << ")\n";
   while (cin >> r) {
      if (r < 0 || r >= N)
        cout << "Invalid rank\n";
     else 
        cout << "The element of rank " << r << " is " << select(A,N,r) << "\n";
   }

  delete[] A;
}

我的“test.txt”文件包含以下值:

10 -- this denotes the length of the array or how many values it will read in
7
14
12
2
25
18
15
13
100
63

如有任何帮助，我们将不胜感激。我的教授根本没有解释这是如何工作的，我在网上找到的任何其他例子也没有回答我的问题。我花了很多时间摆弄不同的方式来实现这个，在这一点上我只是不知道。谢谢

编辑:更改为现在可以直接实现和编译。还添加了我正在使用的库

Answer 1

您的代码有很多问题。

while(A[left] < pivot_value) {  left++; }

这不会检查左边是否超出数组的末尾。

while(A[right] > pivot_value) { right--;} 

这不会检查是否在数组开始之前不运行。

while(left < right) 

这是一个无限循环，当

1. 左<右
2. A[left] >= pivot_value
3. A[右] <= pivot_value

select(A, len - pivot_rank, rank - pivot_rank );

这不是要继续的正确分区。