堆排序

堆的定义：一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储（不适用数组第一个位置）
堆有序：当一颗二叉树的每个节点都大于等于它的两个子节点时，它被称为堆有序。

堆排序是一种选择排序，其时间复杂度为O(nlogn)。
实现的大概思路：

• 将无序数列构造成堆有序；
  首先取最后一个非子节点的元素的索引k（N/2取整）然后逐次向上进行构造，先比较此k节点的两个子节点的大小，如果左孩子2k小于右孩子2k+1，则继续比较右孩子与父节点的大小，顺序不同则交换右孩子与父节点；如果左孩子2k大于右孩子2k+1，则继续比较左孩子与父节点，顺序不同则交换左孩子与父节点。循环遍历所有非子节点，最后就能实现堆有序。

• 对堆存储的元素进行排序。
  因为在堆第一个节点的值是整个堆中最大的值，所以将与堆的最后一个值进行交换，然后将前N -1个节点重新实现堆有序，此时堆第一个节点的值成为了第二大的值，将其与整个堆中倒数第二个值进行交换。循环遍历，并进行节点交换，最后实现了堆排序。

堆排序

堆排序是唯一能够同时最优地利用空间和时间的方法——在最坏的情况下它也能保证使用~ 2NlgN次比较和恒定的额外空间。但现代操作系统的许多应用很少使用它，因为它无法利用缓存。

• java

public class Heap {

    public static void sort(Comparable[] a) {
        int N = a.length - 1;
        for (int k = N / 2; k >= 1; k--) {
            sink(a, k, N);
        }
        while (N > 1) {
            exch(a, 1, N--);
            sink(a, 1, N);
        }
    }

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

    public static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String[] a = {" ", "80", "30", "60", "40", "20", "10", "50", "70"};
        show(a);
        sort(a);
        show(a);
    }
}

• python

class Heap:
    def heap_sort(self, data):
        data.insert(0, "")
        n = len(data) - 1
        k = n // 2
        while k >= 1:
            self.sink(data, k, n)
            k -= 1

        while n > 1:
            self.exch(data, 1, n)
            n -= 1
            self.sink(data, 1, n)
        data.pop(0)

    def sink(self, data, k, length):
        while 2 * k <= length:
            j = k * 2
            if j < length and self.less(data[j], data[j+1]):
                j += 1
            if not self.less(data[k], data[j]):
                break
            self.exch(data, k, j)
            k = j

    def less(self, x, y):
        return x < y

    def exch(self, data, i, min_index):
        data[i], data[min_index] = data[min_index], data[i]


if __name__ == "__main__":
    s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
    heap = Heap()
    heap.heap_sort(s)
    print(s)