-1

我一直在尝试学习如何实现快速排序。我阅读了基本算法并尝试首先实现我自己的代码（基于我对算法的理解）。

为了简单起见，我将枢轴作为第一个元素。如果可以，请忽略它。我的代码运行但没有返回正确的结果，我无法弄清楚原因。任何帮助深表感谢。

public class QuickSortMain 
{
public static void displayArray(int[] arr)
{
    for(int i = 0; i < arr.length; i++)
        System.out.print(arr[i] + "  ");
}

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

private static void quickSort(int[] arr, int lo, int hi)
{
    if(lo >= hi) return;

    int j = lo;
    int left = lo;
    int right = hi;

    while(arr[left] <= arr[j])
        left++;

    while(arr[right] >= arr[j])
        right--;

    if (left >= right) return;

    swap(arr, left, right);
    swap(arr, j, left);

    quickSort(arr, lo, j-1);
    quickSort(arr, j+1, hi);
}

private static void swap(int[] arr, int i1, int i2)
{
    int temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
}

public static void main(String[] args)
{

    int[] myArray = {14, 79, 11, 42, 3, 27, 192, 44, 26, 742, 129};
    System.out.println(myArray.length);
    System.out.println("Original Array:");
    displayArray(myArray);

    quickSort(myArray);
    System.out.println("");
    System.out.println("Sorted Array:");
    displayArray(myArray);

}
}

这是我得到的输出： 11 原始数组：14 79 11 42 3 27 192 44 26 742 129
排序数组：3 14 11 42 79 27 192 44 26 742 129

谢谢！

4

1 回答 1

0

您需要确保所有小于枢轴的值都在一侧，而所有大于枢轴的值都在另一侧。您在分区方法中没有进行足够的交换。

为了解决这种情况，我建议您编写测试用例来突出显示算法不起作用的区域。使用调试器也有帮助。

private static void quickSort(int[] arr, int lo, int hi)
{
    if(lo >= hi) return;

    int j = lo;
    int left = lo;
    int right = hi;

    while (left < right){
        left++;
        while(arr[left] < arr[j] && (left < right))
            left++;

        while(arr[right] > arr[j] && (left < right))
            right--;

        if (left < right){
            swap(arr, left, right);
        }
    }

    if(arr[left] < arr[j]){
        swap(arr, j, left);
    }

    quickSort(arr, lo, left-1);
    quickSort(arr, left, hi);
}
于 2013-10-13T21:39:56.943 回答