排序算法(5)----堆排序

这篇博客从以下几个方面来说:

1. 什么是最大堆以及代码实现
2. 堆排序基础代码
3. 一次优化(提高效率)
4. 二次优化(原地堆排序,无需额外空间)

1.什么是最大堆以及代码实现

这里可以参考言简意赅的博客:堆与最大堆

2.堆排序基础代码

import com.heap.MaxHeap;
import utils.CreateRandom;

public class HeapSort {
    //堆排序,将需要排序的数组中的元素全部依次入堆,然后反向的取出最大值.
    // 算法复杂度 O(n * log n)
    public static int[] heapSort_1(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr.length);
        for (int anArr : arr) {
            maxHeap.insert(anArr);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extrackMax();
        }
        return arr;
    }
}

3.一次优化

import com.heap.MaxHeap;
import utils.CreateRandom;

public class HeapSort {
    /*优化1:Heapify
    * 最大堆特性:
    *       一个没有子节点的节点,可以看做是只有一个根节点的堆,
    *       arr[count / 2] 即为堆中第一个拥有节点的节点
    * 因此只需要从下向上的,依次执行shiftDown操作,由小的堆逐渐变成大的堆就可以了
    * 算法复杂度 O(n)
    * */
    public static int[] heapSort_2(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        //在向 MaxHeap 中传入 arr 数组后,整个数组已经满足最大堆
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extrackMax();
        }
        return arr;
    }
}

4.二次优化(原地堆排序)

import com.heap.MaxHeap;
import utils.CreateRandom;

public class HeapSort {
    /*优化2:原地堆排序
    * 在最大堆中,将第一个位置的值(同时也是最大值)与数组最后一个位置交换位置,在原数组的基础上直接得到有序数组,
    * 而不需要开辟新的数组空间来存储堆中排好序的元素.
    * */
    public static int[] heapSort_3(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        return maxHeap.sortInside();
    }
}