算法4习题 2.1.12
算法4习题 2.1.12 问题 Instrument shellsort to print the number of compares divided by the array size for each increment. Write a test client that tests the hypothesis that this number is a small constant, by sorting arrays of random Double values, using array sizes that are increasing powers of 10, starting at 100.
打印希尔排序中每个增量带来的比较次数和数组大小的比值。 验证该值是一个小常数。
思路 统计每个增量对应的比较次数。
private static boolean less(Comparable v, Comparable w) { count ++ ; return v.compareTo(w) < 0; } 解答 Extensive experiments suggest that the average number of compares per increment might be N^(1/5) 大量实验表明每个增量的比较次数约为N的1/5次方。