堆排序(heap sort) 详解 及 代码(C++)

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

堆排序包含两个步骤: 

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

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

代码:

/*
 * 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 (std::vector<int>& L, int s, int num)
{
	int temp = L[s-1];
	for (int j=2*s; j<=num; j*=2) {
		if (j<num && L[j-1] > L[j]) //选取最小的结点位置
			++j;
		if (temp < L[j-1]) //不用交换
			break;
		L[s-1] = L[j-1]; //交换值
		s = j; //继续查找
	}
	L[s-1] = temp;
}

void HeapSort (std::vector<int>& L)
{
	int num = L.size();
	for (int i=num/2; i>0; --i) {
		HeapAdjust(L, i, num); //从第二层开始建堆
	}

	for (int i=num; i>1; --i) {
		std::swap(L[0], L[i-1]);
		HeapAdjust(L, 1, i-1); //从顶点开始建堆, 忽略最后一个
	}

	return;
}

int main (void)
{
	std::vector<int> L = {49, 38, 65, 97, 76, 13, 27, 49};
	HeapSort(L);
	for (std::size_t i=0; i<L.size(); ++i) {
		std::cout << L[i] << " ";
	}

	std::cout << std::endl;
	return 0;
}

输出:

97 76 65 49 49 38 27 13