堆排序算法

问题描述

现有一组数据：23,45,18,11,13,79,72,25,3,17。
请使用快速排序算法将它们按照从小到大的顺序排列。

算法思想

（1）将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

（2）将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

（3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

程序代码

#include <iostream>
using namespace std;
const int N = 10;
/*定义交换函数*/
void swap(int& x, int& y) {//使用引用作为参数，来改变变量本身的值
    int t = x;
    x = y;
    y = t;
}
/*定义堆调整函数*/
void Heapify(int a[], int len, int k) {
    if (k < len) {
        int max = k; //根结点
        int L = 2 * k + 1; // 左子节点
        int R = 2 * k + 2; // 右子节点
        /*找出最大结点*/
        if (L < len && a[L] > a[max]) {
            max = L;
        }
        if (R < len && a[R] > a[max]) {
            max = R;
        }
        /*交换最大子节点到根结点并做递归*/
        if (max != k) {
            swap(a[k], a[max]);
            Heapify(a, len, max);
        }
    }

}
/*堆排序函数*/
void heapSort(int b[], int len) {
    /*构造最大堆*/
    for (int i = (len - 1) / 2; i >= 0; i--) {
        Heapify(b, len, i);//从最后一个父结点开始做最大堆调整,构造最大堆
    }
    for (int i = len - 1; i >= 0; i--) {//依次将最大堆的根结点（最大值）取出
        swap(b[0], b[i]);//将最大堆的根（最大值）换到最后
        Heapify(b, i, 0);//除去最大值,对交换后的二叉树做最大堆调整，使二叉树根结点始终为最大值
    }
}
int main() {

    int c[N] = { 23,45,18,11,13,79,72,25,3,17 };//定义一个数组，给定需要进行排序的序列
    for (int i = 0; i < N; i++) {
       cin>>c[i];
    }
    
    cout << "排序前：" << endl;
    for (int i = 0; i < N; i++) {
        cout << c[i] << " ";
    }
    heapSort(c, N);
    cout << "\n排序后：" << endl;
    for (int i = 0; i < N; i++) {
        cout << c[i] << " ";
    }//依次输出排序完成后的数组元素
    return 0;
}