选择排序之——堆排序（c/c++）

堆是一类特殊的数据结构的统称。堆在逻辑结构上可以看作为树&＃xff0c;但是物理结构是通过顺序表来实现的。堆总是满足下列性质&＃xff1a;

堆中某个节点的值总是不大于或不小于其父节点的值&＃xff1b;

堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大顶堆&＃xff0c;根节点最小的堆叫做最小堆或小顶堆。

堆是非线性数据结构&＃xff0c;相当于一维数组&＃xff0c;但有两个直接后继。

堆的定义如下&＃xff1a;n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时&＃xff0c;称之为堆。

(ki <&＃61; k2i,ki <&＃61; k2i&＃43;1)或者(ki >&＃61; k2i,ki >&＃61; k2i&＃43;1), (i &＃61; 1,2,3,4...n/2)

堆排序算法&＃xff1a;按照堆的定义建成小&＃xff08;大&＃xff09;顶堆&＃xff0c;输出堆顶的最小&＃xff08;大&＃xff09;数&＃xff0c;再对剩余元素重新建堆&＃xff0c;再输出&＃xff0c;再建堆......

    (1)初始时如何建堆&＃xff1f;(2)如何调整剩余元素使成为一个堆&＃xff1f;   

    问题的关键在于调整&＃xff0c;初始建堆也可以看做是调整所有元素成为一个堆。

堆总是一个完全二叉树&＃xff0c;而树的叶子节点自身便是一个堆&＃xff0c;不需要调整&＃xff1b;只有有孩子的节点才会不符合堆的要求。本文堆排序算法的数组从下标1开始&＃xff0c;假设数组有n个数&＃xff0c;下标自1至n&＃xff0c;则最后一个有孩子的节点的下标是n/2&＃xff08;向下取整&＃xff09;。从最后一个有孩子的节点往前进行查找&＃xff0c;n/2-1&＃xff0c;n/2-2&＃xff0c;.......&＃xff0c;1。

比如小顶堆 13 36 24 85 47 30 53 91共8个数&＃xff0c;8/2&＃61;4&＃xff0c;从第四个数85开始&＃xff0c;将它自身作为根节点来调整堆&＃xff0c;再对第三个数24开始调整堆...直到第一个数&＃xff0c;这样这8个数就构成了一个堆。小顶堆建好之后&＃xff0c;第一个数便是最小的数&＃xff0c;将它与第八个数相交换&＃xff0c;再对前7个数调整建堆&＃xff0c;建好之后将此时第一个数与第七个数相交换&＃xff0c;再对前6个数建堆......

本算法通过建立小顶堆来进行排序&＃xff0c;这样得到的输出序列为降序序列。

堆排序算法的时间复杂度为o(nlogn)&＃xff0c;空间复杂度为0(1)。它是一种不稳定的排序方法。

heapAdjust函数用来调整数组使成为一个堆&＃xff0c;如下&＃xff1a;该数列除了arr[s]外其余数均满足堆定义&＃xff0c;它对数列arr{s...m]进行处理&＃xff0c;使得该数列均满足堆定义。

void heapAdjust(int* arr, int s, int m){//数组arr[s...m]中除了arr[s]外其余元素均符合堆的定义&＃xff0c;现调整arr[s]使得//arr[s...m]均满足堆定义int i;int rc &＃61; arr[s];for (i &＃61; 2 * s; i <&＃61; m; i *&＃61; 2){if (i arr[i &＃43; 1])&＃43;&＃43;i;if (rc

完整代码如下&＃xff1a;