试设计一算法，使得在二叉堆O(n)算法的时间内重排数组，使所有取负值的排序码排

来源：蜘蛛抓取(WebSpider) 时间：2016-05-03 00:38 标签： O(1/n)算法

在继续学下去之前，我们先来看看我们学习堆这个数据结构到底有什么意义，或者说有什么用。
- Google map（即在两个地点之前寻找最短的路径）
- 所有的优先队列问题

那么我们在上次提到过一个问题，我们所有的操作都是建立在一个已经建好的堆中，但是现实中，我们怎么可能那么轻松就得到一个建好的堆呢，所以我们还是得自己在一堆毫无规律的数组中，自己建立一个二叉堆。
那么构建堆的最好方式是什么呢？（也就是我们怎么写一个builtHeap（）的方法）
假设我们要把下面的一组数构建成二叉堆：
我们需要把它们一个一个插入堆中（假设一开始有个空堆），我们上篇讲过，我们往堆中插入一个元素的算法复杂度为O（logN），那么我们插入N个元素呢？当然就是O（n log n）了！
下面我们就先说说具体的步骤：
1. 按原始顺序将所有元素插入（构建）二叉树，复杂度为（O（n））
2. 从树的最底层开始，寻找第一个带有孩子的节点（例如在 n/2处），对每个元素实行 down-heap操作。调整整个树。

老规矩，来波图文解释:
1. 首先，我们按顺序写出数组，并将他们构建成一个二叉树，如图：
2. 接着我们寻找我们的最底层的，含有孩子的节点，也就是43，再看看我们for循环，此时，heapSize的值为9,int（9/2） = 4.如下图：
4. 重复上述步骤，直到我们的堆顶完成后，我们在检查右边是否符合：
5. 最后我们就建立了我们的小堆，这个过程实际就是一个插入元素的过程，复杂度就是O（n）

好了，现在再来谈谈堆排序。假设我们现在已经从上述的步骤中建立了一个完整的堆，那么我们可以通过以下的步骤来实现一个堆的排序。
- 首先，heapify一个数组（即在未排序的数组上调用build-heap，建立一个堆）
- 其次，遍历整个数组并执行dequeue（）操作，但注意此时不是返回最小元素，而是与最后一个元素进行交换
- 循环完成后，数组将从低到高排序。

有点不理解吗？图文说话：
1. 假设我们给定一个未成堆的数组，如下所示：
2. 执行我们的builtHeap（）操作，如下所示：
3. 循环遍历堆，并调用dequeue操作，将根元素与堆末尾的元素交换，heapSize（）相应减一：
4. 此时按照dequeue（）原理，根应该变为了5，heapSize由于减一，相应的堆末尾变成了22，如下图：
5. 执行3的操作，变成：
6. 一直这样，直到heapSzie为0的时候，堆排序完成。（绿色部分代表已经完成的排序）
7. 此时这就是一个已经排好序的堆，算法复杂度为O（nlog n）。

有机会我会用C++将整个过程写出来。

* 最坏情况：O(n2) 如果未优化的冒泡排序，最好情况也是O（n2），优化后最好情况是O（n）

不过针对上述代码还有两种优化方案。

优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可（程序如下）。

优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了（上面程序中" j<=len-1-i" 实现）。

选择排序无疑是最简单直观的排序。它的工作原理如下。

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

* 基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列前面，直到全部记录排序完毕。

* 最坏情况：O（n2） ，最好情况：O（n2）

插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果被扫描的元素（已排序）大于新元素，将该元素后移一位

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

* 最坏情况：输入数组已反向排序 O（n2）； 最好情况：输入数组已排序 O（n）；平均情况：O（n2）

* 由于插入排序其内层循环非常紧凑，对于小规模输入，插入排序是一种非常快的排序算法

//移完所有大于nums[i]的值后，j刚好指向最靠前一个大于nums[i]的位置

希尔排序，也称递减增量排序算法，实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法。

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数

，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

然后我们对每列进行排序：

将上述四行数字，依序接在一起时我们得到：

。这时10已经移至正确位置了，然后再以3为步长进行排序：

最后以1步长进行排序（此时就是简单的插入排序了）。

归并排序是采用分治法的一个非常典型的应用。

先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解，基本思路是将数组分解成

，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

* 将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，

* 得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

* 综上可知：归并排序其实要做两件事：（1）“分解”——将序列每次折半划分。（2）“合并”——将划分后的序列段两两合并后排序。

//分段 将一个数组分成2个数组

// 分段排序 再合起来

while(i<=mid && j<=high){ //把两个子序列的头元素比较，取较小者进入新序列，然后在旧序列中跳过这个较小值，开始下一次比较

while(i<=mid){ //若第一段序列还没扫描完，将其全部复制到合并序列

while(j<=high){ //若第二段序列还没扫描完，将其全部复制到合并序列

快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。

从数列中挑出一个元素作为基准数。

分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。

再对左右区间递归执行第二步，直至各区间只有一个数。

* 快速排序采用的思想是分治思想。快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),

* 然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。

* 递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。

* 所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标

开始的元素均为大根堆。于是只要从

开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。

堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将

做最大堆调整。第二次将

做最大堆调整。重复该操作直至

交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。

最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。

* 要先构建最大堆，然后循环删除堆的根节点上的最大值，并将它移到堆末尾，并将堆长度减一，再开始下一次的删除根节点

//循环，每次把根节点和最后一个节点调换位置

* 堆调整，使其生成最大堆

下面为七种经典排序算法指标对比情况：

声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。

我要回帖

更多关于 O(1/n)算法 的文章

 

随机推荐