使用快速排序分区的中值中值规则出现越界错误

Question

我正在使用 中值中位数 算法来选择第 k 个元素href="https://rads.stackoverflow.com/amzn/click/com/0763782505" rel="nofollow noreferrer">算法基础，我在用java实现它时遇到了麻烦。我收到数组越界错误，想知道是否有人可以帮助我正确实现该算法。

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at test2.selection2(test2.java:23)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.main(test2.java:11)

这些是变量的值：

N size = 10
low = 0
high = 10
k = 3
arraysize = 10
r = 2
i = 1,2,3
first = 0,5,10
last = 4,9,11
lower = 7, 33
upper = 10, 44

-pivotitem
T size = 2
low = 0
high = 2
k = 1
arraysize = 10
r = 0

high==low [0]
list is empty

由于我的数组从大小 10 开始，因此 r 将为 2。当从ivotitem 再次调用partition2 时，r 将为 0，从而生成大小为 0 的数组 T。然后 low 和 high 将等于 0 ，什么也不返回，这就是我收到错误的地方。我不知道为什么会发生这种情况，因为我的代码与书中的算法类似。

Answer 1

您的交换方法看起来好像它以索引作为参数，但您向它提供了值

list = swap (list[i], list[j], list);

这不是错误的根源，并且在更改调用后错误仍然存​​在，但也许您多次出错。顺便说一句：代码去哪里了？

Answer 2

原来是C-Code？使用 & 调用partition2

index& pivotpoint)

这意味着，一个引用，即改变的结果被调用者看到。

您似乎使用静态“thepivotpoint”来解决这个问题，但是您不能将其用作参数；它只会隐藏静态成员。

public static void partition2 (int[] list, int low, int high) // , int pivotpoint)
/* unchanged */
    thepivotpoint = j - 1;
    list = swap (mark, thepivotpoint, list);
}

它还没有完成。

Answer 3

我还有一些其他改进，没有解决方案，但也许是进一步发展的更好基础：

• 并非所有变量都在方法的开头声明（帕斯卡风格）以减少它们的范围。这使得推理代码变得更加容易。
• 我稍微统一了参数顺序 (int[], int, ...)
• 从 if ... return else ... 中删除了 else。
• 将partition2分成2个方法。
• 添加了一种调试 show 的方法，该方法会触发计数器，以停止无限循环。

• 删除了对我没有帮助的评论。也许您可以添加更好的评论。

  导入java.util.Arrays;
  
  公开课枢轴
  {
      静态 int 枢轴点；
  
      公共静态无效主（字符串[]参数）
      {
          int[] 列表 = {17, 10, 44, 7, 7, 33, 24, 10, 48, 49 };
          枢轴点 = 0；
          System.out.println(select4(list,list.length,3));
      }
  
      公共静态 int select4 (int[] list, int high, int k)
      {
          返回选择2（列表，0，高，k）；
          // 返回选择2（列表，1，高，k）；
      }
  
      public static int Selection2 (int[] list, int low, int high, int k)
      {
          如果（高 == 低）
              返回列表[低]；
          分区2（列表，低，高）；
          if (k == 枢轴点)
              返回列表[枢轴点]；
          if (k < 枢轴点)
              return Selection2 (list, low, thepivotpoint - 1, k);
          return Selection2 (列表, 枢轴点 + 1, 高, k);
      }
  
      静态整数计数 = 0；
      公共静态无效显示（int [] T）
      {
          对于 (int i : T)
              System.out.print(i + "\t");    
          System.out.println();  
          if (++count > 20) System.exit (1);
      }
  
      公共静态无效分区2（int []列表，int低，int高） 
      {
          int 数组大小 = 高 - 低；
          int r = (int) Math.ceil (数组大小 / 5);
          int[] T = new int[r+1];
          for (int i = 1; i <= r; i++)
          {
              int 第一个 = 低 + 5 * i - 5；
              int last = Math.min(low + 5 * i - 1, 数组大小);
              T[i]=中位数（列表，第一个，最后一个）；
          }
          显示（列表）；
          approxTheMedian (T, r, 低, 高, 列表);
      }
  
      公共静态无效近似中位数（int [] T，int r，int low，int high，int []列表） 
      {
          int hubitem = select4(T, r, (r + 1) / 2); 
          int j = 低；
          整数标记=0；
          for (int i = low; i < high; i++)
          {
              if (列表[i] == 枢轴项)
              {
                  列表=交换（i，j，列表）；
                  标记=j； //标记枢轴项放置的位置
                  j++；
              }
              else if (列表[i] < 枢轴项)
              {
                  列表=交换（i，j，列表）；
                  j++；
              }
          }
          枢轴点 = j - 1；
          列表=交换（标记，枢轴点，列表）；
      }
  
      公共静态 int 中位数（int[] 列表、int 开始、int 结束）
      {
          int[]copy = (int[])list.clone();
          Arrays.sort（复制）；
          返回副本[(开始+结束)/2]；
      }
  
      公共静态 int[] 交换（int 1、int 2、int[] 列表）
      {
          int 虚拟 = 列表[一];
          列表[一] = 列表[二];
          列表[二] = 虚拟；
          返回列表；
      }
  }