堆排序

概念

堆分为大顶堆和小顶堆。

• 大根堆

父节点元素不小于左右孩子节点

• 小根堆

父节点不大于左右孩子节点

性质

数据结构上是完全二叉树:
父节点的索引编号为i
左孩子索引为2i+1
右孩子的索引为2(i+1)
反之索引为k的父节点索引为(k-1)/2。(向下取整)

堆排序（大根堆）

步骤

1. 堆构建

• 构建顺序

从下往上构建：从i/2开始构建堆

• 堆调整

最简单就是递归调整

2. 下沉
将第一个元素与最后一个元素交换，数组长度减一，然后重复堆构建。
关于下沉:结合构建顺序是由下往上，所以这里隐藏这一条信息-sink(k)。节点K的孩子节点为根的堆均是构建成功的子堆。

Java版本

import java.util.Arrays;
import java.util.Random;

/**
 * Created by cqs on 2017/12/16.
 */
public class HeapSort {

    Comparable[] a;//元素

    int length;//排序元素个数

    //构建堆
    private void build() {
        //从(this.length - 1) / 2开始下沉操作
        for (int i = (this.length - 1) / 2; i >= 0; --i) {
            sink(i);
        }
    }

    //交换
    private void swap(int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 下沉（非递归版）
     *
     * @param k "根"节点索引
     */
    private void sink(int k) {
        while (2 * k <= this.length) {
            int l = 2 * k + 1;
            int r = 2 * k + 2;
            int max = k;
            if (l < this.length && a[max].compareTo(a[l]) < 0) {
                max = l;
            }
            if (r < this.length && a[max].compareTo(a[r]) < 0) {
                max = r;
            }
            if (max == k) break;
            swap(max, k);
            k = max;
        }

    }

    /**
     * 下沉(递归版)
     *
     * @param k "根"节点索引
     */
    private void sink2(int k) {
        int l = 2 * k + 1;
        int r = 2 * k + 2;
        int max = k;
        if (l < length && a[max].compareTo(a[l]) < 0) {
            max = l;
        }
        if (r < length && a[max].compareTo(a[r]) < 0) {
            max = r;
        }
        if (max != k) {
            swap(k, max);
            //调整堆
            sink(max);
        }
    }

    //排序
    public void sort(Comparable[] arr) {
        this.a = arr;
        this.length = arr.length;
        build();
        while (this.length > 0) {
            swap(0, this.length - 1);
            //数组长度"减一"
            this.length -= 1;
            //因为堆顶元素子节点已经是堆了，所以直接下沉操作就可以了
            sink(0);
        }
    }


    //测试
    public static void main(String[] args) {
        HeapSort sort = new HeapSort();
        Integer[] a = new Integer[100];
        Random random = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(100);
        }

        sort.sort(a);
        System.out.println(Arrays.asList(a));
    }
}