【算法】堆排序

浅浅的花香味﹌ 2022-06-15 12:21 140阅读 0赞

堆排序是建立在堆这种数据结构上的一种排序算法，是选择排序的一种。  
堆排序的思想是：利用最大堆（或最小堆）输出堆顶元素，即最大值（或最小值），再将剩下的元素重新生成最大堆（或最小堆），继续输出堆顶元素，重复此过程，直到全部元素都被输出，得到的输出序列就是有序序列。  
很显然，堆排序算法的实现只需要借助之前的博文中提到的堆的建立和删除算法即可完成。  
我们可以新建一个数组用于存放输出序列，不过这样太过麻烦。我们只需每次将输出的堆顶元素与堆中最后一个元素交换并将堆的大小减一即可，所以为了得到增序序列，需要建立最大堆。

下面给出代码：  
由于建立最大堆和删除堆顶元素的过程都需要进行向下过滤调整，所以将这一过程单独拿出来写成函数Ajust（）。

void Adjust(int *a, int i, int n)
    {
        //对数组a的前n个元素，从元素i开始向下迁移调整
        int parent,child,temp;
        parent = i;
        temp = a[i];
        while((parent*2+1) <= (n-1)){
            child = parent*2+1;
            if((child != n-1)&&(a[child] < a[child+1]))
                child++;  //child指向两个子结点中较大的那个
            if(temp >= a[child])
                break;
            else{
                a[parent] = a[child];//将child元素移动到父节点的位置
                parent = child;//parent指向下一层较大的结点
            }
        }
        a[parent] = temp;//将temp放到当前位置
    }
    
    void HeapSort(int *a, int n)
    {
        int temp;
        for(int i = (n-2)/2; i>=0; i--)
            Adjust(a,i,n); //建立最大堆
        for(int i = n-1; i>0; i--){
            temp = a[i];
            a[i] = a[0];
            a[0] = temp; //将堆中第一个和最后一个元素换位
            Adjust(a, 0, i); //从有i个结点的新堆的根结点开始向下过滤调整
        }
    }