©2020-2024 ioDraw All rights reserved,
Privacy Policy
堆排序（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的位置。