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

Question

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循环的判断语句中取出，为什么排序速度会慢了上百倍呀？

Answer 1

첫 번째 함수의 for 루프는 less() == true까지 실행되고 종료되며, 두 번째 함수는 종료되기 전에 j<h까지 루프에서 실행됩니다. 비교는 분명히 시간이 걸리며 작업으로 간주될 수 있습니다. 두 번째 함수는 less() == true 이후에 많은 쓸모없는 비교를 수행하며 복잡성은 직접적으로 O(n^2)로 저하됩니다.

Answer 2

속도 문제에 관계없이 글쓰기 방식은 동일하지 않습니다. 가장 안쪽 루프의 첫 번째 루프 실행 횟수는 두 번째 루프의 실행 횟수보다 작아야 합니다.