时间戳

首页 > 解决方案 > 有人可以向我解释这种 3-way-quicksort 的实现吗

java - 有人可以向我解释这种 3-way-quicksort 的实现吗

问题描述

试图理解这段代码我有点迷失，在第一次迭代之后，再次调用排序函数，几次，传递给“排序”的值正在改变：

sort(a, lo, lt - 1, c);
sort(a, gt + 1, hi, c);

我不明白为什么，修改这些索引意味着什么以及它如何影响排序。我尝试调试这段代码，在我看来，这些索引更改将区域限制为排序到数组的右侧或左侧，在第一次迭代之后，大多数较大和较小的值应该是. 任何人都可以对此有所了解并阐明这两行代码的目的吗？

public class Quick3Way{

    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);
        System.out.println(Arrays.toString(a));
        sort(a, 0, a.length - 1);
    }

    public static void sort(Object[] a, Comparator c)
    {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1, c);
    }


    public static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;

        // partition
        int i = lo;
        int lt = lo;
        int gt = hi;

        while (i <= gt){
            if      (less(a[i], a[lt]))     exch(a, i++, lt++);

            else if (less(a[lt], a[i]))     exch(a, i, gt--);
            else                            i++;
        }

        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    public static void sort(Object[] a, int lo, int hi, Comparator c)
    {
        if (hi <= lo) return;

        // partition
        int i = lo;
        int lt = lo;
        int gt = hi;

        while (i <= gt){
            if (less(a[i], a[lt], c))       exch(a, i++, lt++);
            else if (less(a[lt], a[i], c))  exch(a, i, gt--);
            else                            i++;
        }

        sort(a, lo, lt - 1, c);
        sort(a, gt + 1, hi, c);
    }


    // test client
    public static void main(String[] args)
    {
        Integer[] arraypart = { 1,1,2,2,3,4,5,6,710,30,0,50};
        Integer[] arraysort = new Integer[arraypart.length];
        System.arraycopy(arraypart, 0, arraysort, 0, arraypart.length);

        System.out.print("Original:\t");
        for (int str : arraypart)
            System.out.print(str);
        System.out.println();

        System.out.print("Full sort:\t");
        Quick3Way.sort(arraysort);
        for (int str : arraysort)
            System.out.print(str);
        System.out.println();
    }

    // private
    private static void exch(Comparable[] a, int i, int j)
    {
        System.out.println(Arrays.toString(a));
        Comparable tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        System.out.println(Arrays.toString(a));
    }

    private static void exch(Object[] a, int i, int j)
    {
        Object tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    private static boolean less(Comparable a, Comparable b)
    { return a.compareTo(b) < 0; }

    private static boolean less(Object a, Object b, Comparator c)
    { return c.compare(a, b) < 0; }
}

标签： javasortingquicksort

解决方案

首先，我不相信这段代码是 3 路快速排序，我认为它只是普通的快速排序，尽管如果有更多经验的人可以检查代码并验证这一点会很好。但是对于这两行，希望以下内容会有所帮助：

所以你选择了一个枢轴元素。我们称它为 x

然后你做两个分区。因此，列表现在包含小于 x 的所有内容（不一定已排序）后跟 x 后跟所有大于 x 的内容（不一定已排序）。

所以你肯定知道 x 在正确的位置。现在您需要对 x 两侧的部分进行排序。这就是这段代码的用武之地：

sort(a, lo, lt - 1, c);
sort(a, gt + 1, hi, c);

大致翻译为：

排序（the_list，from_start，to_one_before_x，with_this_comparitor）；

排序（the_list，from_one_after_x，to_end，with_this_comparitor）；

显然，随着算法的递归，您可以将 from_start 替换为 from_start_of_partition 并将 from_end 替换为 from_end_of_parition 等。

推荐阅读