堆排序(heap sort) 具体解释 及 代码(C++)

本文地址: http://blog.csdn.net/caroline_wendy

堆排序包括两个步骤:

第一步: 是建立大顶堆(从大到小排序)或小顶堆(从小到大排序), 从下往上建立; 如建堆时, s是从大到小;

第二步: 是依次交换堆顶和堆底, 并把交换后的堆底输出, 仅仅排列剩余的堆, 从上往下建立; 如构造时, s始终是1;

堆排序(Heap Sort)的时间复杂度是O(nlogn), 最坏情况下也是如此.

而高速排序(Quick Sort), 若初始记录序列有序, 高速排序将退化为起泡排序(Bubble Sort), 时间复杂度是O(n^2).

这是堆排序比高速排序的长处.

代码:

/*

 * main.cpp

 *

 *  Created on: 2014.6.12

 *      Author: Spike

 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>

#include <stack>

#include <queue>

using namespace std;

void HeapAdjust (int data[], int length, int k)

{

	int tmp = data[k];

	int i=2*k+1;

	while (i<length) {

		if (i+1<length && data[i]>data[i+1]) //选取最小的结点位置

			++i;

		if (tmp < data[i]) //不用交换

			break;

		data[k] = data[i]; //交换值

		k = i; //继续查找

		i = 2*k+1;

	}

	data[k] = tmp;

}

void HeapSort (int data[], int length)

{

	if (data == NULL || length <= 0)

		return;

	for (int i=length/2-1; i>=0; --i) {

		HeapAdjust(data, length, i); //从第二层開始建堆

	}

	for (int i=length-1; i>=0; --i) {

		std::swap(data[0], data[i]);

		HeapAdjust(data, i, 0); //从顶点開始建堆, 忽略最后一个

	}

	return;

}

int main (void)

{

	int data[] = {49, 38, 65, 97, 76, 13, 27, 49};

	int length = 8;

	HeapSort(data, length);

	for (int i=0; i<length; ++i) {

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

	}

	std::cout << std::endl;

	return 0;

}

输出:

97 76 65 49 49 38 27 13