谁能给我解释一下这个实现3路,快速排序

问题描述 投票:0回答:1

我有点失去了试图理解这个代码,第一之后,而迭代排序函数被再次调用,好几次,并通过了值“排序”正在发生变化:

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

我不明白为什么,是什么修改这些指标的意思,它是如何影响排序。我试着调试这一段代码,它看起来对我来说,这些指数的变化是制约该地区排序,对阵列的右侧或左侧的一个,在第一次迭代后,大部分的较大和较小的值应该是。任何人可以阐明它的一些光以及澄清这些2行代码的目的是什么?

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; }
}
java sorting quicksort
1个回答
0
投票

首先,我不相信这个代码是快速排序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_of_partition和from_end与from_end_of_parition等替代FROM_START

© www.soinside.com 2019 - 2024. All rights reserved.