algorithm - 从数组 a[0..n-1] 中选择第 k 个最小值

<分区>

我已经完成了以下来自编程珍珠的代码，这里是代码

import java.util.*;
public class select {
public static int select1(int x[],int l,int u,int k){
    //pre l<=k<=u
    //post x[l..k-1]<=x[k]<=x[k+1..u]
    Random r=new Random();
   int  t=r.nextInt(u-1-l)+l;
     if (l>=u) return -1 ;
    swap(l,t);
    int s=x[l];
    int i=l;
     int j=u+1;
       while (true){
         do
         {
              i++;
         }while (i<=u && x[i]<t);
         do
         {
              j--;
         }while (x[j]>t);
          if (i>j)  break;
           int temp=x[i]; x[i]=x[j];x[j]=t;
            swap(l,j);

             if (j<k){
               return   select1(x,j+1,u,k);

         }
       }
            return    select1(x,l,j-1,k);
           }

    public static void main(String[] args) {
        int x[]=new int[]{4,7,9,3,2,12,13,10,20};
                  select1(x,0,x.length-1,5);

    }


    public static void swap(int i,int j){
        int c=i;
        i=j;
        j=c;

    }
}

但是这里是错误的

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at select.select1(select.java:21)
        at select.main(select.java:36)
Java Result: 1

最佳答案

用手工做...一步一步...写在一张纸上。使用铅笔和计算器。您会发现错误，并且您可能会学到一些东西……也许吧。

[警告:故事即将到来]

让我告诉你一个关于一个男人的小故事，他是家里第一个上大学的......

我父亲是 1960 年代中期的一名年轻工程师。他为 NASA 的 Apollo 计划工作。特别是作为 Lunar Accent 火箭发动机的专家。他编写了模拟电机性能超过预期燃烧的软件。然后可以针对飞行硬件对正常和异常事件进行建模和验证。他用 Fortran 编写了代码……将其发送到满是非常漂亮的女士的房间，这些女士会为他生成穿孔卡片堆。然后，该堆栈将被丢弃在柜台并安排运行。结果出现在约 200 页的 11 x 17 拖拉机进纸纸上。

有了这些结果，我父亲就会退休到作业打印机周围的一间小工作室。然后他会手动测试结果，手动验证每个步骤的代码。他有一个黄色的垫子、一桶铅笔和一个计算尺。如果它没有验证它会更正并一次又一次地运行......直到它是正确的。

那些马达每次都工作，每个人都回家了。

好的..故事结束......现在:

长大了，忍气吞声，做一些工作。别再浪费我们的时间了。

关于algorithm - 从数组 a[0..n-1] 中选择第 k 个最小值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2979970/