堆排序
前言
堆排序（HeapSort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似于完全二叉树的结构，同时满足子节点的键值总是小于（或者大于）其父节点。
每个节点的值都大于或者等于其左右子节点的值，称为大顶堆；或者每个节点的值都小于或者等于其左右子节点的值，称为小顶堆。
对堆中的节点按层进行编号，将这种逻辑结构映射到数组如下图所示：
该数组从逻辑上讲就是一个堆结构，并且有以下特点：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
综上，堆排序的基本思想就是将待排序的序列构建成一个大顶堆，此时整个序列最大值就是堆顶的根节点。将其与末尾元素交换，此时末尾元素就成为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素中的次小值，也就是n-1个元素中的最大值，并将其放置末尾，并如此反复，就能得到一个有序序列。
实现步骤
步骤一：构造初始堆，将给定无序序列构造成一个大顶堆
假定无序序列结构如下
此时从最后一个非叶子节点[6]开始，叶结点不用调整，从左至右，从上至下进行调整。
找到第二个非叶子节点[4]，由于{4，8，9}中9元素最大，4和9交换。
此时，交换导致了子树{4，5，6}结构混乱，继续调整，现在6元素最大，交换4和6
步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，如此反复重建和交换。
将堆顶元素9和末尾元素4进行交换
重新调整结构，使其继续满足堆定义
再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
后续过程，继续进行调整，交换，如此反复调整，最终即可整个序列有序。
堆排序算法的基本思路总结：
- 将无序序列建成一个堆，根据升降序需求选择大顶堆和小顶堆。
- 将堆顶元素与末尾元素交换，将最大元素沉到数组末端。
- 重新调整，使其重新满足堆定义，然后继续交换堆顶元素和当前末尾元素，反复执行调整和交换，直至整个序列有序。
代码实现
public static void heapSort(int[] array)
{
//从倒数第一个非叶子节点开始
for (int i = array.length/2 - 1; i>=0; i--)
{
//从第一天非叶子节点从下至上，从左至右调整结构
adjustHeap(array,i, array.length);
}
//将堆顶元素与末尾元素交换 将最大元素沉到数组末尾 + 重新调整堆结构
for (int i = array.length - 1; i > 0 ; i--)
{
//交换堆顶元素和末尾元素
swap(array,0,i);
//交换后的末尾元素忽略(j--) 不再参与堆结构的调整
//重新调整堆结构
adjustHeap(array,0,i);
}
}
private static void swap(int[] array, int start, int end)
{
int temp = array[start];
array[start] = array[end];
array[end] = temp;
}
public static void adjustHeap(int[] array,int index,int length)
{
//取出当前元素
int temp = array[index];
//i节点是index节点的左子节点
for (int i = 2 * index + 1; i < length; i = 2 * i + 1)
{
//表明左子节点小于右子节点
if (i+1 < length && array[i] < array[i+1])
{
//将指针移至较大节点
i++;
}
//如果子节点大于父节点
if (array[i] > temp)
{
//将较大值赋给当前节点
array[index] = array[i];
//指针移向子节点
index = i;
}
else
{
break;
}
}
//循环结束，已经将最大值放在了堆顶
//将temp值放到最终的位置
array[index] = temp;
}
public static void main(String[] args)
{
//升序
int[] array = {4,6,8,78,13,19,1,5,9,};
System.out.println("排序前=>"+ Arrays.toString(array));
heapSort(array);
System.out.println("排序后=>"+Arrays.toString(array));
}
输出结果
排序前=>[4, 6, 8, 78, 13, 19, 1, 5, 9]
排序后=>[1, 4, 5, 6, 8, 9, 13, 19, 78]
以上。
如有不足或错误欢迎评论指正。