我有点失去了试图理解这个代码,第一之后,而迭代排序函数被再次调用,好几次,并通过了值“排序”正在发生变化:
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; }
}
首先,我不相信这个代码是快速排序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