java - 霍尔分区分析

Question

我的任务是绘制图表并分析 Hoare 的分区算法并比较理论和实际最坏情况的值。它说我需要一个计数变量来跟踪关键步骤（即比较和交换）。我为 Hoare 的分区编写了这段代码。

public static int partition(Comparable[] a, int left, int right) {
        Comparable pivot = a[(left + right) / 2];
        int i = left - 1, j = right + 1;
        while (true) {
            do {
                i++;
            } while (a[i].compareTo(pivot) < 0);

            do {
                j--;
            } while (a[j].compareTo(pivot) > 0);

            if (i < j) {
                Comparable temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            } else {
                return j;
            }
        }
}

现在我对在哪里添加 count 变量感到困惑。我知道 count 变量将在 if (i < j) 行中递增。但是我是否还需要在两个 do-while 循环中增加计数以跟踪比较？

那么，更新后的代码会是这样吗？

public static int partition(Comparable[] a, int left, int right) {
        int count = 0;
        Comparable pivot = a[(left + right) / 2];
        int i = left - 1, j = right + 1;
        while (true) {
            do {
                count++;
                i++;
            } while (a[i].compareTo(pivot) < 0);

            do {
                count++;
                j--;
            } while (a[j].compareTo(pivot) > 0);

            if (i < j) {
                count++;
                Comparable temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            } else {
                return j;
            }
        }
}

还是像这样？

public static int partition(Comparable[] a, int left, int right) {
            int count = 0;
            Comparable pivot = a[(left + right) / 2];
            int i = left - 1, j = right + 1;
            while (true) {
                do {
                    i++;
                } while (a[i].compareTo(pivot) < 0);
    
                do {
                    j--;
                } while (a[j].compareTo(pivot) > 0);
    
                if (i < j) {
                    count++;
                    Comparable temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                } else {
                    return j;
                }
            }
    }

标签： javaalgorithmquicksortanalysis