iOS开发算法--堆排序

待我称王封你为后i 2023-10-17 13:26 6阅读 0赞

![strip][]

堆排序

详细代码请参考[Algorithm][]。参考代码比文字好理解。

堆排序是时间复杂度为O(N\*logN)的排序方法。是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A\[PARENT\[i\]\] >= A\[i\]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1）.它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前 和排序后他们的相对位置不发生变化）

##### 堆的存储 #####

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 *i + 1和2* i + 2。如第0个结点左右子结点下标分别为1和2。

![1240][]

##### 堆的操作——插入删除 #####

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。

堆的删除，按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。

![1240 1][]

##### 堆排序 #####

堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。由于堆也是用数组模拟的，故堆化数组后，第一次将A\[0\]与A\[n - 1\]交换，再对A\[0…n-2\]重新恢复堆。第二次将A\[0\]与A\[n – 2\]交换，再对A\[0…n - 3\]重新恢复堆，重复这样的操作直到A\[0\]与A\[1\]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。

##### 大根堆和小根堆 #####

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。堆中任一子树亦是堆。堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。

大根堆排序算法的基本操作：  
①建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。

②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。

③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)。

[strip]: http://upload-images.jianshu.io/upload_images/1170656-fc6040d719b38ba0.gif?imageMogr2/auto-orient/strip
[Algorithm]: https://github.com/dangdangfeng/Algorithm
[1240]: http://upload-images.jianshu.io/upload_images/1170656-93d8ca6bb0141c27.jpeg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240
[1240 1]: http://upload-images.jianshu.io/upload_images/1170656-faef5d3396f116f8.jpeg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240