一、简介
在了解堆排序之前，首先要知道堆是一种什么样的数据结构。
1.1 堆的概念
堆是一种二叉树结构，可以分为大顶堆和小顶堆，而堆排序就是基于该种结构的特性产生的排序算法。
大顶堆
小顶堆
数组存储特性
1.2 排序思想
排序思想
/**
* 维护堆的性质(大顶堆)
*
* @param arrays 数组
* @param n 数组长度
* @param i 待维护节点的下标
*/
private static void heapify(int[] arrays, int n, int i) {
// 父节点
int largest = i;
// 二叉树左右孩子节点
int lSon = largest * 2 + 1;
int rSon = largest * 2 + 2;
if (lSon < n && arrays[largest] < arrays[lSon]) {
largest = lSon;
}
if (rSon < n && arrays[largest] < arrays[rSon]) {
largest = rSon;
}
if (largest != i) {
ArraysUtils.swap(arrays, largest, i);
// 继续向下递归维护堆的性质
heapify(arrays, n, largest);
}
}
/**
* 堆排序入口
*
* @param arrays
* @param n
*/
public static void heapSort(int[] arrays, int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arrays, n, i);
}
for (int i = n - 1; i > 0; i--) {
ArraysUtils.swap(arrays, i, 0);
heapify(arrays, i, 0);
}
}
排序示例
