文章目录

1. 堆排序

1.1 算法思想

堆排序是指利用堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1.2 算法步骤

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  2. 将最大的数与最低端数交换并排除，此时得到了一个最值数;
  3. 重复步骤1、2，直至只剩最后一个数。

1.3 复杂度分析

堆排序利用树的思想，只需要logn次遍历就能比较整个堆，因此时间复杂度为O（nlogn），空间复杂度为O（1）。

最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性
O(nlogn) O(nlogn) O(nlogn) O（1） 不稳定

2. 代码实现

2.1 Java版

class Solution {
   
    public int[] sortArray(int[] nums) {
   
        // 堆排序
        // 交换类排序的升级，
        // 时间onlgn，空间o1，不稳定
        int[] arr = new int[nums.length];
        System.arraycopy(nums,0,arr,0,nums.length);
        heapSort(arr);
        return arr;
    }
    private void heapSort(int[] arr){
   
        int len = arr.length;
        // 建立堆
        for(int i = len / 2 -1; i >= 0; --i){
   
            adjust(arr, len, i);
        }

        // 调整堆
        for(int i = len -1; i > 0;--i){
   
            swap(arr, 0, i);
            adjust(arr, i, 0);
        }
    }
    private void adjust(int[] arr, int len, int idx){
   
        int left = 2 * idx+1, right = 2 * idx +2;
        int maxIdx = idx;
        if(left < len && arr[left] > arr[maxIdx]){
   
            maxIdx = left;
        }
        if(right < len && arr[right] > arr[maxIdx]){
   
            maxIdx = right;
        }
        if(maxIdx != idx){
   
            swap(arr, idx, maxIdx);
            adjust(arr, len, maxIdx);
        }
    }

    private void swap(int[] arr, int i, int j){
   
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}