堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

算法思想:

*
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;

*
将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

*

由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

代码:
#include <iostream> #include <algorithm> using namespace std; //
堆排序:(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。 void max_heapify(int arr[], int start, int
end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <=
end) { //若子节点在范围内才做比较 if (son + 1 <= end && arr[son] < arr[son + 1])
//先比较两个子节点指标,选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成,直接跳出函数
return; else { //否则交换父子內容再继续子节点与孙节点比較 swap(arr[dad], arr[son]); dad = son; son
= dad * 2 + 1; } } } void heap_sort(int arr[], int len) { //初始化,i从最后一个父节点开始调整
for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1);
//先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完成 for (int i = len - 1; i > 0;
i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); } } int main() { int
arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2,
5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout
<< endl; return 0; }
 

排序思想

1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

 

首先我们给定一个无序的序列,将其看做一个堆结构,一个没有规则的二叉树,将序列里的值按照从上往下,从左到右依次填充到二叉树中。

 对于一个完全二叉树,在填满的情况下(非叶子节点都有两个子节点),每一层的元素个数是上一层的二倍,根节点数量是1,所以最后一层的节点数量,一定是之前所有层节点总数+1,所以,我们能找到最后一层的第一个节点的索引,即节点总数/2(根节点索引为0),这也就是第一个叶子节点,所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢?这个计算方式仍然适用,当我们从上往下,从左往右填充二叉树的过程中,第一个叶子节点,一定是序列长度/2,所以第最后一个非叶子节点的索引就是
arr.len / 2 -1,对于此图数组长度为5,最后一个非叶子节点为5/2-1=1,即为6这个节点

那么如何构建呢? 我们找到了最后一个非叶子节点,即元素值为6的节点,比较它的左右节点中最大的一个的值,是否比他大,如果大就交换位置。

在这里5小于6,而9大于6,则交换6和9的位置。

 

技术
今日推荐
阅读数 169685
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信