堆排序算法
什么是堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
完全二叉树
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点。
为了便于理解，可以对节点按照从上往下，从左至右的顺序编号，与广度优先遍历的顺序是一样的。
堆的性质
对于第i个非叶子节点，它的左右节点的下标序号是2i+1和2i+2；
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ；
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] ；
第一个非叶子节点的下标序号是length / 2 - 1。
堆排序的思想
假设要从小到大排序，可以依次找到最大，第二大的数...。将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。举个例子：
第一步：构建最大堆
1. 这个初始的序列：4,6,8,5,9
2. 从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
3. 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
4. 交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
第二步：取出最大值
将堆顶元素与最后一个元素交换，得到了最大值。
如果需要从小到大排序，就需要构建最大堆，否则构建最小堆；堆排序的过程（这里从小到大排序）就是
1. 构建堆；
2. 交换堆顶与堆尾元素，找到该堆中最大值；
3. 重复1，2步骤 n - 1 次，即可完成排序。
代码实现
堆排序主要是把构建堆，交换堆顶与堆尾元素这两个过程重复n-1次即可，第i次构建堆的时间复杂度是log(n-1-i)，堆排序时间复杂度近似为O(nlogn)。
1. java代码
public class HeapSort {
// 堆排序
public static void main(String[] args)
{
int[] a = {5, 4, 1, 2, 6, 3, 7, 9, 8 };
int arrayLength = a.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++)
{
// 建堆
buildMaxHeap(a, arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(a, 0, arrayLength - 1 - i);
System.out.println("交换后：" + Arrays.toString(a));
}
}
// 对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex)
{
// 从lastIndex处节点（最后一个节点）的父节点开始(在构造有序堆时，我们开始只需要扫描一半的元素（n/2-1 ~ 0）即可，为什么? 因为(n/2-1)~0的节点才有子节点)
for (int i = (lastIndex - 1) / 2; i >= 0; i--)
{
// k保存正在判断的节点
int k = i;
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if (biggerIndex < lastIndex)
{
// 若果右子节点的值较大
if (data[biggerIndex] < data[biggerIndex + 1])
{
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大的子节点的值
if (data[k] < data[biggerIndex])
{
// 交换他们
swap(data, k, biggerIndex);
}
}
}
// 交换
private static void swap(int[] data, int i, int j)
{
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
交换后：[8, 5, 7, 4, 6, 3, 1, 2, 9]
交换后：[2, 6, 7, 4, 5, 3, 1, 8, 9]
交换后：[1, 6, 2, 4, 5, 3, 7, 8, 9]
交换后：[2, 1, 3, 4, 5, 6, 7, 8, 9]
交换后：[1, 2, 3, 4, 5, 6, 7, 8, 9]
交换后：[2, 1, 3, 4, 5, 6, 7, 8, 9]
交换后：[2, 1, 3, 4, 5, 6, 7, 8, 9]
交换后：[1, 2, 3, 4, 5, 6, 7, 8, 9]
2. Python代码
def heap_sort(arr):
length = len(arr)
# 循环 n - 1次
for i in range(length - 1):
print('第%s次构建堆' % (i),arr)
# 建堆
build_heap(arr, length - 1 - i)
# 交换堆顶和"最后"一个元素
arr[0],arr[length - 1 - i] = arr[length - 1 - i], arr[0]
print('交换后',arr)
def build_heap(arr, last):
# 长度为last的堆，最后一个非叶子节点下标索引是(last - 1) / 2
last_node = int((last - 1)/2)
# range(4,-1,-1) 表示 [4,3,2,1,0]
for i in list(range(last_node, -1, -1)):
k = i
# 左节点下标
left = 2*i + 1
# left < last表命有右子节点，left存储的是左右节点中较大数的下标索引
if left < last and arr[left] < arr[left + 1]:
left = left + 1
# 子节点比父节点大，交换
if arr[i] < arr[left]:
# 交换位置，把大数放在上面，小数放在子节点
arr[i],arr[left] = arr[left],arr[i]
最后总结
堆排序通过n-1次构建堆与交换得到最值，得到最终的排序结果。构建堆是从最后一个非叶子节点开始，将较大值升到该节点，逐步左移，到根节点为止，完成一个堆的构建，第一次得到最大值；第二次就是n-1个元素构建堆，选出第二大的值，直到n-1次完成，即可完成排序，时间复杂度为O(nlogn)。
点击【阅读原文】访问Github代码地址。
猜你可能喜欢