一，概念

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

二，算法思想：

堆排序的基本思想是：1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了

三，代码：

 #include<stdio.h> #include<stdlib.h> //堆排序用于查找最大值 或者 最小值 void show(int *p, int n) {     for (int i = 0; i < n;i++)     {         printf("%4d", p[i]);     }     printf("n"); } void findmax(int *arr, int size) {     for (int j = size - 1; j>0; j--)//从尾部循环到头部     {         int parent = j / 2;//定义         int child = j;//记录当前下标         if (j < size - 1 && arr[j]< arr[j + 1])//该行的j<size-1 可以避免数组越界         {                 child++;         }         if (arr[child]>arr[parent])         {             int temp = arr[child];             arr[child] = arr[parent];             arr[parent] = temp;         }     } } void heapsort(int *arr, int size) {     for (int j = size; j > 0; j--)     {         findmax(arr, j);         int temp = arr[0];         arr[0] = arr[j - 1];         arr[j - 1] = temp;     } } void heapsort1(int *arr, int size) {          for (int i = 0; i < size; i++)     {         findmax(arr + i, size-i);     } } void main() {      int a[11] = { 10, 13, 99, 12, 30, 14, 50, 19, 60, 29 };     int b[6] = { 2, 5, 66, 25, 8, 99 };     //printf("%dn", a[10]);     //int *pp = a;     //printf("%d", pp[10]);     //show(b, 6);     //findmax(a, 11);     //show(a, 11);     //heapsort(a, 11);     heapsort1(a, 10);     show(a, 11);  }   void findmax1(int *arr1, int size1) {     int *arr = arr1;     int size = size1;     for (int i = 0; i < size1; i++)     {         arr = arr1;         arr = arr + i;          size = size1 - i;         for (int j = size-1; j > 0; j--)//从尾部循环到头部         {             int parent = j / 2;//定义             int child = j;//记录当前下标             if (j < size - 1 && arr[j]< arr[j + 1])//该行的j<size-1 可以避免数组越界             {                 child++;             }             if (arr[child]>arr[parent])//最大值攀顶             {                 int temp = arr[child];                 arr[child] = arr[parent];                 arr[parent] = temp;             }         }     } } 

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)