排序算法(2) 堆排序 C++实现

2 可以视为一棵完全二叉树

3 一个堆可以被看作一棵二叉树和一个数组,如下图所示:

clipboard

4 下标计算(通常使用内联函数或者宏来定义下标操作):

已知某个结点的下标为i

其父节点下标:i/2向下取整

左孩子下标:2i

右孩子下标:2i+1

5 最大堆:除根节点以外的每个节点i,有A[PARENT(i)] >= A[i]

最小堆:除根节点意外的每个节点i,有A[PARENT(i)] <= A[i]

堆排序

步骤:

建大顶堆

去堆顶元素与当前堆的最后一个元素进行互换。

该堆顶元素已达最终位置,排除出堆

对剩下的堆进行最大堆调整

重复2到4步

排序过程

clipboard[1]

1 建堆过程

clipboard[2]

1) 从第一个非叶子节点开始,对value为8的节点进行调整,无需调整。

    2) 对value值为9的节点进行调整。

clipboard[3]

3) 对value为2的节点调整

clipboard[4]

4) 对value为3的节点进行调整

clipboard[5]

    ----》

clipboard[6]

5) 对value为7的节点进行调整

clipboard[7]

  ---》

clipboard[8]

建堆完成

clipboard[9]

2 堆顶元素与当前堆的最后一个元素进行互换。

3 该堆顶元素已达最终位置,排除出堆

clipboard[10]

4 对剩下的堆进行调整

clipboard[11]

递归进行堆首和堆尾互换以及调整堆的步骤,结果即为排好序的堆。

clipboard[12]

代码实现


// heapsort.h

class 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+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

C语言梳理一下,分布在以下10个章节中:

Linux-C成长之路(一):Linux下C编程概要

Linux-C成长之路(二):基本数据类型

Linux-C成长之路(三):基本IO函数操作

Linux-C成长之路(四):运算符

Linux-C成长之路(五):控制流

Linux-C成长之路(六):函数要义

Linux-C成长之路(七):数组与指针

Linux-C成长之路(八):存储类,动态内存

Linux-C成长之路(九):复合数据类型

Linux-C成长之路(十):其他高级议题

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/c5aa56528fa4abf1b948dc8f67aabab1.html