c++ - 递归获取数组中第k小的元素

Question

我正试图从教科书中提供的伪代码中“翻译”这个算法。虽然我的程序一直在崩溃，但我不确定我的实现哪里出了问题。这是图像中的伪代码，我的代码就在它下面:

int kSmallFirst (int k, int anArray[], int first, int last) {
    int pivotIndex = 0;

    if (k < pivotIndex - first + 1)
        return kSmallFirst(k, anArray, first, pivotIndex - 1);
    else if (k == pivotIndex - first + 1)
        return pivotIndex;
    else
        return kSmallFirst(k - (pivotIndex - first + 1), anArray, pivotIndex + 1, last);
}

int main () {
    int i = 0;
    int arr[512];
    fstream data;
    data.open("data.txt");

    while (!data.eof()) {
        data >> arr[i];
        i++;
    }

    data.close();

    cout << kSmallFirst(42, arr, 0, i-1);

    return 0;
}

非常感谢!

Answer 1

问题是:您没有实现算法的主要部分，这在您的书中用斜体字体描述:

Choose a pivot value 'p' form 'anArray[first..last]'

Partition the values of 'anArray[first..last]' about 'p'

这两行不是注释!它们是您要转换为 C/C++ 的伪代码，以使您的代码执行您希望它执行的操作。