算法之堆排序学习
堆排序算法重新学习。
选择排序,每一趟从未排序序列中选择出最小元素,将元素放到已排序序列尾部。
选择排序算法有以下几种:
- 直接选择排序
- 堆排序
堆排序算法
堆排序则是利用堆这种数据结构进行排序。需要先了解下堆的定义。
堆
堆是一个完全二叉树,每个结点的值都大于等于(或者小于等于)其左右子结点的值。
堆分为大顶堆和小顶堆,大顶堆是每个结点的值都大于等于左右子结点的值,也就是堆顶是最大值。小顶堆是每个节点值都小于等于左右结点的值,也就是堆顶是最小值。一般排序如果是按照从大到小排序(降序)可以使用小顶堆;如果是按照从小到大排序(升序)可以使用大顶堆。
堆可以使用数组来表示,映射到数组后假设数组中索引i为当前结点,则有如下:
- 左子结点为:2i + 1
- 右子结点为:2i + 2
- 父结点为:(i - 1) / 2
- 最后一个非叶子结点为:array.length / 2 - 1
堆排序算法描述
堆排序算法(升序,大顶堆)描述如下:
- 将无序序列构造成大顶堆
- 将堆顶元素和未排序序列最后一个元素进行交换
- 调整大顶堆,继续2、3步骤
堆排序代码示例
/**
* 堆排序
* 1. 将无序序列构造成大顶堆
* 2. 将堆顶元素和未排序序列最后一个元素进行交换
* 3. 调整未排序序列的大顶堆后,继循环2、3步
*
* 结点索引为i,则左子结点索引为2i + 1,右子结点索引为2i + 2,
* 父节点索引为(i - 1) / 2
* 最后一个非叶结点索引为:(array.length / 2) - 1
* @param source
*/
public void heapSort(Integer[] source) {
// 构造大顶堆,从最后一个非叶结点开始
for (int i = (source.length >> 1) - 1; i >= 0; i--) {
adjustHeap(source, i, source.length - 1);
}
for (int i = source.length - 1; i > 0; i--) {
// 交换堆顶和最后一个元素
swap(source, 0, i);
// 调整剩余未排序序列的大顶堆
adjustHeap(source, 0, i - 1);
}
}
/**
* 以start为根的子树调整成大顶堆
* @param source
* @param start
* @param end
*/
private void adjustHeap(Integer[] source, int start, int end) {
Integer temp = source[start];
// 从当前元素的左子结点开始遍历
for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) {
// 如果左子结点比右子结点小,则将i指向右子结点
if (i + 1 <= end && source[i] < source[i + 1]) {
i++;
}
// 到这里i指向左右子结点中大的那个结点
// 比较大的结点和父结点进行比较,如果比父结点大,需要放到父结点位置上去
if (source[i] > temp) {
// 比父结点大的元素,放到父结点位置上
source[start] = source[i];
start = i;
} else {
break;
}
}
// 遍历完后,将temp元素放到最终位置
source[start] = temp;
}
private void swap(Integer[] source, int i, int j) {
Integer temp = source[i];
source[i] = source[j];
source[j] = temp;
}
public static void main(String[] args) {
Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
System.out.println("before: " + Arrays.asList(array));
new HeapSort().heapSort(array);
System.out.println("after: " + Arrays.asList(array));
}
堆排序算法分析
时间复杂度
- 时间复杂度为$O(nlog_{2}n)$
空间复杂度
空间复杂度为O(1)
算法的稳定性
堆排序算法是不稳定的。
适用场景
- 数据较多的时候,可以使用堆排序,堆排序所需的辅助空间少于快排。
参考内容
- 《数据结构(Java版)》