前提

面试中经常会遇到对堆排序的考察&＃xff0c;比如阿里巴巴2016研发工程师笔试题之一&＃xff1a;

将整数数组(7-6-3-5-4-1-2)按照堆排序的方式原地进行升序排列&＃xff0c;请问在第一轮排序结束之后&＃xff0c;数组的顺序是_____。

不了解堆排序的小伙伴此时就会比较尴尬了。

那么到底什么是堆排序呢&＃xff1f;它的原理是什么?代码又怎么实现呢&＃xff1f;

什么是堆

在介绍堆排序之前&＃xff0c;先让我们来了解一下堆及其属性&＃xff1a;

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质&＃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)

若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树&＃xff0c;则堆的含义表明&＃xff0c;完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此&＃xff0c;若序列{k1,k2,…,kn}是堆&＃xff0c;则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。

堆排序

堆排序(Heapsort)是利用堆这种数据结构而设计的一种排序算法&＃xff0c;它的最坏&＃xff0c;最好&＃xff0c;平均时间复杂度均为O(nlogn)&＃xff0c;它也是不稳定排序。堆排序的流程&＃xff1a;

1. 将无序序列构建成一个堆&＃xff0c;根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换&＃xff0c;将最大元素"沉"到数组末端;
3. 重新调整结构&＃xff0c;使其满足堆定义&＃xff0c;然后继续交换堆顶元素与当前末尾元素&＃xff0c;反复执行1-2步骤&＃xff0c;直到整个序列有序。

动图演示

代码实现

void adjuctHeap(int i, int arr[], int count) {int tmp;int max;// 条件判断检测是否到了叶子节点while (i <&＃61; count / 2 - 1) {//父节点索引为i时&＃xff0c;左子节点下标为2i&＃43;1&＃xff0c;右子节点下标为2i&＃43;2//总数为偶数时&＃xff0c;最后一个父节点没有右子节点&＃xff0c;此时tmp置为0tmp &＃61; 2 * i &＃43; 2 >&＃61; count ? 0 : arr[2 * i &＃43; 2];//max值&＃xff1a;左右子节点中更大的那个节点的下标max &＃61; arr[2 * i &＃43; 1] >&＃61; tmp ? 2 * i &＃43; 1 : 2 * i &＃43; 2;//如果子节点比父节点大&＃xff0c;则交换父子节点的值if (arr[max] > arr[i]){tmp &＃61; arr[max];arr[max] &＃61; arr[i];arr[i] &＃61; tmp;//父子节点交换完以后&＃xff0c;要判断新的子节点下面是否也有子节点&＃xff0c;如果有的话也要进行相同的调整i &＃61; max;}elsebreak;}}void heapSort(int arr[], int count) {int i;int tmp;//停留在构造成功大根堆的前一步。 count / 2 - 1 表示倒数第一个非叶子节点for (i &＃61; count / 2 - 1; i > 0; i--) adjuctHeap(i, arr, count);while (count > 1) {adjuctHeap(0, arr, count); //构造大根堆tmp &＃61; arr[0]; //取出第一个值&＃xff0c;及最大值arr[0] &＃61; arr[count - 1]; //调整最大值到最后的位置arr[count - 1] &＃61; tmp;count--; //末尾往前移动一位}}

平均时间上&＃xff0c;堆排序的时间常数比快排要大一些&＃xff0c;因此通常会慢一些&＃xff0c;但是堆排序最差时间也是O(nlogn)的&＃xff0c;这点比快排好。

结束语

至此&＃xff0c;十种常见的排序算法都已经整理完毕&＃xff0c;如果中间有什么写错或者笔误的地方还劳烦大家批评指正&＃xff0c;共同进步。