快捷導(dǎo)航

c++實(shí)現(xiàn)堆排序的示例代碼

更新時(shí)間：2023年02月02日 09:05:49 作者：吳天德少俠

本文主要介紹了c++實(shí)現(xiàn)堆排序的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

看了一下優(yōu)先隊(duì)列，查了一下堆排序。堆排序主要就是建最大堆（最小堆）和交換2個(gè)操作。如果建的是最大堆，那么交換的時(shí)候，父節(jié)點(diǎn)就和最大的子節(jié)點(diǎn)比較，如果它比最大的子節(jié)點(diǎn)還大，那就不用比了。因?yàn)楹竺孢€有一個(gè)交換的操作，所以最后得到的就是由小到大的排序；反之，得到的就是由大到小的排序。

#include<iostream>
#include<algorithm>
using namespace std;

void maxHeapify(int arr[], int start, int end)
{
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) {
		if (son + 1 <= end && arr[son] < arr[son + 1]) {
			son++;// 找出最大的兒子
		}
		// 父節(jié)點(diǎn)跟最大的子節(jié)點(diǎn)比較即可
		if (arr[dad] > arr[son]) {
			return;
		}
		else {
			// 交換父節(jié)點(diǎn)與子節(jié)點(diǎn)
			swap<int>(arr[dad], arr[son]);
			// 這個(gè)時(shí)候父節(jié)點(diǎn)位置滿(mǎn)足要求了，下面的子節(jié)點(diǎn)不一定滿(mǎn)足要求
			// 還需要檢查有沒(méi)有導(dǎo)致下面的子節(jié)點(diǎn)受到影響
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heapSort(int arr[], int len)
{
	// 初始化，從最后一個(gè)父節(jié)點(diǎn)開(kāi)始，調(diào)整所有的父節(jié)點(diǎn)
	for (int i = len / 2 - 1; i >= 0; i--) {
		maxHeapify(arr, i, len - 1);
	}
	// 這個(gè)時(shí)候找到了最大元素（堆頂），
	// 將其和最后一個(gè)元素交換。(這樣就會(huì)得到由小到大的排序)	
	for (int i = len - 1; i > 0; i--) {
		swap(arr[0], arr[i]);
		// 將交換之后除了最后一個(gè)元素的所有元素，重新調(diào)整為最大堆
		maxHeapify(arr, 0, i - 1);
	}
}

int main()
{
	int arr[]{ 5,3,4,9,7,8,1,2,10,23,15 };
	int len = int(sizeof(arr) / sizeof(*arr));
	heapSort(arr, len);
	cout << "排序之后:" << endl;
	for (auto item : arr) {
		cout << item << " ";
	}

	return 0;
}

在這里插入圖片描述