首页 / 操作系统 / Linux / 排序算法（2） 堆排序 C++实现

堆

1 数组对象2 可以视为一棵完全二叉树3 一个堆可以被看作一棵二叉树和一个数组，如下图所示：4 下标计算（通常使用内联函数或者宏来定义下标操作）：

• 已知某个结点的下标为i
• 其父节点下标：i/2向下取整
• 左孩子下标：2i
• 右孩子下标：2i+1

5 最大堆：除根节点以外的每个节点i，有A[PARENT（i）] >= A[i] 最小堆：除根节点意外的每个节点i，有A[PARENT（i）] <= A[i]

---

堆排序

步骤：

1. 建大顶堆
2. 去堆顶元素与当前堆的最后一个元素进行互换。
3. 该堆顶元素已达最终位置，排除出堆
4. 对剩下的堆进行最大堆调整
5. 重复2到4步

排序过程1 建堆过程    1） 从第一个非叶子节点开始，对value为8的节点进行调整，无需调整。    2） 对value值为9的节点进行调整。    3） 对value为2的节点调整 4） 对value为3的节点进行调整   ----》  5） 对value为7的节点进行调整  ---》 建堆完成2 堆顶元素与当前堆的最后一个元素进行互换。3 该堆顶元素已达最终位置，排除出堆4 对剩下的堆进行调整递归进行堆首和堆尾互换以及调整堆的步骤，结果即为排好序的堆。

---

代码实现

// heapsort.hclass HeapSort:public BaseSort {public:    HeapSort（int Array[], int len） : BaseSort（） {        this-&gt;Array = Array;        this-&gt;len = len;    }    void sort（）;private:    /* 建堆 */    void buildMaxHeap（）;     /* 调整堆，以保持最大堆性质 */    void maxHeapIfy（ int i , int curlen）;     /* 堆排序 */    void heapSort（）;     /* 返回父节点下标 */    int Parent（int i） {        if （ i % 2 == 0 ）            return i/2;        else            return i/2 + 1;    };     /* 返回左孩子节点下标 */    int Left（int i） { return 2 * i + 1; };     /* 返回右孩子节点下标 */    int Right（int i） { return 2 * i + 2; };private:    int* Array;    int len;};相关成员函数实现
// heapsort.cpp#include "heapsort.h"void HeapSort::sort（） {    heapSort（）;}void HeapSort::heapSort（） {       buildMaxHeap（）;    int i = this->len;    int tmp;    while（ i > 0 ） {        tmp = this->Array[0];        this->Array[0] = this->Array[i-1];        this->Array[i-1] = tmp;        i--;        maxHeapIfy（0, i）;    }}void HeapSort::maxHeapIfy（ int i, int curlen ） {    int left, right, largest;    int tmp;    left = Left（i）;    right = Right（i）;    if （ left < curlen-1        && Array[left] > Array[i]）        largest = left;    else        largest = i;    if （ right < curlen-1        && Array[right] > Array[largest]）        largest = right;    if （ largest ！= i ） {        tmp = Array[i];        Array[i] = Array[largest];        Array[largest] = tmp;        maxHeapIfy（largest, curlen）;    }}void HeapSort::buildMaxHeap（） {    int i;    for （ i = （len-1）/2 ; i >= 0; i-- ） {        maxHeapIfy（i, len）;        if （DEBUG） {            printArray（this->Array, this->len, "midResult"）;        }    }}测试代码：
/* --------- HeapSort -------- */int b[10] = {7,3,2,9,8,5,1,10,4,6};HeapSort* heapsort = new HeapSort（b, len）;heapsort->sort（）;printArray（b, len, "HeapSort "）;------------------------------分割线------------------------------C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm读C++ Primer 之构造函数陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm读C++ Primer 之智能指针 http://www.linuxidc.com/Linux/2011-08/40177.htm读C++ Primer 之句柄类 http://www.linuxidc.com/Linux/2011-08/40175.htm将C语言梳理一下，分布在以下10个章节中：

1. Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-02/113519.htm