algorithm - 快速选择不适用于所有索引

Question

我正在尝试参考以下链接 http://www.cs.yale.edu/homes/aspnes/pinewiki/QuickSelect.html中给出的算法来实现快速选择

但是程序会因许多 k 值而崩溃，并且仅在少数情况下可以正常工作。请指导我哪里做错了。

#include <stdio.h>
#include <stdlib.h>

int a1[10];
int a2[10];

int quickselect(int a[], int k,int len){
        int r = rand()%(len-1);

        int pivot = a[r];
        int i =0;
        int len1=0,len2=0;
        for(i=0 ;i<len;i++){
        if(a[i]<pivot)
            a1[len1++]=a[i];
        else if(a[i]>pivot)
            a2[len2++] = a[i];
        else
            continue;
    }

    if(k<=len1)
        return quickselect(a1, k,len1);
    else if (k > len-len2)
        return quickselect(a2, k - (len-len2),len2);

    return pivot;

}
int main()
{
  int a[7] = {8,3,2,6,1,9,5};
  int val = quickselect(a,3,7);
  printf("%d \n",val);

  return 0;
}

Answer 1

我已经测试了你的代码。我认为您应该更改int r = rand()%(len-1)为，int r = rand()%len因为何时len==1会出现浮点异常。