快速选择算法

Question

当我运行以下快速选择代码时

#include <cstdlib>
#include <iostream>

using namespace std;
const int n = 15;
int b[100];
int btotal=0;
int c[100];
int ctotal=0;

void read(int a[],int size){
    for (int i=1; i<=15; i++) cin >> a[i];
}

int quickselect(int a[], int k)
{
    int r = 1 + rand()%(n-1);
    int pivot = a[r];
    for (int i=1; i<=n; i++) {
        if (a[i] < pivot) {
            b[i] = a[i];
            ++btotal;
        }

        if (a[i] > pivot) {
            c[i] = a[i];
            ++ctotal;
        }  
    }

    if (k <= btotal) quickselect(b,k);
    if (k > (n-ctotal)) return quickselect(c, k - (n-ctotal));        

    return pivot;          
}

int main(int argc, char *argv[])
{
    int a[n];
    cout <<" enter contents of array " << endl;
    read(a, n);
    quickselect(a, 6);
    //system("PAUSE");
    //return EXIT_SUCCESS;
    return 0;
}

1 4 2 3 5 7 6 9 8 10 13 12 11 15 14

我有运行时错误，我认为这是与索引有关的问题，但找不到哪里，请帮助我

Answer 1

您是在数组a的边界之外编写的。

int a[15]将为15个整数分配空间，索引范围从a[0]到a[14]。您当前正在读/写以将[1]偏移到(并包括) [15]，这是错误的。

所需的最小更改

void
read (int a[],int size)
{
  for (int i=0; i < 15; i++) // CHANGE TO
    ...
}

...

int
quickselect(int a[],int  k)
{
  ...

  for (int i=0; i < n; i++) { // CHANGE TO

  ...
}