消息关闭
    暂无新消息!

java实现归并排序问题

问题作者 : 八点半2017-06-27发布
java实现归并排序出现了不完整排序,代码如下
import edu.princeton.cs.algs4.StdRandom;

public class Merge {
private static Comparable[] aux;

public static void sort(Comparable[] a)
{
aux = new Comparable[a.length];
sort(a, 0, a.length-1);
}

private static void sort(Comparable[] a, int lo, int hi)
{
if(hi <= lo) return;
int mid = (hi + lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);

}

private static void merge(Comparable[] a, int lo, int mid, int hi)
{
for(int k = lo; k <= hi; k++)
aux[k] = a[k];
System.out.printf("[  aux  ]:  ");
for(Comparable x : aux)
System.out.printf("%.3f ", x);
System.out.println();

int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++)
{
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(a[j], a[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
System.out.printf("[%d, %d, %d]:  ", lo, mid, hi);
for(double x : (Double [])a)
System.out.printf("%.3f ", x);
System.out.println();
}

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


public static void main(String[] args)
{
int N = 10;
Double[] a = new Double[N];
for(int i = 0; i < N; i++)
a[i] = StdRandom.random();
System.out.printf("[   a   ]:  ");
for(double x : a)
System.out.printf("%.3f ", x);
System.out.println();
Merge.sort(a);
System.out.printf("[   a   ]:  ");
for(double x : a)
System.out.printf("%.3f ", x);
}
}

追踪结果如下图:蓝标是第一次归并出错


1个回答