堆排序详解（附可运行代码）

堆排序详解（附可运行代码）

堆排序

首先得明白什么是堆，将一个数组的元素排列成二叉树的形式后满足得两个条件

一颗完全二叉树对于任何一个结点而言，值大于等于（或小于等于）其所有子结点的值

如图所示就是一个大顶堆（本文全篇以大顶堆为例）：

调堆操作heapify

那怎么进行堆排序呢？接下来我们介绍 调堆操作heapify ，假如刚开始的数组元素排列成二叉树后是这样的（根结点为0号元素）

父子结点的对应关系如下：

当前结点为 “i”，父结点为(i - 1) / 2当前结点为 “i”，左儿子结点为2*i + 1，右儿子结点为2 * i + 2

调堆操作从某个结点出发，不仅将当前结点和两个子结点调成推，也会将受此次调堆操作影响的结点调成堆。

比如我们现在从根结点出发进行调堆操作：

1、我们将当前结点与其最大的儿子结点进行交换，显然当前结点最大的儿子结点是10，交换结果如下：

2、没完，由于此次调堆操作影响到了下面的这个子二叉树，也要对此二叉树进行调堆操作。由于上次调堆操作将值为4的结点换下来了，当前结点变成值为4的这个结点，与其最大的儿子结点交换。

3、此时当前结点是值为4的这个结点，再进行调堆操作，发现子结点已经越界了，于是结束了从根结点开始的调堆操作（注意：调堆操作可以从任意结点开始，并不一定是从根结点开始）

完成了上述调堆操作后，检查此时的二叉树，发现已经是一个大顶堆了。然而并不是每次完成调堆操作后，都能得到一个大顶堆（或小顶堆），为什么呢？

比如我们一开始的二叉树是这样的：

我们仍然从根结点开始调堆，经过两次的heapify操作后我们得到的并不是一个大顶堆，而是下面这样：

显然此时不是一个大顶堆。其实我们在开始堆排序前要进行一次建堆操作，建堆完成后，把根结点和末尾结点交换（最值交换到了数组末尾），然后将排序区间缩小一个元素，再从根结点开始调堆（前面的根结点和末尾结点元素交换位置改变了根结点的堆性质）

建堆操作

建堆操作从最后一个内部结点开始进行heapify操作（不是从根结点开始），然后从后往前建堆，直到根结点进行heapify后结束建堆操作。

为什么要从最后一个内部节点开始heapify呢？（写得比较啰嗦，耐心看吧…）

因为上面的结点完成heapify后，下面的结点进行heapify会影响上面结点的堆性质，因为下面结点heapify时会把大的元素交换上去，从而影响上面结点的堆性质。虽然从下面的结点开始进行heapify，下面的结点完成堆化后，进行上面结点的heapify时会把值较小的结点换下来会影响下面结点大顶堆的性质，但是没关系，heapify操作是自上而下，一直到叶节点才结束（子结点越界）。会自上而下地对受heapify影响的结点再次进行heapify。

1、对最后一个内部结点进行heapify的结果

2、对倒数第二个内部结点进行heapify的结果

3、对根结点进行heapify的结果

建堆和heapify操作懂了，接下来介绍堆排序的具体步骤：

对数组元素建堆（从最后一个内部结点开始heapify）此时根结点就是最大元素，将最大元素和最后一个结点交换，并隔离最后一个元素，缩小排序区间从根结点开始heapify重复2、3操作

完整代码如下：

/** * parent = (i-1)/2; * son1 = 2*i + 1; * son2 = 2*i + 2; */#include#includeusing namespace std;//调堆就是要当前结点满足堆的性质，在调当前结点过程中会改变其他结点的堆性质//因此使用递归函数，不停地对已改变结点进行调堆void heapify(vector &tree, int parent, int nodes_num){ //一直执行递归函数，直到对子节点调堆时，子节点越界 if(parent >= nodes_num) return ; int left_son = 2*parent + 1; int right_son = 2*parent + 2; int max = parent; //不能等于nodes_num，否则越界 if(left_son < nodes_num && tree[max] < tree[left_son]){ max = left_son; } if(right_son < nodes_num && tree[max] < tree[right_son]){ max = right_son; } if(parent != max){ swap(tree[parent], tree[max]); //父结点调堆后，再对被更换的子结点调堆 //对最初的父结点的子结点全部调堆后，此父结点完成堆化 heapify(tree, max, nodes_num); }}//建堆就是把所有的内部结点调堆void build_heap(vector &tree, int nodes_num){ int last_node = nodes_num - 1; int last_parent = (last_node-1) / 2; //初始状态时可能所有的内部结点都不满足大顶堆 //建堆只能从最后一个内部结点开始调堆，而不能从根结点开始 for(int i = last_parent; i >= 0; i--) heapify(tree, i, nodes_num);}void heap_sort(vector &tree, int nodes_num){ //先把杂乱的数据建成大顶堆 build_heap(tree, nodes_num); for(int i = nodes_num - 1; i >= 0; i--){ //交换根结点和乱序部分的最后一个元素，使得有序部分在容器尾 swap(tree[0], tree[i]); //交换根结点元素和最后一个元素后，只有根结点元素不满足大顶堆 //此时，我们对根结点调堆即可 //i表示这棵树的结点数，即乱序部分元素个数 heapify(tree, 0, i); }}int main(){ vector tree = {44,4,11,1,0,1,21,88}; heap_sort(tree, tree.size()); cout<<"排序结果："; for(int i = 0; i < tree.size(); i++) cout<

直接选择排序

/** * 时间复杂度为O(n^2) */ #includeusing namespace std;void SelectionSort(int* nums, int len){ //在后面选择最小的，往前面插入 for(int i=0; i nums[j]) min = j; } if(min != i){ int temp; temp = nums[min]; nums[min] = nums[i]; nums[i] = temp; } }}void show(int*nums, int len){ for(int i=0; i

运行结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。