堆排序

通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆，

取出次大值或者次小值，如此反复执行就可以得到一个有序序列，此过程为堆排序。

思路：

1.创建一个堆 H[0……n-1]；

2.把堆首（最大值）和堆尾互换；

3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

4.重复步骤 2，直到堆的尺寸为 1。

代码实现：

#include <iostream>

#include <random>

using namespace std;

template <typename T> //整數或浮點數皆可使用

void max_heapify(T* 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++;

		if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數

			return;

		else { // 否則交換父子內容再繼續子節點和孫節點比較

			swap(arr[dad], arr[son]);

			dad = son;

			son = dad * 2 + 1;

		}

	}

}

template <typename T> //整數或浮點數皆可使用

void heap_sort(T* arr, int len) {

	// 初始化，i從最後一個父節點開始調整

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

		max_heapify(arr, i, len - 1);

	// 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢

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

		swap(arr[0], arr[i]);

		max_heapify(arr, 0, i - 1);

	}

}

int main()

{

	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };

	int len = (int) sizeof(arr) / sizeof(*arr);

	heap_sort(arr,len);

	for (int i = 0; i < len; i++)

		cout << arr[i] << ' ';

	cout << endl;

	double arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };

	len = (int) sizeof(arrf) / sizeof(*arrf);

	heap_sort(arrf,len);

	for (int i = 0; i < len; i++)

		cout << arrf[i] << ' ' << endl;

	return 0;

}

巴特西

十大经典排序之堆排序（C++实现）

堆排序

最新文章

热门文章