内部排序—堆排序

落日映苍穹つ 2022-06-13 04:51 171阅读 0赞

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：

Key\[i\]<=key\[2i+1\]&&Key\[i\]<=key\[2i+2\]或者Key\[i\]>=Key\[2i+1\]&&key>=key\[2i+2\]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆分为大顶堆和小顶堆，满足Key\[i\]>=Key\[2i+1\]&&key>=key\[2i+2\]称为大顶堆，满足 Key\[i\]<=key\[2i+1\]&&Key\[i\]<=key\[2i+2\]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

堆排序的基本思想是对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输入堆顶的最大关键字（对于大顶堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此返回，直到全部关键字排成有序序列为止。

///  /// 堆排序 /// 思想：根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。 /// 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。 /// 
    /// 
    /// 
       
    private int[] HeapSort(int[] arrData)
    {
        // 循环建立初始堆
        for (int i = arrData.Length / 2; i >= 0; i--)
        {
            HeapAdjust(arrData, i, arrData.Length);
    }
    
        // 进行n-1次循环，完成排序
        for (int i = arrData.Length - 1; i > 0; i--)
        {
            //最后一个元素和第一元素进行交换 
            int temp = arrData[i];
            arrData[i] = arrData[0];
            arrData[0] = temp;
    
            //大顶堆堆顶元素R[0]始终是未排序里面最大的
            //筛选 R[0] 结点，得到i-1个结点的堆,对未交换数组重新调整堆
            HeapAdjust(arrData, 0, i);
        }
        return arrData;
    }
    
    ///  /// 建堆、调整堆[大顶堆] /// 
    /// 数组
    /// 父节点
    /// 长度
    private void HeapAdjust(int[] arrData, int parent, int length)
    {
        int temp = arrData[parent]; // temp保存当前父节点
        int child = 2 * parent; // 先获得左孩子
    
        //循环从所有子节点中取出最大的
        while (child < length)
        {
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (child + 1 < length && arrData[child] < arrData[child + 1])
            {
                child++;
            }
    
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arrData[child])
                break;
    
            // 把孩子结点的值赋给父结点
            arrData[parent] = arrData[child];
    
            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = 2 * child;
        }
        arrData[parent] = temp;
    }