简介

鉴于我是一个懒狗，本着又不是不能用、能跑就行的想法，对各式的排序算法一直都是蜻蜓点水，点到为止，了解个大概思路，一直都没有尝试过进行手撕，也算是一件很遗憾的事情了。自己平时写算法一直靠着Arrays.sort()和PriorityQueue等现成的调用得过且过，最近看到面试经常现场考到了很多排序算法，考点涉及到了快速选择算法，堆排序等算法，心想着要不试着撕一下吧，不然真的要完蛋了。

首先，我们先把各种排序算法的复杂度先列举一下，如下表格：

PS: 接下来的手撕部分和图解参考了书 Algorithhms 4th Edition by Robert Sedgewick, Kevin Wayne 也就是《算法 第4版》，这也是我学算法看的第一本书，算是回顾了

选择排序

介绍

选择排序简单来说，就是每次扫描一轮数组，每次挑出最小的、第二小、第三小的…的元素，每轮扫描结束后我们都将这个元素交换到到头部有序序列的末尾。

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

代码实现

一把撕出来了，还行（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package com.company;

import java.util.Arrays;

public class selectionSort {
    public static void sort(int[] arr){
        int len = arr.length;
        for(int i = 0; i < len; i++){ //每轮扫描查找后半段的最小值
            int min = Integer.MAX_VALUE;
            int index = -1;
            for(int j = i; j < len; j++){
                if(arr[j] <= min){
                    index = j;
                    min = arr[j];
                }
            }
            swap(arr, index, i); //将最小值交换到有序数组的尾端
        }
    }
    public static void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

复杂度分析

Selection sort uses N2/2N^2/2 compares and NN exchanges to sort an array of length NN.

Proof: You can prove this fact by examining the trace, which is an NN-by-NN table in which unshaded letters correspond to compares. About one-half of the entries in the table are unshaded—those on and above the diagonal. The entries on the diagonal each correspond to an exchange. More precisely, examination of the code reveals that, for each ii from 00 to N−1N - 1, there is one exchange and N−i−1N - i - 1 compares, so the totals are NN exchanges and (N−1)+(N−2)+...+2+1+0=N(N−1)/2∼N2/2(N - 1) + (N - 2) + . . . + 2 + 1 + 0 = N(N - 1) / 2 \sim N^2 / 2 compares.

为了将数组进行一个彻底的排序，假设数组的长度大小为nn，那么我们需要对数组扫描nn次，复杂度为O(n2)O(n^2)。

此外我们每轮扫描结束之后，我们还需要进行一次交换，交换的复杂度为O(n)O(n)。

该算法没有开辟额外的数组空间，通过交换的形式实现了数组的排序，因此空间复杂度为O(1)O(1)。

综上，选择排序的时间复杂度为O(n2)O(n^2)，空间复杂度为O(n)O(n)。

插入排序

介绍

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

想了一下，前半段有序数组是单调的，插入位置查找可能可以用二分？但是也没用啊，插入必然会使后方的元素后移，后方元素还是要遍历的，得不偿失。

代码实现

还行？小心下标，写的时候留个心眼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package com.company;

import java.util.Arrays;

public class insertSort {
    public static void sort(int[] arr){
        int len = arr.length;
        for(int i = 0; i < len; i++){
            for(int j = i; j > 0 && arr[j] < arr[j - 1]; j--){
              //从后向前不断的交换直到找到自己的位置可以填充进去
                swap(arr, j, j - 1);
            }
        }
    }
    public static void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

复杂度分析

相当于我们遍历一个数组，每次选择一个元素进行前移，插入到前段的有序数组中，而每次交换的次数就会变得很不稳定了。

