快速选择算法

Question

我正在尝试在随机生成数字的数组上实现快速选择算法。现在对算法进行编码后，它不会从低到高对数组进行排序，也无法找到第 k个最小的元素。

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int Partition(int *myArray, int startingIndex, int endingIndex){
    int pivot = myArray[endingIndex];
    int partitionIndex = startingIndex;
    for(int i = startingIndex; i<endingIndex; i++){
        if(myArray[i]<= pivot){
            swap(myArray[i],myArray[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(myArray[partitionIndex],myArray[endingIndex]);
    return partitionIndex;
} 
 
int QuickSelect(int *myArray, int startingIndex, int endingIndex, int KthElement){
    if (startingIndex < endingIndex){
        int partitionIndex = Partition(myArray, startingIndex, endingIndex);
        if(KthElement == partitionIndex)
            return KthElement;
        if(KthElement < partitionIndex)
            QuickSelect(myArray, startingIndex, partitionIndex - 1, KthElement);
        else
            QuickSelect(myArray, partitionIndex + 1, endingIndex, KthElement);
    }
}
    /*if(startingIndex < endingIndex){
        int partitionIndex = Partition(myArray, startingIndex,endingIndex);
        QuickSelect(myArray,startingIndex,partitionIndex-1);
        QuickSelect(myArray,partitionIndex+1,endingIndex);
    }// 1 */
void printArray(string intro, int const *myArray, int n, ostream &out) {
    out << intro;
    for(int i = 0; i < n; i++){
        out << " " << myArray[i];
    }
    out << endl;
}
int main(){
    int numOfElements;
    int KthElement;
    srand(time(NULL));
    cout<<"Enter The Amount Of Numbers You Wish To Use: ";
    cin >> numOfElements;
    int myArray[numOfElements];
    for(int i = 0; i< numOfElements; i++){
        myArray[i] = rand() %10;
    }
    printArray("Array Before Sorting:", myArray, numOfElements, cout);
    cout <<"nEnter The Rank K Of The Element You Wish To Retrieve: ";
    cin >> KthElement;
    QuickSelect(myArray,0,numOfElements,KthElement);
    printArray("Array After Sorting:", myArray, numOfElements, cout);
    cout << "The " << KthElement << " Smallest Element Is: "
         << QuickSelect(myArray,0,numOfElements,KthElement);
}

Answer 1

对于 5 numOfElements，数组从 0 扩展到 4。您的endingIndex假定它是数组的最后一个索引。

修复：

QuickSelect(myArray, 0,numOfElements-1,KthElement);

代码问题：

• 您的程序访问 中的越界数组位置

  int pivot = myArray[endingIndex];
  

• 检查k<1和k>(num_of_elements)。

• 还要检查您的代码是否为 num_of_elements = 1。

• 检查 k 对数组意味着什么，即对于 k=1 ，arr[0] 应该返回而不是 arr[1] ;

Answer 2

你的int QuickSelect()有问题 ：
• 未记录 - 它返回什么，为什么KthElement而不是k ？
• 并不总是返回值
• 如果它返回一个值，它始终是其最后一个参数的未修改值