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

            //判断子结点与父结点大小
            if (data.get(son) < dadValue) {
                break;
            }

            //将子结点挪到父结点
            data.set(index, data.get(son));
            index = son;
            son = son * 2 + 1;
        }
        data.set(index, dadValue);
    }
}

@@ -628,21 +628,21 @@
  @param 
-index
+start
  %E5%A0%86%E8%B0%83%E6%95%B4%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE
@@ -656,19 +656,19 @@
  @param 
-l
 en
+d
  %E5%A0%86%E8%B0%83%E6%95%B4%E7%BB%93%E6%9D%9F%E4%BD%8D%E7%BD%AE
@@ -762,22 +762,22 @@
 int 
-l
 en
+d
 , int 
-index
+start
 ) %7B%0A
@@ -788,48 +788,13 @@
     
-int dadValue = data.get(index);%0A        
+for (
 int 
@@ -799,21 +799,21 @@
 t son = 
-index
+start
  * 2 + 1
@@ -817,33 +817,54 @@
 + 1;
-%0A        while (son %3C len
+ son + 1 %3C end; start = son, son = son * 2 + 1
 ) %7B%0A
@@ -893,11 +893,11 @@
 1 %3C 
-l
 en
+d
  && 
@@ -1066,18 +1066,25 @@
 on) 
-%3C dadValue
+%3E data.get(start)
 ) %7B%0A
@@ -1103,198 +1103,93 @@
     
-break;%0A            %7D%0A%0A            //%E5%B0%86%E5%AD%90%E7%BB%93%E7%82%B9%E6%8C%AA%E5%88%B0%E7%88%B6%E7%BB%93%E7%82%B9%0A            data.set(index, data.get(son));%0A            index = son;%0A            son = son * 2 + 1;%0A        %7D%0A        data.set(index, dadValue);
+//%E5%B0%86%E5%AD%90%E7%BB%93%E7%82%B9%E6%8C%AA%E5%88%B0%E7%88%B6%E7%BB%93%E7%82%B9%0A                SortUtils.swap(data, son, start);%0A            %7D%0A        %7D
 %0A   

change : 修改堆排序的实现。