  • 如果当前的数组完全顺序，已经是有序数组了，那么每一轮都不需要进行交换，复杂度为O(n)O(n)；
  • 反之，如果数组完全逆序，每次选择的元素都被迫必须交换到数组的头部，复杂度为O(n2)O(n^2)

归并排序

介绍

归并算法基于一个最简单的模型，给定两个有序数组，我们可以通过归并算法将其合并，时间复杂度为O(n)O(n)。再加上单个元素构成的数组是有序的这一条件，所以我们就可以无限套娃下去，基本思路就是从最底下开始合并，最后到顶上形成一个有序数组。

归并算法

根据算法第四版的写法，我们需要完成一个原地归并(In-place merge)，

手撸了一个：

1
2
3
4
5
6
7
8
9
10
11
12
public static void merge(int[] arr, int lo, int mid, int hi, int[] aux){
        int i = lo, j = mid + 1;
        for(int k = lo; k <= hi; k++){
            aux[k] = arr[k];
        }
        for(int k = lo; k <= hi; k++){
            if(i > mid) arr[k] = aux[j++]; //[lo, mid]被掏空了
            else if(j > hi) arr[k] = aux[i++]; //[mid + 1, hi]被掏空了
            else if(aux[j] < aux[i]) arr[k] = aux[j++]; //后段小，先从后段取
            else arr[k] = aux[i++]; //前段小，从前段取
        }
    }

这里的merge函数表示的是将arr数组中的[lo, mid]和[mid + 1， hi]区间进行合并的操作，注意区间是左闭右闭。由于左右两段区间的长度和消耗速度不一定相同，归并过程中，当一段数组已经被完全使用，也就是指针已经超出他的尾端下标时，我们应当直接从另一个数组中直接取数。此外，我们需要另外开辟一块空间aux用来临时存放两段数组的相关信息。

自顶向下归并

自顶向下归并排序，顾名思义，就是从上到下将整的区间化整为零，然后按照dfs的方式一小段一小段的进行组合，示意图如下：

注意到归并的时候是一个类似于后序遍历的走法，一旦我们有两段可以的归并区间，我们会直接将其归并，而不是等待其他分段先归并。

更加准确的图如下：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package com.company;

import java.util.Arrays;

public class mergeSort {
    public static void sort(int[] arr, int lo, int hi, int[] aux) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(arr, lo, mid, aux);
        sort(arr, mid + 1, hi, aux);
        merge(arr, lo, mid, hi, aux);
    }
    public static void sort(int[] arr, int[] aux){
        sort(arr, 0, arr.length - 1, aux);
    }

    public static void merge(int[] arr, int lo, int mid, int hi, int[] aux) {
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            aux[k] = arr[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) arr[k] = aux[j++];
            else if (j > hi) arr[k] = aux[i++];
            else if (aux[j] < aux[i]) arr[k] = aux[j++];
            else arr[k] = aux[i++];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        int len = arr.length;
        int[] aux = new int[len];
        sort(arr, aux);
        System.out.println(Arrays.toString(arr));
    }
}

自底向上归并

自底向上归并原理其实类似，只是他是一级一级合并的，而不是凑到两个就合并。

如图：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.company;

import java.util.Arrays;

public class mergeSort {
    public static void merge(int[] arr, int lo, int mid, int hi, int[] aux) {
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            aux[k] = arr[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) arr[k] = aux[j++];
            else if (j > hi) arr[k] = aux[i++];
            else if (aux[j] < aux[i]) arr[k] = aux[j++];
            else arr[k] = aux[i++];
        }
    }
    public static void sort(int[] arr, int[] aux){
        int len = arr.length;
        for(int sz = 1; sz < len; sz += sz){
            for(int lo = 0; lo < len - sz; lo += sz + sz){
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, len - 1), aux);
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        int len = arr.length;
        int[] aux = new int[len];
        sort(arr, aux);
        System.out.println(Arrays.toString(arr));
    }
}

复杂度分析

如图所示，一次归并排序任务会被分割成如下若干个小任务，而两两数组之间我们都需要进行归并操作，也就是每一层我们总计都要对数组进行一轮遍历，复杂度O(n)O(n)。总共分摊下来，共有lognlog n层，因此时间复杂度为O(nlogn)O(nlogn)。

