详解堆排序_堆排序的最坏时间复杂度

堆排序详解

算法性能分析

堆排序最坏情况下、最好情况下以及平均情况下的时间复杂度均为为O(NlogN)，空间复杂度是O(1).

堆排序的排序方式为内排序（In-place）,顾名思义，内排序即所有的排序操作都在内存中完成，只是占用常数级内存，而不占用额外内存。

堆排序是不稳定的排序算法，当存在相同的元素时，不能保证先后顺序不变。

预备知识

其实每个算法都有其核心逻辑，比如快速排序的核心就是Partition()函数，即基于某个元素分区。比如归并排序的核心就是MergeTwoArray()函数，即合并两个有序的数组。

那么堆排序的核心逻辑呢？它就是Heap_Adjust()函数，也可以称他为渗透调整函数，整个堆排序的过程中主要用它两次。第一次是依据原始无序序列构建大顶堆（升序）或者小顶堆（降序）。第二次是将堆顶的元素跟末尾的元素交换，交换后要调用它再次构建大顶堆或者小顶堆。

还需要知道的关于堆的几个特性：

1.堆首先是一颗完全二叉树。

2.大顶堆，小顶堆不再赘述。

3.最后一个非叶节点在哪里？怎么求？

       一个公式LastRoot = length/2-1,在这里length是数组长度，LastRoot即为最后一个非叶节点。从最小的小堆开始排序！

4.堆中的节点映射在数组中有什么特点？

        大顶堆（i即数组下标）：array[i] >= array[2i+1] && array[i] >= array[2i+2]

        小顶堆：array[i] <= array[2i+1] && array[i] <= array[2i+2]

        可以这样解释，i元素在堆中的两个子节点为2i+1和2i+2.

基本思想及步骤

基本思想：

将要排序的n个元素的序列构造成一个大顶堆，最大值即根节点。根节点与末尾元素交换，再次操作剩下的n-1个元素，重新构造堆，这便得到n个元素的次大值。反复执行，便得到有序序列。

步骤：

1.构造初始堆（即将要排序的n个元素的序列构造成一个大顶堆）

          a.按顺序放好，放在堆的指定位置。

          b.开始调整，从最后一个非叶节点开始调整（前面已给出怎么求）。从右到左，从下到上依次调整非叶节点的小堆。

              有人会问，如何调整？这就涉及到了核心逻辑函数，Heap_Adjust(int *list，int roots,int length)函数。暂时不提，后面详解。

2.将堆顶元素与末尾元素交换后，调整剩下的n-1个元素，一直重复此步骤。即可。

          a.交换堆顶元素和末尾元素，swap(a,b)

          b.调用Heap_Adjust(int *list,int roots,int length)函数，调整即可。

核心解读

重头戏，渗透调整函数解读，该函数有三个参数，数组，初始调整的root，要调整的数组长度。经过该函数调整后，响应的堆会变成期望的大顶堆或者小顶堆！

Heap_Adjust(int* list,int roots,int length){     //length为还需要调整的长度

         int temp = list[roots];                    //把要调整的小堆的root放入temp暂存

         for(int j = 2*roots+1;j<=length;j=j*2+1) {                   //j=j*2+1，如果它的子节点非叶节点，就向下渗透！！！

                  if(list[j]<list[j+1]&&j<length){j++;}                     //第一个子节点比第二个子节点小，指针移向第二个子节点

                  if(temp>list[j]){break;}                                      //root比第二个子节点还大的话，说明次堆不用调整，break

                  list[roots] = list[j];                                             //运行到这里说明需要交换，roots这个位置放入j的值

                  roots = j;                                                          //roots也换成j

         }

         list[roots] = temp;                                                      //根节点换到原来的子节点的位置

}

次要核心，堆排序的上层两步，1.建堆。2.交换调整。该函数调用两次Heap_Adjust()函数。如前面的步骤，代码实现

void Heap_Sort(int* list,int length) {
   //步骤一   

 int LastRoot = length  / 2 -1 ;                                                  //第一个非叶节点
    for (LastRoot = length / 2 - 1; LastRoot >= 0; LastRoot--) {    //依次调整
        Heap_adjust(list, LastRoot, length - 1);
    }

//步骤二
    for (int i = length - 1; i >= 1; i--) {
        swap(list[i], list[0]);                                                             //交换堆顶和末尾
        Heap_adjust(list, 0, i - 1);                                                  //调整
    }
}

完整代码

#include <iostream>
using namespace std;
 
void swap(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}
 
void Heap_adjust(int* list,int roots,int Size) {
	int temp = list[roots];
	for (int j = roots * 2 + 1; j <= Size; j = j * 2 + 1) {
		if (list[j] < list[j + 1] && j < Size) {
			j++;
		}
		if (temp > list[j]) {
			break;
		}
		list[roots] = list[j];
		roots = j;
	}
	list[roots] = temp;
}
 
void Heap_Sort(int* list,int length) {
	int LastRoot = length  / 2 -1 ;
	for (LastRoot = length / 2 - 1; LastRoot >= 0; LastRoot--) {
		Heap_adjust(list, LastRoot, length - 1);
	}
	for (int i = length - 1; i >= 1; i--) {
		swap(list[i], list[0]);
		Heap_adjust(list, 0, i - 1);
	}
}
 
 
 
int main()
{
    std::cout << "Hello World!\n"; 
#define N 10
	int A[N] = { 21,32,4,32,65,2,43,44,33,22 };
	cout << "The origin list is:" << endl;
	for (int i = 0; i < N; i++) {
		cout << A[i] << " ";
	}
	Heap_Sort(A, 10);
	cout << endl << "After Sort:" << endl;
	for (int i = 0; i < N; i++) {
		cout << A[i] << " ";
	}
#undef N
	return 0;
}

总结

其实，堆排序也不是很难，理解后还是挺简单的，而且个人觉得堆排序确实是排序界的当仁不让的老大！虽然也有缺点，比如说虽然最坏情况下比快排时间复杂度优越，但是由于对数组操作都是N到N/2之间操作，那么在大的数组的情况下，cpu的缓存利用率并不高，所以速度没有快排快。

熟练掌握了堆排序，在排序问题上，其实会有很大的帮助。快排，归并，希尔排序后面会补上。