//最小堆
class Dui
{
    public int[] datas;

    public Dui(int maxLength) {
        if (maxLength <= 0)
        {
            datas = new int[16 + 1];
        }
        else {
            datas = new int[maxLength + 1];
        }
    }

    public int Pop() {
        int temp = datas[1];
        datas[1] = datas[datas[0]];
        datas[0]--;
        SiftDown(1);
        return temp;
    }

    public bool isEmpty() {
        return datas[0] == 0 ? true:false;
    }

    public void ValueTo(int[] copyValues) {
        datas[0] = copyValues.Length;
        if (datas[0] < 1) {
            return;
        }
        for (int i = 1; i <= datas[0]; i++) {
            datas[i] = copyValues[i-1];
        }
        Create();//调整节点
    }

    public void Create() {
        //倒数最后一个非叶节点
        int index = datas[0] / 2;

        for (int i = index; i >= 1; i--) {
            SiftDown(i);
        }
    }

    //向下调整
    public void SiftDown(int index) {
        bool isNeedSwap = true;
        int t = index;
            
        //有左儿子
        while (index * 2 <= datas[0] && isNeedSwap) {
            if (datas[index] > datas[index * 2]) {
                t = index * 2;
            }

            //有右儿子
            if (index * 2 + 1 <= datas[0]) {
                if (datas[t] > datas[index * 2 + 1]) {
                    t = index * 2 + 1;
                }
            }

            if (index != t)
            {
                int temp = datas[index];
                datas[index] = datas[t];
                datas[t] = temp;
                index = t;
            }
            else {
                //比左右两儿子都小了
                isNeedSwap = false;
            }
        }
    }
}

static void Main(string[] args)
{
    int[] datas = new int[100000];
    Random random = new Random();
    for (int i = 0; i < 100000; i++) {
        datas[i] = random.Next(1, 10000);
    }
    Stopwatch stopwatch = new Stopwatch();
    Dui dui = new Dui(100000);
    dui.ValueTo(datas);
    stopwatch.Start();
    int j = 0;
    while (!dui.isEmpty()) {
        datas[j++] = dui.Pop();
    }
    stopwatch.Stop();
    for (j = 0; j < 100000; j++) {
        Console.WriteLine(datas[j]);
    }
            
    Console.WriteLine("用时：" + stopwatch.ElapsedMilliseconds);
    Console.ReadKey();
}

堆排序，就是利用最小堆，每次都能确定根节点的值就是当前集合中的最小值，所以每次只要将根节点输出，然后将最后一个节点替换上来再向下调整，形成新的最小堆。输出完毕，就是排序完毕了。

还有一种思路就是利用最大堆，根节点为当前集合的最大值，与最后一个节点交换，树长度减1.再向下调整，形成新的最大堆，再和最后一个元素交换....到最后树的长度只有1时，你把树的长度恢复，你会发现这是一个工整的最小堆，按数组顺序输出就是排序好的了。

模拟排序10W条随机数据用时：58ms