十大经典排序算法(动态演示+代码)-堆排序

堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。

算法思想

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无序区

2. 将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]

3. 由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。

代码

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

// 堆排序最大堆有序区。从堆顶把根卸出来放在有序区之前再恢复堆。

void max_heapify(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++;
		if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成直接跳出函数
			return;
		else { //否则交换父子內容再继续子节点与孙节点比較
			swap(arr[dad], arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heap_sort(int 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[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
	int len = (int) sizeof(arr) / sizeof(*arr);
	heap_sort(arr, len);
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
	return 0;
}

排序思想

1.首先将待排序的数组构造成一个大根堆此时整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换此时末尾的数为最大值剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆再将顶端数与n-1位置的数交换如此反复执行便能得到有序数组

首先我们给定一个无序的序列将其看做一个堆结构一个没有规则的二叉树将序列里的值按照从上往下从左到右依次填充到二叉树中。

 对于一个完全二叉树在填满的情况下非叶子节点都有两个子节点每一层的元素个数是上一层的二倍根节点数量是1所以最后一层的节点数量一定是之前所有层节点总数+1所以我们能找到最后一层的第一个节点的索引即节点总数/2根节点索引为0这也就是第一个叶子节点所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢这个计算方式仍然适用当我们从上往下从左往右填充二叉树的过程中第一个叶子节点一定是序列长度/2所以第最后一个非叶子节点的索引就是 arr.len / 2 -1对于此图数组长度为5最后一个非叶子节点为5/2-1=1即为6这个节点

那么如何构建呢 我们找到了最后一个非叶子节点即元素值为6的节点比较它的左右节点中最大的一个的值是否比他大如果大就交换位置。

在这里5小于6,而9大于6则交换6和9的位置。