【排序算法】排序算法-堆排序

• 概述
• 执行流程
• 代码

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
堆:
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

public class HeapSort {

    public static void main(String[] args) {

        int[] arr = {9,8,7,6,5,4,3,2,1};
        sort(arr, arr.length);
        System.out.println("升序排列:" + Arrays.toString(arr));
        sort2(arr, arr.length);
        System.out.println("降序排列:" + Arrays.toString(arr));
    }

    //升序
    static void sort(int[] nums, int heapSize) {
        //原地建堆
        buildMaxHeap(nums, heapSize);

        while (heapSize > 1) {
            //交换堆顶元素和尾部元素
            swap(nums, 0, --heapSize);

            //对0位置进行siftDown(恢复堆的性质)
            maxHeapify(nums, 0, heapSize);
        }
    }

    //降序
    static void sort2(int[] nums, int heapSize) {
        //原地建堆
        buildMinHeap(nums, heapSize);

        while (heapSize > 1) {
            //交换堆顶元素和尾部元素
            swap(nums, 0, --heapSize);

            //对0位置进行siftDown(恢复堆的性质)
            minHeapify(nums, 0, heapSize);
        }
    }
    
    static void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }

    
    static void buildMinHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            minHeapify(a, i, heapSize);
        }
    }

    
    static void minHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, smallest = i;
        if (l < heapSize && a[l] < a[smallest]) {
            smallest = l;
        }
        if (r < heapSize && a[r] < a[smallest]) {
            smallest = r;
        }
        if (smallest != i) {
            swap(a, i, smallest);
            minHeapify(a, smallest, heapSize);
        }
    }

    
    static void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    
    static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

• 测试