一篇读懂移动平均算法(移动平均算法的空间复杂度)

面试中经常会遇到对堆排序的考察，比如阿里巴巴2016研发工程师笔试题之一:将整数数组按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，

 

前提面试中经常会遇到对堆排序的考察，比如阿里巴巴2016研发工程师笔试题之一：将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是_____不了解堆排序的小伙伴此时就会比较尴尬了。

那么到底什么是堆排序呢？它的原理是什么?代码又怎么实现呢？什么是堆在介绍堆排序之前，先让我们来了解一下堆及其属性：堆(heap)是计算机科学中一类特殊的数据结构的统称堆通常是一个可以被看做一棵树的数组对象。

堆总是满足下列性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆是非线性数据结构，相当于一维数组，有两个直接后继堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆(ki <= k2i,ki = k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)。

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

堆排序堆排序（Heapsort）是利用堆这种数据结构而设计的一种排序算法，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序堆排序的流程：将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;。

将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行1-2步骤，直到整个序列有序。动图演示

代码实现void adjuctHeap(int i, int arr[], int count) { int tmp; int max; // 条件判断检测是否到了叶子节点while (i <=

count / 2 - 1) { //父节点索引为i时，左子节点下标为2i+1，右子节点下标为2i+2//总数为偶数时，最后一个父节点没有右子节点，此时tmp置为0 tmp = 2 * i +

2 >= count ? 0 : arr[2 * i + 2]; //max值：左右子节点中更大的那个节点的下标max = arr[2 * i + 1] >= tmp ? 2 * i + 1 : 2

* i + 2; //如果子节点比父节点大，则交换父子节点的值if (arr[max] > arr[i]) { tmp = arr[max]; arr[max] = arr[i]; arr[i] = tmp;

//父子节点交换完以后，要判断新的子节点下面是否也有子节点，如果有的话也要进行相同的调整 i = max; } elsebreak; } } void heapSort(int arr[], int

count) { int i; int tmp; //停留在构造成功大根堆的前一步 count / 2 - 1 表示倒数第一个非叶子节点for (i = count / 2 - 1; i > 。

0; i--) adjuctHeap(i, arr, count); while (count > 1) { adjuctHeap(0, arr, count

); //构造大根堆 tmp = arr[0]; //取出第一个值，及最大值 arr[0] = arr[count - 1];

//调整最大值到最后的位置 arr[count - 1] = tmp; count--; //末尾往前移动一位 } }

平均时间上，堆排序的时间常数比快排要大一些，因此通常会慢一些，但是堆排序最差时间也是O(nlogn)的，这点比快排好结束语至此，十种常见的排序算法都已经整理完毕，如果中间有什么写错或者笔误的地方还劳烦大家批评指正，共同进步。