堆排序 - QXSoftware

堆排序利用堆的性质进行排序。堆分为大顶堆和小顶堆。以升序排序为例，堆排序的思路如下：

首先构造一个大顶堆
然后把堆顶取出，和序列最后的元素交换，然后对前面 n - 1 个元素执行堆化操作
如此往复，直到全部有序

堆排序的时间复杂度是 O(nlogn)，空间复杂度是 O(1)。

下面是 C 语言的实现：

#include <stdio.h>

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

static void sift_down(int *arr, int iBegin, int iEnd)
{
	int i = iBegin;
	int j;
	int k = arr[i];
	for(j = 2 * i + 1; j < iEnd; j = 2 * j + 1)
	{
		if(j + 1 < iEnd && arr[j + 1] > arr[j]) ++j;
		if(k >= arr[j]) break;
		arr[i] = arr[j];
		i = j;
	}
	arr[i] = k;
}

static void heapify(int *arr, int len)
{
	int i;
	for(i = len / 2 - 1; i > -1; i--)
		sift_down(arr, i, len);
}

static void heap_sort(int *arr, int len)
{
	int i;
	heapify(arr, len);
	for(i = len - 1; i > -1; i--)
	{
		swap(&arr[0], &arr[i]);
		sift_down(arr, 0, i - 1);
	}
}

int main()
{
	const int LEN = 10;
	int data[] = {2,3,1,45,32,6,7,8,-6,9};
	int i;

	printf("Before:\n");
	for(i = 0; i < LEN; i++)
		printf("%d ", data[i]);
	printf("\n");

	heap_sort(data, LEN);

	printf("After:\n");
	for(i = 0; i < LEN; i++)
		printf("%d ", data[i]);
	printf("\n");

	return 0;
}

参考资料：

Heap sort

转载请注明出处：

This work is licensed under a MIT License.