空间复杂度方面，我们只需要开辟一个和原数组等长的临时数组aux即可。

类似例题

148. 排序链表

这是一道leetcode上面很经典的算法题， 要求我们对链表进行排序，在这里我们使用自顶向下的归并排序算法来进行解决。

题目

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

进阶：

你可以在 O(nlogn)O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0,5∗104][0, 5 * 10^4] 内

−105≤Node.val≤105-10^5 \leq Node.val \leq 10^5

题解

其实链表的归并排序和数组的归并排序差距不大，关键在于我们如何确定当前链表的中点mid，其余的归并相关操作其实大致相同。还有就是遇到类似的递归问题，我们要严格的确定好我们的区间表示了什么，尤其是左右端点的开闭情况，否则当我们分割区间的时候会产生很多错误。这点在二分查找中也有体现。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package com.company;

public class mergeSort {
    public static ListNode merge(ListNode listNode1, ListNode listNode2) { //合并两段有序链表
        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy, tmp1 = listNode1, tmp2 = listNode2;
        while (tmp1 != null && tmp2 != null) {
            if (tmp1.val < tmp2.val) {
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            } else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if (tmp1 != null) tmp.next = tmp1;
        else tmp.next = tmp2;
        return dummy.next;
    }

    public static ListNode sortedList(ListNode head, ListNode tail) { //指定区间，递归进行合并，注意当前区间为左闭右开，tail取不到
        //首先要将区间尽可能的等分成两段
        if (head == null) { //特殊情况处理
            return head;
        }
        if (head.next == tail) { //单节点直接返回
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head; //快慢指针查找中点
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next; //两步分开走，这点很妙，可以避免跨太大了漏掉tail
            }
        }
        ListNode mid = slow;
      	//开始套娃
        ListNode list1 = sortedList(head, mid);
        ListNode list2 = sortedList(mid, tail);
        return merge(list1, list2);
    }

    public static ListNode sortedList(ListNode head) { //复用代码，完整链表尾部tail为null
        return sortedList(head, null);
    }

