算法笔记--堆排序


堆排序也是一种选择排序,对序列的原始顺序不敏感,适用于数据量大的情况。


1. 算法思想

          堆:子节点的值总是小于/大于它的父节点。这里使用的是最大堆。

          将数组转化为最大堆,依次将对顶元素取出,与堆中最后一个元素交换,堆长度减一,对堆作调整;如此循环至堆为空,最后得到一个元素由小到大排列的数组。

2. 时间复杂度

          最好情况 O(nlogn):初始化建堆复杂度O(n)(建堆过程中每个元素最多比较2次,平均交换1次);每次弹出后调整时间O(logn),弹出n-1次

          最坏情况 O(nlogn):数据顺序对排序效率无影响

3. 空间复杂度 O(1)

          就地排序,辅助空间为常数级

4. 稳定性

          不稳定。存在不相邻交换

5. 代码实现(C语言)

          首先是针对给定位置元素调整堆的代码,在堆化和排序过程中都要调用:

void ShiftDown(int *A, int pos, int len)
{
	int i, maxInd, tmp;

	i = pos;

	while (i <= (len - 2) / 2)
	{
		maxInd = i;

		if ((i * 2 + 1) < len && A[maxInd] < A[i * 2 + 1])
		{
			maxInd = i * 2 + 1;
		}
		if ((i * 2 + 2) < len && A[maxInd] < A[i * 2 + 2])
		{
			maxInd = i * 2 + 2;
		}

		if (maxInd != i)
		{
			tmp = A[i];
			A[i] = A[maxInd];
			A[maxInd] = tmp;
			i = maxInd;
		}
		else
		{
			break;
		}
	}
}
          然后是数组初始化(堆化)的代码:

void Heapfy(int *A, int n)
{
	int i;

	for (i = (n - 2) / 2; i >= 0; --i)
	{
		ShiftDown(A, i, n);
	}
}
          最后是堆排序的过程:

void HeapSort(int *A, int n)
{
	int i;
	int tmp;

	Heapfy(A, n);

	for (i = n - 1; i > 0; --i)
	{
		tmp = A[0];
		A[0] = A[i];
		A[i] = tmp;

		ShiftDown(A, 0, i);
	}
}


上一篇:运营商的ISIS协议使用


下一篇:《Photoshop图像合成专业技法(修订版)》—第1章1.1节你最好的朋友:“快速选择工具”和“调整边缘”