0

我正在尝试实施快速排序，但我没有得到正确的结果。这是我的代码：

public static void quickSort(Comparable[] a, int start, int stop) {
    if (start < stop) {
        int pivot = partition(a, start ,stop);
        System.out.print("Pivot: "+a[pivot]+" Array: ");
        printArray(a);
        quickSort(a,start,pivot-1);
        quickSort(a,pivot+1, stop);
    }       
}

public static int partition(Comparable[] a, int start, int stop) {
    Comparable pivot = a[stop];
    int i = start;
    int j = stop-1;


     while (i < j) {
            while( (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
                i++;
            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
                j--;
            if(i < j)
                swap(a, i,j);
        } 

    swap(a,i, stop);

    return i;

}

输入：{51,17,82,10,97,6,23,45,6,73}，我得到结果：6 6 10 17 23 45 51 73 97 82 输入：{12,9,4, 99,120,1,3,10}，我得到一个索引越界错误。希望能在我出错的地方提供一些帮助。

4

3 回答 3

1

你的两个问题不相关。

问题{51,17,82,10,97,6,23,45,6,73}是——当 时会发生什么stop == start + 1？然后i == start == stop - 1 == j，所以你永远不会进入while-loop，所以你无条件地-swap(a, i, stop)即使a[i]已经小于。a[stop]

问题{12,9,4,99,120,1,3,10}似乎是您没有阅读堆栈跟踪。;-) 假设你有一个不错的 Java 编译器和 JVM，它应该给你确切的行号和有问题的索引，所以你会看到问题出在这一行：

            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

一旦j到达-1。（如果pivot是感兴趣范围内的最小值，就会发生这种情况。）您只需要为此添加一个检查：

            while(j > start && (isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

（并且，就此而言，对于相应的情况i：

            while(i < stop && (isLess(a[i], pivot)|| isEqual(a[i], pivot)))

)

. . . 你需要学习如何调试你的代码。:-)

于 2012-10-26T18:18:38.727 回答
0

我向你推荐算法：设计和分析，斯坦福非常好的网络课程。完成本课程后，您将更轻松地编写此类代码。这是一个有点增强的版本，枢轴被选为三的中位数。请注意，您不必编写自己的printArray()函数。在 Java 中，您可以使用System.out.println(Arrays.toString(numbers)). 您还可以观察如何quickSort()使用方法重载以更优雅的方式调用，只有一个参数。

public class QuickSort
{

public static void main(String[] args)
{
    int numbers[] =
    { 51, 17, 82, 10, 97, 6, 23, 45, 6, 73 };
    quickSort(numbers);
    System.out.println(Arrays.toString(numbers));
}

public static void quickSort(int[] array)
{
    quickSort(array, 0, array.length - 1);
}

private static void quickSort(int[] array, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pivot = choosePivot(array, left, right);
    pivot = partition(array, pivot, left, right);
    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
}

private static int partition(int[] array, int pivot, int left, int right)
{
    swap(array, pivot, left);
    pivot = left;
    int i = left + 1;
    for (int j = left + 1; j <= right; j++)
    {
        if (array[j] < array[pivot])
        {
            swap(array, j, i);
            i++;
        }
    }
    swap(array, pivot, i - 1);
    return i - 1;
}

private static void swap(int[] array, int j, int i)
{
    int temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

private static int choosePivot(int[] array, int left, int right)
{
    return medianOfThree(array, left, (left + right) / 2, right);
    // return right;
}

private static int medianOfThree(int[] array, int aIndex, int bIndex, int cIndex)
{
    int a = array[aIndex];
    int b = array[bIndex];
    int c = array[cIndex];
    int largeIndex, smallIndex;
    if (a > b)
    {
        largeIndex = aIndex;
        smallIndex = bIndex;
    }
    else
    {
        largeIndex = bIndex;
        smallIndex = aIndex;
    }
    if (c > array[largeIndex])
    {
        return largeIndex;
    }
    else
    {
        if (c < array[smallIndex])
        {
            return smallIndex;
        }
        else
        {
            return cIndex;
        }
    }
}

}
于 2012-10-26T18:18:48.040 回答
0

好吧，这是实现快速排序的代码，

public class QuickSort 
{
   int partition(int arrNum[], int low, int high)
   {
      int pivot = arrNum[high]; 
      int a = (low - 1); // smaller element index
      for(int b = low; b < high; b++)
      {
         // condition to check current element is smaller than or equal to pivot
         if(arrNum[b] <= pivot)
         {
            a++;
            // swapping arrNum[a] and arrNum[b]
            int temp = arrNum[a];
            arrNum[a] = arrNum[b];
            arrNum[b] = temp;
         }
      }

      // swapping arrNum[a + 1] and arrNum[high]
      int temp = arrNum[a + 1];
      arrNum[a + 1] = arrNum[high];
      arrNum[high] = temp;

      return a + 1;
   }

   void sortNumber(int arr[], int low, int high)
   {
      if(low < high)
      { 
         int part = partition(arr, low, high);
         // Recursive function sort elements before partition and after partition
         sortNumber(arr, low, part - 1);
         sortNumber(arr, part + 1, high);
      }
   }

   // printing utility function
   static void printingArray(int arr[])
   {
      int num = arr.length;
      for(int a = 0; a < num; ++a)
         System.out.print(arr[a] + " ");
      System.out.println();
   }

   public static void main(String[] args) 
   {
      int arr[] = {33, 36, 63, 34, 45, 78};
      int n = arr.length;

      QuickSort qs = new QuickSort();
      qs.sortNumber(arr, 0, n - 1);

      System.out.println("Quicksort sorted array : ");
      printingArray(arr);
   }
}
于 2018-03-29T11:44:39.837 回答