algorithm - 具有最多和最少比较的堆排序输入

Question

您好，我环顾四周，没能找到对这个问题的任何直接讨论。大多数似乎涵盖了时间复杂度和大 O 表示法。

我想知道堆排序算法的输入顺序是否以及如何影响对输入进行排序所需的比较次数。例如，采用按升序(从最小到最大)排序的堆排序算法......如果我输入一组已经以这种方式(升序)排序的整数，与一组输入相比需要进行多少次比较降序排列(从大到小)？与一组完全随机的相同数字相比怎么样？

public class Heap {
    // This class should not be instantiated.
    private Heap() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * 
     * @param pq
     *            the array to be sorted
     */
    public static void sort(Comparable[] pq) {
        int N = pq.length;
        for (int k = N / 2; k >= 1; k--)
            sink(pq, k, N);
        while (N > 1) {
            exch(pq, 1, N--);
            sink(pq, 1, N);
        }
    }

    private static void sink(Comparable[] pq, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(pq, j, j + 1))
                j++;
            if (!less(pq, k, j))
                break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i - 1].compareTo(pq[j - 1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }

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

Answer 1

堆排序不同于冒泡排序和快速排序，当输入元素以降序/升序方式排序时，最好和最坏的情况不会发生。堆排序的第一步是建立一个堆(通常是最大堆)，这可以通过使用 heapify 的“筛选”版本在线性时间 O(n) 内完成，无论初始元素的顺序如何 。如果输入已经是堆，只是节省了交换的时间。
通常认为最好和最坏情况下的性能都是 O(nlogn)( the heap sort item on wiki 表示最好情况下的性能可以是 Ω(n)，并且有一个关于它的链接)，但是大 - O 表示法省略了常数因子和低阶项，因此它们在大 O 表示法中是等价的，但它们可以相差一个常数因子。

例如，我得到了给定元素的所有 720 个排列:{1,2,3,4,5,6} 并用您的代码对它们进行排序，最小/最大比较次数为 12/17，而顺序分别是 {6,1,4,2,3,5}/{1,4,2,5,6,3}。最小/最大交换次数为8/15，顺序分别为{6,3,5,1,2,4}/{1,2,3,5,4,6}。 My another post是关于最大交换次数。