本文共 1132 字，大约阅读时间需要 3 分钟。

1.堆排序的算法思想

• 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。

2.简单总结下堆排序的基本思路：

a.将无序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆(注意：实现升序需要建大堆，实现降序需要建小堆）;

b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

• 以升序为例基本代码实现如下：

void AdjustDown(int* arr,int root,int count){
   	int parent = root;	int child = parent * 2 + 1;	while (child <= count - 1)	{
   		//向下调整算法有一个前提：左右子树必须是一个堆，才能调整。		if (child +1 <= count -1 && arr[child + 1] > arr[child])//注意：child +1 <= count -1		{
   			child++;		}		//选出较大的那个孩子		if (arr[child] > arr[parent])		{
   			swap(arr[child], arr[parent]);			parent = child;			child = parent * 2 + 1;		}//如果孩子大于父亲，则交换		else		{
   			break;		}	}}void HeapSort(int* arr, int count){
   	//排序之前先建堆，升序要建大堆	for (int i = (count - 1 - 1) / 2; i >= 0; i--)	{
   		AdjustDown(arr, i, count);	}	int num = count - 1;	while (num)	{
   		swap(arr[0], arr[num]);		AdjustDown(arr, 0, num);		--num;	}}

2.快速排序的特性总结

• 时间复杂度分析

  ①：最优情况下时间复杂度：O( nlogn ).

  ②：最差情况下时间复杂度：O( nlogn ).

• 空间复杂度分析

  堆排序空间复杂度为：O( 1 ).

• 稳定性分析

  堆排序是一种不稳定的排序。

3.堆排序详细图解

• 最后分享一个我在其他博客上看到的堆排序的详细图解的链接：https://www.cnblogs.com/chengxiao/p/6129630.html