计算 shell 排序中的比较次数

Question

使用这段代码，我必须计算进行元素比较的次数。话虽如此，我不确定比较是在 sort() 方法的 for 循环内还是在 less() 方法内完成的。非常感谢您的帮助。

    public class Shell {
private static int compares;
// This class should not be instantiated.
private Shell() { }

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 */
public static void sort(Comparable[] a) {
    int n = a.length;

    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < n/3) h = 3*h + 1; 

    while (h >= 1) {
        // h-sort the array
        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);
            }
        }
        assert isHsorted(a, h); 
        h /= 3;
    }
    assert isSorted(a);
}

/******************************************** ********************************** * 辅助排序功能。 ****************************************************** ****************************/

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

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

/******************************************** ********************************** * 检查数组是否排序 - 对调试有用。 ****************************************************** ***************************/

    private static boolean isSorted(Comparable[] a) {
      for (int i = 1; i < a.length; i++)
        if (less(a[i], a[i-1])) return false;
      return true;
}

// is the array h-sorted?
private static boolean isHsorted(Comparable[] a, int h) {
    for (int i = h; i < a.length; i++)
        if (less(a[i], a[i-h])){
            return false;
        }
    return true;

}

// print array to standard output
      private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
          StdOut.println(a[i]);
    }
}

/**
 * Reads in a sequence of strings from standard input; Shellsorts them; 
 * and prints them to standard output in ascending order. 
 *
 * @param args the command-line arguments
 */
public static void main(String[] args) {
    String[] a = StdIn.readAllStrings();
    Shell.sort(a);
    show(a);
}

}

Answer 1

鉴于您的代码看起来像经典学生的练习，可能要求您仅计算 less 函数在 sort 函数内部调用时进行的元素比较的次数.如果我错了，请更新您的问题，添加更完整的目标描述。

如您所见，每次调用 less 函数时都会进行比较。但是在您的代码中 less 甚至是通常用于比较两个对象的方法。因此，您应该仅在 sort 方法中直接调用 less 函数时进行计数。其他情况 isSorted 和 isHsorted 存在只是因为断言。

需要说明的是，断言是 Java 编程语言中的一种语句，可让您测试有关程序的假设。

记住，这是你的练习，所以你不应该四处寻找简单的答案，我也不会写任何详细的代码解决方案。

但我可以给你另一个建议，你可以尝试创建一个新方法 lessWithCounter 来代表 less 在 sort 方法中调用。

计算 shell 排序中的比较次数

Counting number of comparisons in shell sort

java

sorting

shellsort