package me.wayne.sort.unstable;

import java.util.List;

import me.wayne.sort.SortUtils;

public class HeapSort {

    /**
     * 堆排序,不稳定
     * 时间复杂度O(n*log2n)
     * 空间复杂度O(1)
     */
    public static void sort(List<Integer> data) {

        //从最后一个非终端结点开始建堆
        int i;
        for (i = data.size() / 2 - 1; i >= 0; i--) {
            maxHeapFix(data, data.size(), i);
        }

        //不断的将最大的数挪到最后一个,然后再第0个数开始调整堆
        for (i = data.size() - 1; i >= 1; i--) {
            SortUtils.swap(data, i, 0);
            maxHeapFix(data, i, 0);
        }
        System.out.println(data.toString());
    }

    /***
     * @param start 堆调整起始位置
     * @param end 堆调整结束位置
     * 堆调整函数,给定起始和结束位置
     */
    private static void maxHeapFix(List<Integer> data, int end, int start) {
        for (int son = start * 2 + 1; son + 1 < end; start = son, son = son * 2 + 1) {
            if (son + 1 < end && data.get(son + 1) > data.get(son)) {
                //获取两个子结点中较大的结点的引用
                son++;
            }

            //判断子结点与父结点大小
            if (data.get(son) > data.get(start)) {
                //将子结点挪到父结点
                SortUtils.swap(data, son, start);
            }
        }
    }
}

@@ -171,16 +171,70 @@
 %E5%A4%8D%E6%9D%82%E5%BA%A6O(1)%0A
+     * %E6%80%9D%E8%B7%AF:%E4%BB%8E%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E9%9D%9E%E7%BB%88%E7%AB%AF%E8%8A%82%E7%82%B9%E5%BB%BA%E4%B8%80%E4%B8%AA%E5%A4%A7%E9%A1%B6%E5%A0%86%0A     * %E7%84%B6%E5%90%8E%E4%BE%9D%E6%AC%A1%E5%B0%86%E5%A0%86%E9%A1%B6%E5%85%83%E7%B4%A0%E6%94%BE%E5%88%B0%E6%9C%80%E5%90%8E%E5%86%8D%E9%87%8D%E6%96%B0%E8%B0%83%E6%95%B4%E5%A0%86%0A
      */%0A
@@ -307,16 +307,18 @@
 %E9%9D%9E%E7%BB%88%E7%AB%AF%E7%BB%93%E7%82%B9%E5%BC%80%E5%A7%8B%E5%BB%BA
+%E5%A4%A7%E9%A1%B6
 %E5%A0%86%0A      

change : add comments for heap sort.