选择排序——堆排序

不念不忘少年蓝@ 2022-03-20 02:54 226阅读 0赞

/*
     *背景知识：
     *  堆是满足如下性质的完全二叉树：二叉树中任一非叶子结点关键字的值均小于（或者大于）它的孩子结点的关键字。
     *  在小根堆中，第一个元素（完全二叉树的根节点）的关键字最小；大根堆中第一个元素关键字最大。显然，根中任一
     *  子树仍然是一个堆。
     */
    
    /*
     *算法思想：
     *  若对一个大根堆（小根堆）进行如下操作：
     *      1.输出堆顶元素
     *      2.将剩余元素按关键字大小重新排列又建成一个大根堆（小根堆）。
     *      3.重复步骤1和2，直到序列中所有元素都已经输出。
     */
    
    /*
     *过程分析：
     *  由算法思想分析可知，堆排序需要解决两个问题：
     *      1.输出堆顶元素后，调整剩余元素为一个新的堆。2.将无序序列建立成一个堆。
     *
     *  对于问题1的解决：
     *      1.在输出堆顶元素后，以堆中的最后一个元素替代；也即将二叉树中最后一个叶子结点移动
     *        到根结点位置，作为二叉树的根。
     *      2.将根结点关键字的值与其左右两个子树的根结点关键字进行比较，并与其较大者进行交换
     *       （若是小根堆，则与较小者交换）
     *      3.从上到下、从左到右，对每一个子树重复步骤2，当叶子结点所在的子树也被调整完毕，则
     *        完成了一次的堆的调整过程，得到新的堆。
     *  对于问题2的解决：
     *      首先分析堆的特点，显然单结点的二叉树是堆，在完全二叉树中，所有以叶子结点为根的子
     *      树都是堆。
     *      所以，只需要应用解决问题1所用的筛选算法，自底向上逐层把所有以非叶子结点为根的子树
     *      调整为堆，直到整个完全二叉树为堆。也即，只需依次将序号为n/2,n/2-1,……,1的结点为根的
     *      子树均调整为堆即可。
     */
    
    /*
     *性能分析：
     *  时间复杂度O(nlog2n)
     */
    
    #include <stdio.h>
    #define length 9
    
    //在进行堆排序时，将完全二叉树储存在数组中。
    //也即：下标从k到m的数组元素序列描述的是以order[k]为根的完全二叉树，且以order[2k]、order[2k+1]
    //为根的子树的大根堆。
    void Sift(int order[],int k,int m)//将下标从k到m的数组序列调整为一个大根堆的筛选
    {
        int j,i;
        i=k;j=2*i;
        while(j<=m)//若j<=m，order[2*i]是order[i]的左孩子
        {
            //使j成为左右孩子中较大者的下标
            if(order[j]<order[j+1] && j<m)j++;//注意此处的j<m判定不可少，注意完全二叉树最后可能只有左子树，没有右子树的
            if(order[i]<order[j])
            {
                int temp=order[i];
                order[i]=order[j];
                order[j]=temp;
    
                i=j;//注意，此处是调整堆，所以没有交换的孩子的那边的子树已经是一个堆了，不必调整
                j=2*i;//此时需要调整的是，与根结点交换过的孩子这边的子树
            }
            else break;//如果没有发生交换，说明已经成为一个堆了。
        }
    }
    void HeapSort(int *order,int n)//注意，n是最后一个数字的下标，不是数组长度
    {
        int i;
        for(i=n/2;i>0;i--)Sift(order,i,n);//建立堆。则此时order[1]就是最大值了。
    
        //由于0序列不满足左子树为2*i的特点，所以，order中0号位不参与排序。
        //堆排序是对order[1]~order[n]进行排序。
        for(i=n;i>1;i--)//进行n-1趟排序。
        {
            int temp=order[1];
            order[1]=order[i];
            order[i]=temp;//经过本次交换后，将堆中的最大值放到了最后面，然后对剩下的进行堆调整。
    
            Sift(order,1,i-1);
        }
    }
    
    int main()
    {
        int order[length]={0,49,52,65,97,35,13,27,49};
        HeapSort(order,length-1);
        int i;
        for(i=1;i<length;i++)printf("%d  ",order[i]);
        return 0;
    }