堆排序输入，最多和最少的比较 [英] heapsort input with most and fewest comparisons

问题描述

你好，我四处张望了一下，一直没能找到这个问题的任何直接的讨论。大多数人似乎覆盖时间复杂度和大O符号。

我不知道是否和如何输入顺序成堆排序算法将影响所需要的输入进行排序比较的次数。例如，采取堆排序算法，按升序的顺序（从小到大）....如果我输入的是一个整数集已经下令以这种方式（升序）有多少的比较会是要求相比，一组输入的是订购递减方式（从大到小）？怎么样相比完全随机组相同的号码的

 公共类堆{
    //这个类不能被实例化。
    私有堆（）{
    }

    / **
     *重新排列升序排列，使用自然顺序。
     *
     * @参数PQ
     *数组进行排序
     * /
    公共静态无效排序（可比[] PQ）{
        INT N = pq.length;
        对于（INT K = N / 2; K＆GT; = 1; K--）
            水槽（PQ，K，N）;
        而（N大于1）{
            可置换（PQ，1，N--）;
            水槽（PQ，1，N）;
        }
    }

    私有静态无效汇（可比[] PQ，INT K，INT N）{
        而（2 * K＆LT; = N）{
            INT J = 2 * K;
            如果（J＆n种安培;＆安培;少（PQ，J，J + 1））
                J ++;
            如果（！少（PQ中，k，j））后
                打破;
            可置换（PQ，K，J）;
            K = D];
        }
    }

    私有静态布尔以下（可比[] PQ，诠释我，诠释J）{
        返回PQ [我 -  1] .compareTo（PQ [J  -  1]）＆LT; 0;
    }

    私有静态无效可置换（Object []对象PQ，诠释我，诠释J）{
        对象交换= PQ [我 -  1];
        PQ [我 -  1] = PQ [J  -  1];
        PQ [J  -  1] =调剂;
    }

    //为V＆LT; W'
    私有静态布尔少（相当于V，可比W）{
        返回（v.compareTo（瓦特）℃，）;
    }
}
 

解决方案

堆排序从冒泡排序和快速排序的不同，最好的和最坏的情况不会发生，当输入的元素是有序的升/降的方式。堆排序的第一步是建立一个堆（最大堆一般），它可以以线性时间O（N）来完成，通过使用筛选下来版本heapify的，无论什么样的顺序初始元素。如果输入已经是一个堆，它只是节省了时间交流。
它通常被认为是最好的和最坏的情况下表现均为O（nlogn）（ 对维基堆排序项说，最好的情况下性能可Ω（N），并有一个关于它的）的链接，但大O符号遗漏的常数因子和低阶项，所以他们在大O符号等价的，但他们可以通过一个常数因子不同。

例如，我得到的所有720排列一个给定的elemnts：{1,2,3,4,5,6}并与code排序，比较的最小/最大数量为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}分别。 <一href="http://stackoverflow.com/questions/22214495/find-a-heapified-array-when-converting-it-to-a-sorted-array-the-total-number-of">My另一篇文章是关于交流的最大数量。

Hi I've looked around a bit and haven't been able to find any direct discussion of this question. Most seem to cover time complexity and the big O notation.

I'm wondering if and how the order of input into a heapsort algorithm will impact the number of comparisons needed to sort the input. For example, take a heapsort algorithm that sorts in ascending order (smallest to largest)....if I input a set of integers already ordered in this way (ascending) how many comparisons would it require compared to a set of input that is ordered in a descending manner (largest to smallest)? How about compared to a completely randomized set of the same numbers?

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);
    }
}

解决方案

Heap sort is different from bubble sort and quick sort, the best and worst cases wouldn't happen when the input elements are ordered in a descending/ascending manner. The first step of heap sort is building a heap(max-heap in general) which can be done in linear time O(n) by using the "sift down" version of heapify, no matter what order the initial elements are. If the input is already a heap, it just saves the time for exchange.
It's generally considered the best and worst cases performance are both O(nlogn)(the heap sort item on wiki says the best case performance can be Ω(n), and there's a link about it), but the big-O notation omits constant factors and lower order terms, so they are equivalent in big O notation, but they can differ by a constant factor.

For example, I get all 720 permutations of a given elemnts:{1,2,3,4,5,6} and sort them with your code, the minimum/maximum number of comparisons is 12/17 while the order is {6,1,4,2,3,5}/{1,4,2,5,6,3} respectively. And the minimum/maximum number of exchanges is 8/15 while the order is {6,3,5,1,2,4}/{1,2,3,5,4,6} respectively. My another post is about the maximum number of exchanges.

这篇关于堆排序输入，最多和最少的比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！