-2

好吧，我知道这是一个奇怪的问题，但我发现这个快速排序算法的 java 代码：

private static void quickSort (ArrayList <String> list, int first, int last){

        int g = first; 
        int h = last;

        int midIndex = (first + last) / 2;
        String dividingValue = list.get(midIndex);

        do{
            while (list.get(g).compareTo(dividingValue) < 0) g++;
            while (list.get(h).compareTo(dividingValue) > 0) h--;
            if (g <= h)
            {
                swap(list,g,h);
                g++;
                h--;
            }
        }

        while (g < h);

        if (h > first) quickSort (list,first,h);
        if (g < last) quickSort (list,g,last);      
    }

    private static void swap (ArrayList <String> list, int first, int h)
    {
        String temp = list.get(first);
        list.set(first, list.get(h));
        list.set(h, temp);
    }

我工作，但这对我来说真的没有意义。有人能以某种方式给我解释这段代码吗？或者如果可能的话，为快速排序提供更简单的代码？

4

1 回答 1

3

我假设您知道快速排序是如何工作的，并且只是想知道这个特定的实现。我还假设代码是正确的。我们首先定义我们正在处理的范围并选择一个支点。

private static void quickSort (ArrayList <String> list, int first, int last) {

    int g = first; 
    int h = last;

    int midIndex = (first + last) / 2;
    String dividingValue = list.get(midIndex);

然后我们从范围的两端开始向内工作。我们希望枢轴左侧的所有内容都更小，而右侧的所有内容都更大。因此，我们跳过任何已经满足这一点的元素。

    do {
        while (list.get(g).compareTo(dividingValue) < 0) g++;
        while (list.get(h).compareTo(dividingValue) > 0) h--;

当我们遇到两个都违反属性的元素时，我们交换它们，使它们位于正确的一侧，然后向内移动。if (g <= h)检查是必要的，因为我们在交换之后盲目地应用（g++而不是像在循环h--中检查值）。while似乎它交换了枢轴以处理没有要交换的相反元素。这肯定需要测试以确保正确性。

        if (g <= h)
        {
            swap(list, g, h);
            g++;
            h--;
        }

我们继续这样做，直到我们到达枢轴（因为可以交换枢轴，所以有点隐含）。

    } while (g < h);

我们递归地将此属性应用于列表的子部分，以便对整个列表进行排序。

    if (h > first) 
        quickSort(list, first, h);
    if (g < last) 
        quickSort(list, g, last);      
}

private static void swap (ArrayList <String> list, int first, int h)
{
    String temp = list.get(first);
    list.set(first, list.get(h));
    list.set(h, temp);
}
于 2013-06-15T19:53:16.490 回答