首页 >社区问答列表 >java - 希尔排序一个语句使速率慢了上百倍

java - 希尔排序一个语句使速率慢了上百倍

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

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

public static void sort(Comparable[] a) {
    int n = a.length;
    int h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                exch(a, j, j - h);
            }
        }
        h /= 3;
    }
}
public static void sort(Comparable[] a) {
    int n = a.length;
    int h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h ; j -= h) {
                if (less(a[j], a[j - h])) {
                    exch(a, j, j - h);
                }
            }
        }
        h /= 3;
    }
}

第二个sort方法只是把 if 语句从for循环的判断语句中取出,为什么排序速度会慢了上百倍呀?

  • 迷茫
  • 迷茫    2017-04-17 17:33:122楼

    第一个函数里面的for循环运行到less() == true就退出了,第二个会一直循环运行到j<h才退出。比较显然也是要花时间的,可以当作一种运算。第二个函数在less() == true之后做了很多次无用的比较,复杂度直接退化到O(n^2)了。

    +0添加回复

  • 回复
  • 伊谢尔伦
  • 伊谢尔伦    2017-04-17 17:33:121楼

    先不管速度的问题,你这样的写法不等价啊。最内层的循环第一个执行的次数要<=第二个执行的次数。

    +0添加回复

  • 回复