我不确定我的分区功能有什么问题

Question

Eclipse一直告诉我分区功能有问题。它在java中，是类的一部分，全部是关于排序数组的。

分区的工作原理如下：数组中有两个下标i和j，分区算法的最开始处i指向数组中的第一个元素，j指向最后一个元素。然后，算法向前移动i，直到找到值大于或等于主键的元素。索引j向后移动，直到找到值小于或等于主键的元素。如果i≤j，那么它们被交换，并且我跳到下一个位置（i + 1），j跳到前一个（j - 1）。当我变得比j更大时，算法停止。

您能否看到问题所在，因为我无法找到它。非常感谢帮助。

public static int partition(int arr[], int left, int right) 
    { 
     int x = arr[right]; 

     int i = left-1; 
     int temp=0; 

     for (int j=left; j<right; j++) 
     { 
      if(arr[j]<=x) 
      { 
       i++; 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 

      } 
     } 

     temp = arr[i+1]; 
     arr[i+1] = arr[right]; 
     arr[right] = temp; 
     return (i+1); 

    } 

编辑

Eclipse是说，有两个问题，一个与这行代码中的分区功能：

int x = arr[right]; 

而与此行我的测试类：

sort.partition(array, 100, array.length); 

这里是测试类，其中包括我没有提到的功能。

import java.util.Random; 


public class test { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

     int size = 1000; 
     int max = 5000; 
     int[] array = new int[size]; 
     int loop = 0; 

     Random generator = new Random(); 
     //Write a loop that generates 1000 integers and 
     //store them in the array using generator.nextInt(max) 

     generator.nextInt(max); //generating one 

     //I need to generate 1000 
     //So I need some kind of loop that will generate 1000 numbers. 

     for (int i =0; i<1000; i++) 
     { 
      generator.nextInt(max); 
     } 



     /** 
     * After I do this, I'll have the array, array. 
     * Then comes what's under this. 
     * THat method is for measuring the time. 
     * System.currentTimeMillis();, 
     * with this, I can collect a time for the start of the method 
     * and one for the end. 
     * Time at the end, minus the time at the start 
     * gets us the running time. 
     */ 



     long result; 

     long startTime = System.currentTimeMillis(); 
     sort.quickSort(array, 100, array.length-1); 
     long endTime = System.currentTimeMillis(); 
     result = endTime-startTime; 

     System.out.println("The quick sort runtime is " + result + " miliseconds"); 

     long result2; 

     long startTime2 = System.currentTimeMillis(); 
     sort.partition(array, 100, array.length); 
     long endTime2 = System.currentTimeMillis(); 
     result2 = endTime2 - startTime2; 
     System.out.println("The partition runtime is "+result2 + " miliseconds"); 

     long result3; 

     long startTime3 = System.currentTimeMillis(); 
     sort.bubbleSort(array, 100); 
     long endTime3 = System.currentTimeMillis(); 
     result3 = endTime3-startTime3; 
     System.out.println("The bubble sort runtime is "+result3 + " miliseconds"); 

     long result4; 

     long startTime4 = System.currentTimeMillis(); 
     sort.selectionSort(array, 100); //change the second number to change 
     //the size of an array. 
     long endTime4 = System.currentTimeMillis(); 
     result4 = endTime4-startTime4; 
     System.out.println("The selection sort runtime is "+result4 + " miliseconds"); 



    } 

} 

Answer 1

首先，你实际上并没有在数组中存储随机数，所以它将全部为零。

至于你看到的实际错误，你有一个经典的错误。您有两个选择：使right指向数组的末尾或者指向数组末尾的指针。任何一个都是有效的，但是你正在混合这两个。

具体而言，您传递的是1000，一个超过数组的末尾，为right值，但是您立即用它索引数组，然后自然抛出一个异常。