數據結構 - 堆排序(heap sort) 詳解 及 代碼(C++)

堆排序(heap sort) 詳解 及 代碼(C++)

堆排序包含兩個步驟:

第一步: 是建立大頂堆(從大到小排序)或小頂堆(從小到大排序), 從下往上建立; 如建堆時, 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 
#include 
#include 

using namespace std;

void HeapAdjust (std::vector& L, int s, int num)
{
	int temp = L[s-1];
	for (int j=2*s; j<=num; j*=2) {
		if (j 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& 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 L = {49, 38, 65, 97, 76, 13, 27, 49};
	HeapSort(L);
	for (std::size_t i=0; i
 
輸出:
 
97 76 65 49 49 38 27 13