c++中的快速选择实现，无需额外的内存分配

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 rankn";
     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. 左& lt;对
2. A[left]>= pivot_value
3. A[right] <= pivot_value

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