    public static void main(String[] args) {
        ListNode p = new ListNode(-1);
        ListNode head = p;
        for (int i = 0; i < 100; i++) {
            p.next = new ListNode((int) (Math.random() * 1000));
            p = p.next;
        }
        ListNode n_node = sortedList(head);
        while (n_node != null) {
            System.out.println(n_node.val);
            n_node = n_node.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        next = null;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

快速排序

介绍

快速排序使用了一种分治的思想，也可以认为和归并排序有类似之处吧。

我们选定数组中的一个元素作为标准，我们称之为基准（pivot），随后我们将比这个元素小的都移动到他的左边，比这个元素大的都放置到右侧。我们将这种操作称为分区（partition）操作。

随后我们递归的把左侧区间和右侧区间继续进行相关操作，将区间继续细分，直到区间里只有一个元素，此时整个数组就是有序的了。

如图：

简易示例如下：

我们取第一个元素K为基准，随后分割出了左右两个区间。以此类推，就能获得整个有序的区间。

分区算法

快速排序的核心就是这个分区算法，而分区算法就是重中之重。

双路分区

根据之前的思路，我们的目标结果如图所示，其中v是基准。所有比v小的元素都放置到左侧，大的都放置到右侧。

具体实现逻辑，我们直接对数组进行遍历，分为两段分区，如果小，我们就插入到左分区和右分区交界处，然后把交界处的元素换到最右边来。如果大，我们就直接将它放在右区间的右边。使用指针，我们实现了区间的“生长”，当我们完成遍历之后，我们再把头部的基准交换到交界处即可。如图：

小

大

排序的简单逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package com.company;

import java.util.Arrays;

public class quickSort {
    public static void twoWay(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int boundary = lo + 1;
        int pivot = arr[lo];
        for (int i = lo + 1; i <= hi; i++) {
            if (arr[i] < pivot) {
                swap(arr, i, boundary);
                boundary++;
            }
        }
        swap(arr, lo, boundary - 1);
    }

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

    public static void main(String[] args) {
        int[] arr = new int[]{5, 1, 2, 3, 4, 7, -1, 9, 0};
        twoWay(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

三路分区

当我们进行双路分区的时候自然会想到一个问题，如果数组中间存在着大量的和基准pivot相等的元素，会对后续的排序带来更大的影响。例如，区间可能划分不均匀，还会导致无效的交换遍历操作增多。如果我们在做分区的时候划分出三个分区，第一分区存储小于基准的部分，第二部分存储等于基准的部分，第三部分存储大于基准的部分，这也就是我们所说的三路快排。

如图：

参考刚才的双路快排的逻辑，如果我们将三个分区全部置于遍历指针左侧，一次操作可能会涉及多次交换，可读性也不强，因此我们将第三分区直接放置在数组最右侧，从最右端开始生长。将小于v的部分放到指针lt左边，将大于v的部分放到指针gt右边。考虑到v有重复值的情况，遇到等于v的情况，将i指针右移。我们不难得出三路分区算法的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package com.company;

import java.util.Arrays;

public class quickSort {
    public static void threeWay(int[] arr, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        int pivot = arr[lo];
        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt++, i++);
            } else if (arr[i] > pivot) {
                swap(arr, i, gt--);
            } else i++;
        }
    }

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

    public static void main(String[] args) {
        int[] arr = new int[]{5, 1, 2, 3, 4, 7, -1, 9, 0, 5, 5, 5};
        threeWay(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

排序实现

简单的来说就是套娃，把左区间和右区间无限做下去。我们就简单的以三路快排为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.company;

import java.util.Arrays;

public class quickSort {
    public static void threeWaySort(int[] arr, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        int pivot = arr[lo];
        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt++, i++);
            } else if (arr[i] > pivot) {
                swap(arr, i, gt--);
            } else i++;
        }
        threeWaySort(arr, lo, lt - 1);
        threeWaySort(arr, gt + 1, hi);
    }

    public static void threeWaySort(int[] arr) {
        threeWaySort(arr, 0, arr.length - 1);
    }

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

    public static void main(String[] args) {
        int[] arr = new int[]{5, 1, 2, 3, 4, 7, -1, 9, 0, 5, 5, 5};
        threeWaySort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

复杂度分析

快速排序很重要的一点是他是一个原地算法，我们不需要花费额外的空间，只需要在数组身上进行原地交换即可。

关于空间复杂度方面，存在一个问题，每次我们都是从区间第一个去默认取基准pivot的，随后我们根据基准，将区间劈成两段再各自进行排序。当pivot刚好是当前区间的中位数时，区间被正好一分为二，这个时候操作树的深度同上方归并排序也是lognlogn，此时为最佳时间复杂度也就是O(nlogn)O(nlogn)。但是如果数组完全逆序的情况下，操作数可能完全倾向一侧，也就是每次分区之后，一侧区间长度为0，另一侧是len - 2，这个时候操作树的深度就会变为nn，复杂度会退化成O(n2)O(n^2)，空间复杂度因为调用递归的关系，需要栈空间，复杂度最好O(logn)O(logn)，最差O(n)O(n)，因此我们也说快速排序是不稳定的排序算法。

为了防止上述情况的发生，快排前我们可以对数组进行随机的打乱，来确保取到的第一个元素pivot尽可能的是中位数。

堆排序

堆排序，就涉及到树的相关操作了，问题就变得焦灼了起来。

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

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

以下我们以大根堆为例（还是做个升序排列好点）

我们每轮通过对堆内部结构的调整，让最大的元素浮动到根节点上，随后我们将根节点元素取出，和最底层的元素交换位置，以此循环。如图：

堆和数组之间的互相表示

如图所示，如果我们对数组中对编号从1开始计数，按照层级进行顺序编号的话，我们就能很快速的发现规律，对于节点n，他的左子节点编号为2n，右子节点编号为2n + 1。对于他的父节点的话编号应该为n / 2

当然换句话讲，如果从0作为正常数组的下标进行计数的话，对于节点n，他的左子节点编号为2n + 1，右子节点编号为2n + 2。父节点的计算就会难受一些，只能表示为(n + 1) / 2 - 1，好在我们做上浮处理的时候也不需要考虑这些。

针对单个节点的调整（大数上浮）

单个节点的调整中，我们要确保此棵树中的每一个节点作为父节点都是他所在的树中最大的。

思路也很简单，我们只需要选中一个节点，取他的左子节点和右子节点（前提是如果有）。三点比较，谁大就把根节点换成谁。但是把小数换到子节点会导致儿子作为父节点可能不是最大值，要重新调整。

简单代码示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void heapify(int[] arr, int i, int len){ //针对i号元素所在节点进行调整
  //其中还需要给出堆数组的长度，下标不能越界，此外已经排序好放到末尾的数也不能拉出来纳入计算
	int left = 2 * i + 1;
  int right = 2 * i + 2;
  //计算出左节点和右节点的编号
  if(left < len && arr[left] > arr[largest]){
    largest = left;
  }
  if(right < len && arr[right] > arr[largest]){
    largest = right;
  }
  //有大取大，然后交换
  if(largest != i){
    swap(arr, i, largest);
    heapify(arr, largest, len); //把小数换给儿子去了，可能导致儿子作为父节点不够大的情况，重新调整
  }
}

利用单个节点的调整代码，我们自堆底部向前逐个节点进行调整，就完成了整个堆的调整。

代码实现

不难实现～代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package com.company;

import java.util.Arrays;

public class heapSort {

    public static void heapify(int[] arr, int i, int len){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if(left < len && arr[left] > arr[largest]){
            largest = left;
        }
        if(right < len && arr[right] > arr[largest]){
            largest = right;
        }
        if(largest != i){
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }
    public static void buildHeap(int[] arr, int len){
        for(int i = len - 1; i >= 0; i--){ //从后往前逐个节点进行调整，就构建了一遍堆
            heapify(arr, i, len);
        }
    }
    public static void sort(int[] arr){
        int len = arr.length;
        for(int i = len; i > 0; i--){
            buildHeap(arr, i);
            swap(arr, 0, i - 1); //将0所在的最大值换到末尾的有序段中去，然后重新构建堆
        }
    }
    public static void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

复杂度分析

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

那么总的时间计算为：s=2i−1∗(k−i)s = 2^{i - 1} * (k - i)；其中 i 表示第几层，2i−12^{i - 1} 表示该层上有多少个元素，k−ik - i表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

S=2k−2∗1+2k−3∗2.....+2∗(k−2)+20∗(k−1)S = 2^{k-2} * 1 + 2^{k-3} * 2.....+2 * (k-2)+2^{0} * (k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；

等式左右乘上2，然后和原来的等式相减，就变成了：

S=2k−1+2k−2+2k−3.....+2−(k−1)S = 2^{k - 1} + 2^{k - 2} + 2^{k - 3} ..... + 2 - (k-1)

因此我们得到了：S=2k−k−1S = 2^k -k -1，又因为k为完全二叉树的深度，所以有：2k≤n<2k+1−12^k \leq n < 2^{k + 1} - 1，总之我们可以认为时间复杂度为O(n)O(n)

而更改堆元素之后重建堆的时间则是O(nlogn)O(nlogn)，循环 n−1n - 1 次，每次都是从根节点往下循环查找，所以每一次时间是 lognlogn，总时间：logn(n−1)=nlogn−lognlogn(n-1) = nlogn - logn

空间复杂度方面，由于堆排序是就地排序，空间复杂度是常数即O(1)O(1)