排序算法的c++实现—

我们利用最大堆可以实现数组从小到大的原址排序，利用最小堆的可以实现对数组从大到小的原址排序。

1 二叉堆的简单介绍：

最大堆与最小堆可以当作通过数组来实现的一个完全二叉树，除了最底层之外其它层都是满的，并且最底层也是从左到右填充的。在最大堆中，父结点的值大于或等于子结点的值；在最小堆中，父结点的值小于或等于子结点的值。

当堆的元素在数组中下标从1开始时，很容易计算出父结点/左子结点/右子结点的下标：当父结点的下标为 i 时，左孩子下标为2i，右孩子的下标为2i+1;当孩子结点为j时，父结点的下标为 j/2。

但是呢，数组的下标都是从0开始的，所以呢，关于父结点与子结点的关系要稍微绕一下：当父结点的下标为 i 时，左孩子下标为2i+1，右孩子的下标为2(i+1);当孩子结点为j时，父结点的下标为 (j-1)/2。

2 使用最大堆或最小堆实现排序

以使用最大堆进行从小到大的排序为例，假设最大堆使用长度为N的数组表示，数组下标为0（对应堆根结点）的值最大。因此呢，我们可以把数组下标为0的值与数组下标为N-1的值进行交换，并把堆的大小由N减小为N-1并维护最大堆的性质；接下来不断重复以上过程，直到堆的大小变为1为止。

说明几点：

1 堆排序为为原址排序，它不需要额外的内存空间;

2 通常使用最大堆实现从小到大的排序，使用最小堆来实现从大到小的排序；

3 堆排序不是稳定的排序算法;

4 堆排序的时间复杂度为O(NlogN);

