“堆”排序

如果还没有了解过什么是“堆”的话，那可以转移到数据结构专栏有关堆的那一篇文章，那里详细介绍了堆的各种性质，这里就默认大家已经了解“堆”这个数据结构了。

在这里呢我要分享一个效率非常高的排序方法，“堆排序”，它的时间复杂度能够达到惊人的 O(N*logN) ,这比冒泡排序的 O(N^2) 可要高效了不少的，你试想一下，如果N是一百万，那么（N*logN）就是两千万，但是（N^2）可是“一万亿”啊！！！这个差距是什么概念！所以堆排序的效率可要比冒泡排序的效率高得太多了。

那么这个堆排序是怎样的呢？能够达到这种效率，接下来我们就一探究竟。

给定你一个数组，想要进行堆排序首先得先建堆，那如果是要排升序的话，我们需要建小堆还是建大堆呢？？思考5秒钟，你可能会想，这还用说吗？升序肯定是建小堆啊，小堆从上到下不就是升序吗，但是事实真的是这样吗？

你试想一下，如果建小堆，也就意味着你的堆顶的数就是最小的，这个数就不用再动了，但是如果后面的数你需要选出次小的数放到第二个位置，那么你就需要忽略第一个数，以第二个数开始的后面的所有数看作是一个堆，然后调整找到次小的数放到第二个位置，但是以第二个数看作是堆顶的话，那么从第二个数开始的后面的数就不再是一个小堆了，那要选次小的数的话就需要重新建一个小堆，那代价太大了，还不如遍历一遍找到最小的数呢！所以排升序建小堆的话是不可取的。

“堆”排序

那么大佬就想，排升序建小堆不行，那我就建大堆，这个大堆的堆顶就是这棵树中最大的，然后和堆的删除走同样的思路，“替换法”。用堆顶的元素和最后一个元素交换，那么堆顶的元素就来到了最后的位置，也就是升序之后的最大的数的位置，并且这里没有影响这棵树本来的性质（各节点之间的关系），然后不把这个最后的数看作是这个大堆里面的数，这时再对堆顶的数（交换上来的数）走一遍向下调整，原来的堆中的次大的数就选出来了，以此类推，就能完成对这个数组的排序了。这真是一个很绝的想法。不愧是大佬。

这里建大堆用向下调整的方法为妙，向下调整建堆的方法请参考博主的数据结构专栏的二叉树（堆）二叉树（堆）_KOBE 0824 BRYANT的博客-CSDN博客这一篇文章，里面有详细过程。

#include <stdio.h>
#include <assert.h>

void swap(int* a, int* b)
{
	assert(a && b);
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustDown(int* a, int parent, int n)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child+1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int arr[] = { 123,63,54,36,87,963,1254 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int parent = 0;
	
	//建堆的时间复杂度是: O(N)
	for (parent = (sz - 1 - 1) / 2; parent >= 0; parent--)
	{
		AdjustDown(arr, parent, sz);
	}

	//替换法排序的时间复杂度是: O(N*logN)
	int end = sz;
	while (end--)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
	}

	//所以堆排序的时间复杂度是:O(N+N*logN)=O(N*logN)

	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

在原数组向下调整建大堆的时间复杂度为 O(N)；证明如下：

“堆”排序

替换法排序的时间复杂度是: O(N*logN)；所以整体堆排序的时间复杂度为：O(N*logN)；

证明如下：

“堆”排序

以上就是传说中的非常牛的堆排序啦！效率极高的哦，你学会了吗？如果感觉到有所收获的话，那就动动你发财的小手点亮一下小心心，顺便关注一下博主呗！后期会持续出各种排序的方法哦，关注博主不迷路！！！

相关文章