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

private static boolean lessComparable v, Comparable w { return v.compareTow < 0;
} private static void exchComparable[] a, int i, int j { Comparable t = a[i]; a[i] = a[j]; a[j] = t;
} public static void sortComparable[] 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 && lessa[j], a[j - h]; j -= h { excha, j, j - h; } } h /= 3; }
}
public static void sortComparable[] 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 lessa[j], a[j - h] { excha, j, j - h; } } } h /= 3; }
}

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

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注