代码如下：

 /***********************************************************************

 *   Copyright (C) 2019  Yinheyi. <chinayinheyi@163.com>

 *

 * This program is free software; you can redistribute it and/or modify it under the terms

 * of the GNU General Public License as published by the Free Software Foundation; either

 * version 2 of the License, or (at your option) any later version.

 *   Brief:

 *   Author: yinheyi

 *   Email: chinayinheyi@163.com

 *   Version: 1.0

 *   Created Time: 2019年05月07日 星期二 21时41分02秒

 *   Modifed Time: 2019年05月09日 星期四 22时12分52秒

 *   Blog: http://www.cnblogs.com/yinheyi

 *   Github: https://github.com/yinheyi

 *

 ***********************************************************************/

 // 堆使用一个数组表示， 它可以当作一个完全二叉树，除了最底层之外，其它层都是满的，

 // 并且最底层也是从左到右填充的。

 //

 // 当堆的下标（数组的下标）从1开始时比较好计算。因为：

 //      1. 当父结点为i时， 左孩子为2i,  右孩子为2i+1;

 //      2. 当孩子结点的下标为j时，父结点的下标为j/2 (根结点为父结点）;

 //      3. 一个结点的下标为k时， 则它所有的深度为 floor(logK);

 //      4. 当一个堆共n个元素时，它的高度为floor(logN).

 //

 //                    1

 //                /       \

 //             2             3

 //           /   \         /    \

 //         4      5       6       7

 //        / \    / \     /  \   /   \

 //      8    9  10  11  12   13 14   15

 //

 //

 // 但是呢，数组的下标都是从0开始的，所以呢，我们下代码时，还是需要从0开始,而此时：

 //     1. 当父结点的下标为i时，左孩子为2i+1, 右孩子为2*(i+1)

 //     2. 当孩子结点的下标为j时，父结点的下标为（j-1)/2.

 //

 //                    0

 //                /       \

 //             1             2

 //           /   \         /    \

 //         3      4       5       6

 //        / \    / \     /  \   /   \

 //      7    8  9  10  11   12 13   14

 //

 //

 //

 /**************************     代码如下      ****************************/

 // 定义三个宏，分别用于求左孩子/右孩子/父结点的下标。

 #define LEFT(i) (((i) << 1) + 1)

 #define RIGHT(i) (((i) + 1) << 1)

 #define PARENT(i) (((i) - 1) >> 1)

 // 小于比较函数

 bool less(int lhs, int rhs)

 {

     return lhs < rhs;

 }

 // 大于比较函数

 bool greate(int lhs, int rhs)

 {

     return lhs > rhs;

 }

 typedef bool (*Comp)(int, int);

 // 交换两个元素的值

 static inline void swap(int& lhs, int & rhs)

 {

     int _nTemp = lhs;

     lhs = rhs;

     rhs = _nTemp;

 }

 // 假设一个节点的左子树与右子树都满足堆的性质，而该节点不满足最大堆或最小堆的性质，该

 // 函数实现调整节点位置，维护堆的性质。

 // 输入参数分别表示: 堆的数组/数组长度/节点i的下标/表示比较的二元谓词

 // 复杂度为O(logN).

 void Heapify(int array[], int nLength_, int nIndex_, Comp CompFunc)

 {

     if (array == nullptr || nIndex_ >= nLength_ || nIndex_ <  || CompFunc == nullptr)

         return;

     int _nLeft = LEFT(nIndex_);

     int _nRight = RIGHT(nIndex_);

     // 初始化最大值节点的下标;

     int _nLargest = nIndex_;

     if ( _nLeft < nLength_ && !CompFunc(array[_nLargest], array[_nLeft]))

     {

         _nLargest = _nLeft;

     }

     if (_nRight < nLength_ && !CompFunc(array[_nLargest], array[_nRight]))

     {

         _nLargest = _nRight;

     }

     /* 此时不需要维护堆的性质，直接返回   */

     if (_nLargest == nIndex_)

     {

         return;

     }

     swap(array[nIndex_], array[_nLargest]);

     Heapify(array, nLength_, _nLargest, CompFunc);

 }

 // 使用一个数组建立一个最小堆或最大堆。

 // 输入参数为：一维数组/数组的长度/表示比较的二元谓词，用于控制建最小堆还是最大堆

 // 复杂度为O(N).

 void BulidHeap(int array[], int nLength_, Comp CompFunc)

 {

     if (array == nullptr || nLength_ <=  || CompFunc == nullptr)

         return;

     // 从最后一个元素的父节点开始调用Heapify()函数来建堆。

     for (int i = PARENT(nLength_ - ); i >=; --i)

     {

         Heapify(array, nLength_, i, CompFunc);

     }

 }

 // 堆排序的函数

 // 说明：1. 通过建立[最大堆]可以实现[从小到大]的排序;

 //       2. 通过建立[最小堆]可以实现[从大到小]的排序

 //       3. 堆排序为原址排序，它不需要借助额外的空间.(归并排序不是原址排序）

 //       4. 堆排序的复杂度为O(NlogN).

 //

 // 堆排序的思想 (以从小到大排序说明）：

 //       第一步：建立一个最大堆;

 //       第二步：把首元素与最后一个元素进行交换;

 //       第三步：把堆的大小减1,对新的堆进行维护维的性质;

 //       第四步：把首元素与倒数第二个元素进行交换;

 //       第五步：把堆的大小减1,对新的堆进行维护维的性质;

 //       .......

 //

 void HeapSort(int array[], int nLength_, Comp CompFunc)

 {

     if (array == nullptr || nLength_ <= || CompFunc == nullptr)

         return;

     BulidHeap(array, nLength_, CompFunc);

     for (int i = nLength_; i >= ; /* 循环内 */)        // i表示当前堆的大小

     {

         swap(array[], array[--i]);

         Heapify(array, i, , CompFunc);

     }

 }

 /************    测试     *****************/

 #include <iostream>

 // 打印数组函数

 void PrintArray(int array[], int nLength_)

 {

     if (nullptr == array || nLength_ <= )

         return;

     for (int i = ; i < nLength_; ++i)

     {

         std::cout << array[i] << " ";

     }

     std::cout << std::endl;

 }

 // 主函数

 int main(int argc, char* argv[])

 {

     int array[] = { , , , -, , , , , -, -};

     PrintArray(array, );

     HeapSort(array, , greate);

     PrintArray(array, );

     return ;

 }

巴特西

排序算法的c++实现——堆排序

1 二叉堆的简单介绍：

2 使用最大堆或最小堆实现排序

最新文章

热门文章