堆排序分析

堆排序在之前头条三面的时候问过，之前出于侥幸心理没有认真掌握，现在不得不认真学习下了~

什么是堆排序

可以用下面动图生动形象地描述堆排序的过程。

image

1. 将数组映射到一颗二叉树。
2. 构造初始化堆，从底部非叶子节点出发，将叶子结点中值较大的数换到当前结点，并且不断往下获取更大的值。如果当前结点的值已经比左右结点更大，那么不用再往下了，因为下面的结点之前已经调整成结点大于左右结点。初始化后的堆每个每个结点比左右结点更大。
3. 将调整好的堆的根结点换到数组末尾处，再把交换后子数组调整成大顶堆。陆续再换到后面。最后就能实现从小到大的排序。

实现代码

private void heapSort(int[] nums) {
        int len = nums.length;
        for(int i=len/2-1;i>=0;i--) {
            adjustHeap(nums, i, len);
        }
        for(int i =0; i < len; i++) {
            swap(nums, 0, len-i-1);
            adjustHeap(nums, 0, len-i-1);
        }
    }
    private void swap(int[]nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void adjustHeap(int[]nums, int start, int len) {
        int tmp = nums[start];
        for(int i = start*2+1; i<len; i*=2) {
            if(i+1<len && nums[i+1]>nums[i]) {
                i++;
            }
            if(tmp >= nums[i]) {
                break;
            } else {
                nums[start] = nums[i];
                start = i;
            }
        }
        nums[start] = tmp;
    }

---

待更

复杂度分析

画图描述过程

image.png
image.png
image.png
image.png
image.png
image.png
image.png