堆排序

2018-06-18

堆排序（ Heap Sort )

堆排序要用到堆，那什么是堆呢？可以参考我的一博客什么是堆？

名词解释：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法。

算法分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
平均性能：O(N*logN)

其他性能:由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)。
堆排序是不稳定的排序方法（当数组中有相等元素时，堆排序算法对这些元素的处理方法不止一种）。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化）。

一般步骤

1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆（升序）或小顶堆（降序）。
2.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端。
3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

将堆化为数组：
这里写图片描述

具体实现

代码：

void adjust(int arr[], int len, int index)//调整
{
	int left = 2 * index + 1;
	int right = 2 * index + 2;
	int maxIdx = index;
	if (left<len && arr[left] > arr[maxIdx]) maxIdx = left;
	if (right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
	if (maxIdx != index)                 // 如果maxidx被更新
	{
		swap(arr[maxIdx], arr[index]);//交换
		adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
	}

}
void heapSort(int arr[], int size)//堆排序
{
	for (int i = size / 2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
	{
		adjust(arr, size, i);
	}
	for (int i = size - 1; i >= 1; i--)
	{
		swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
		adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
	}
}

int main()
{
	int array[8] = { 5, 1, 6, 3, 8, 4, 7, 10 };
	heapSort(array, 8);
	/*for (auto it: array)
	{
		cout << it;
	}*/
	for (int i = 0; i <sizeof(array)/sizeof(array[0]); i++)
	{
		cout << array[i] <<" ";
	}
	return 0;
}

结果

这里写图片描述

本文总阅读量次