Refresh - 排序

排序算法很重要，一是因为它是最基础的算法，二是不同的排序方法展示了不同的经典思路，学会这些思路对其他问题的思考能带来非常大的帮助。

参考：

• 十大经典排序算法

1. 排序总结
   1. 思路和流程
   2. 高效 vs 不高效
   3. 稳定 vs 不稳定
   4. 最快情况
   5. in place vs. out place
2. 冒泡
3. 选择
4. 插排
5. 归并
   1. in place归并
   2. 归并的比较次数为什么比选择排序少
   3. 外排序
   4. 相关题型
      1. 合并k个升序链表
      2. 左闭右闭？
6. 快排
   1. 快排的比较次数为什么比选择排序少
   2. 最坏情况
   3. 相关题型
7. 堆排
   1. 堆 heap
   2. 堆排 heap sort
      1. 构建堆 nlogn
      2. 构建新堆 logn
   3. PriorityQueue
   4. 相关题型
      1. 最小k个数

排序总结

我决定以后的东西尽量倒着写了，先写结论，从宏观概述，再深入细节，去验证这些概述。不然有时候细枝末节太多了，陷入不必要的汪洋大海了，反倒不能及时把控全局。

思路和流程

大部分的排序的流程，基本都是两步走：

1. 挑一个最值
2. 重复n次

除了分治的思路，比如归并和快排。

高效 vs 不高效

对于“挑一个最值”的排序方式，其关键在于是否通过一些前置的数据结构操作，让“挑一个最值”这一步变得高效。如果设计精巧，能做到O(logn)；如果懒得搞，就得花O(n)的brute force方式挑一个最值。

稳定 vs 不稳定

如果是一个一个挨着换位置的，就是稳定，比如冒泡、插排、归并。

如果出现非连续元素交换的，就是不稳定，比如选择排序交换的那一下，堆排交换的那一下，快排则一直在跨空间交换。

高效的算法除了归并，都不稳定。

最快情况

冒泡和插排这种一个一个挪的排序，应对有序序列时非常高效，O(n)即可，是最速排序。

快排、归并、堆排，都是nlog，且后两个毫无波澜，因为归并无论如何都是二分，堆排无论如何都需要logn去调整为最大/小堆。但是快排不一样，pivot上的数值未必能二分整个序列，最差情况就是永远都是一分，O(n^2)。

但是快排确实是最快的，虽然都是O(nlogn)，但人家常数小。对于比较随机的数列，快排是优于归并和堆排的。

in place vs. out place

是否在原有数组上完成排序，又叫in place（原地排序算法）和out place。

比如归并需要new一个新的数组承接两个数组归并，否则数据就互相覆盖了，所以是out place。其他都是in place。

冒泡

每次挑一个最大的，沉底。挑的方式就是两两比较，每次都拿大的那个出来，那么最终沉底的一定是最大的：

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                // 交换
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}

选择

每次挑一个最小的，放开头。或者每次挑一个最大的，沉底，也行。和冒泡的区别就是怎么选出最大的：冒泡是选的过程中两两换位，大的放前面/后面继续比下去；选择排序是选的过程中只有碰到大的才交换，否则不变。

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

插排

之所以要提一下，是因为这就是打牌的时候，起完牌后的整理牌的操作……一直用，却没有意识到……

先固定最左边那张，然后把右边的依次插到左边合适的位置。

而且，插排很像是倒着的冒泡，不同的地方在于：倒着比的时候，左边的数组已经是有序的，所以不需要一直两两交换，只需要在找到合适的位置后交换一次就行了，如果一直两两交换反而多此一举了：

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 倒着遍历左边已经排序的序列
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                // 存在比它大的数
                arr[j] = arr[j - 1];
                j--;
            }

            // 找到比它小的数，可以停了，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

归并

归并用了分治，分治就是：

1. 分
2. 合：分到一定程度就合

这个合可以是分到不能再分了（只剩下一个元素）就合，也可以是小于一定阈值就不再分了，采用别的排序方式做合并，这样做主要是出于效率考量。

先把合并的merge子流程放这里：

protected int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int k = 0, i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++];
        } else {
            result[k++] = right[j++];
        }
    }

    while (i < left.length) {
        result[k++] = left[i++];
    }

    while (j < right.length) {
        result[k++] = right[j++];
    }

    return result;
}

该merge方法在合并数组时一直在new数组（每层new n个空间，一共logN层），所以空间复杂度是nlogn。

先看一个不太推荐的写法。直接用了原函数的参数（int[]），所以传进来的都是子数组。这种传参方式决定了只能把子数组完整new出来，比较费空间：

public int[] sort(int[] sourceArray) throws Exception {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    if (arr.length < 2) {
        return arr;
    }
    int mid = (int) Math.floor(arr.length / 2);

    // 每一层到这里都会需要n个空间，一共logN层，所以空间是NlogN
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);

    return merge(sort(left), sort(right));
}

所以这么写空间复杂度是NlogN。

如果不想copy太多，就利用原始数组，以start，end划分界限，就不用每次把子数组copy出来了，也很简单：

1. 为了划分，所以参数列表里必须有
   1. 原始数组
   2. start index
   3. end index
2. 所以我们要新创建一个方法，有这些参数；
3. 当只有一个元素的时候，就是划分结束的时候，因为划分返回的必须是数组，所以这里new一个数组；
4. 划分就用左闭右开，方便得很！

    public static int[] mergeSort(int[] arr) {
        return divide(arr, 0, arr.length);
    }

    public static int[] divide(int[] arr, int start, int end) {

        if (end - start == 1) {
            // 别写错了，我们要的是这个位置的值，不是这个位置。所以用`arr[start]`
            return new int[] {arr[start]};
        }

        int mid = (start + end) >> 1;
        return merge(divide(arr, start, mid), divide(arr, mid, end));
    }

这里我们做划分的时候只new了n个元素，所以是O(n)。但因为一开始的merge方法在合并数组时一直在new数组（每层new n个空间，一共logN层，所以还是nlogn），所以空间复杂度还是nlogn，没什么变化，只是在划分这一步变得优雅起来了。

上面这两种方法，切分时候的返回值都是int[]，但是用的方式不同。前者copy，后者原地切分。

下面的方法直接在原始数组上调整，所以divide的函数不需要返回值。这种方法只用了O(n)的空间，因为result临时空间被反复使用，每一次比较的时候都用一次：

public void merge_sort(int[] arr) {
    int len = arr.length;
    
    // 空间O(n)
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

// 这个end是inclusive
public void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1);
    merge_sort_recursive(arr, result, start2, end2);
    
    // 合并
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
        
    // 最后这个是用当前merge好的这一段result覆盖arr相应部分，以让arr有序
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}

这么写空间复杂度是O(n)。但是不太建议这么写，比较复杂。

in place归并

归并的空间复杂度一般是nlogn，上面也给出了n的复杂度，实际上也有O(1)的空间复杂度来做in place merge sort的：

• https://www.baeldung.com/cs/merge-sort-in-place

维基百科说：

• 归并排序（merge sort）— O(nlog n)；需要O(n)额外空间
• 原地归并排序— O(n log^2 n)；需要O(1)额外空间

归并的比较次数为什么比选择排序少

归并排序的时间复杂度：其实就是一共比较了多少次（其实其他排序也是在计算一共比较了多少次……）！如果做成树状merge图，会发现每层都要比较N次，树高为logN，所以时间复杂度为O(nlogn)。

归并的时间复杂度没有堆排好分析。堆排每次贡献一个最值需要logn，一共需要做n次，很像选择排序等。但是归并不需要挑最值，而是一直在做局部排序，到最后一层的时候就排好了。

归并排序使用分治的策略，将一个大问题拆分为较小的子问题来解决。在归并排序中，数组被递归地拆分为两个子数组，直到每个子数组只有一个元素为止。然后，这些子数组被逐步合并以生成有序的结果。在合并的过程中，归并排序会比较两个子数组中的元素，并按照顺序将它们合并到一个新的数组中。这里的关键是，当我们合并两个有序的子数组时，我们可以通过比较当前两个子数组的最小元素来确定下一个要合并的元素。这样，我们可以避免和每个元素重新比较，因为他们已经确定顺序了。这就是比选择排序比较的少的地方。每一个元素都只比较了logN次（每个元素在每一层只会被比较一次，一共比了logN层）。但是在选择排序里，每一个元素都被比较了N次。

通过这种分而治之的方法，归并排序能够在每一次比较中消除较多的元素。当两个子数组中的元素有序时，我们只需要进行一次比较，并将较小的元素放入新的数组中。这样，在合并过程中，我们可以减少比较次数并最大限度地利用已经有序的子数组。

因此，归并排序的优势在于它通过分治的策略，减少了比较次数和元素交换次数，从而提高了排序的效率。归并排序的时间复杂度为O(n log n)，其中n是元素的数量。

在KMP匹配中，有相同的道理：KMP 之所以能够在 O(m+n) 复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。

作者：AC_OIer 链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

外排序

值得一提的是，外排序用的也是归并。

1. 每次读取内存能装下的数据，进行whatever排序，可以用in place排序，不占额外空间；
2. 排好后写入临时文件；
3. 从每个临时文件读一点儿（称为block吧）数据进内存，然后merge他们即可。某一个文件读进来的block被merge完了，就从那个文件再读一个block进来。因为文件原本已经有序了，所以如果之前的block没用完，后面的block一定用不上。这就是归并排序里的merge环节的思想。

而“后面的block一定用不上”，是“外归并排序”能在主存外完成排序的关键步骤 – 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并)，每个大块不用完全载入主存，否则就爆了。

相关题型

开头就说了，学习排序更重要的是学习算法的思想。归并的思想用来解决一些问题会更高效。

合并k个升序链表

合并k个升序链表：

public ListNode mergeKLists(ListNode[] lists) {
}

也是先分再治。归并排序是两个字数组合并为一个数组，这里是两个链表合并成一个链表。

这里用起止索引来划分数组，很优雅：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        return divide(lists, 0, lists.length);
    }

    public ListNode divide(ListNode[] lists, int start, int end) {
        // 要不要end inclusive？取决于想不想。如果这样写，那就是不想，传参的时候就传exclusive index就行了
        // 我建议用end exclusive，后面划分区间的时候很好划分：[start, mid), [mid, end)，不用考虑end+/-1了
        if (end - start == 1) {
            return lists[start];
        }

        if (start >= end) {
            // 可以返回null，因为merge的时候支持其中的链表为null
            // 但其实执行不到这一步
            return null;
        }

        int mid = (start + end) / 2;
        // 用end exclusive，这里划分区间的时候很好划分：[start, mid), [mid, end)，不用考虑end+/-1了
        return mergeTwoLists(divide(lists, start, mid), divide(lists, mid, end));
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            if (list2 == null) {
                return list1;
            } else {
                return list2;
            }
        }

        ListNode p = new ListNode();
        ListNode head = p;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }

        p.next = list1 == null ? list2 : list1;

        return head.next;
    }
}

左闭右闭？

无论是归并时候的数组划分，还是其他思想里的数组划分，都涉及到一个选择：用end inclusive还是end exclusive？推荐使用end exclusive，就像上面的解法一样。

下面这个是官方题解，放在这里主要为了和上面的数组划分对比一下。官方题解用的是end inclusive，数组划分的时候很麻烦。划分为[start, mid]和[mid+1, end]就是可以的，划分为[start, mid-1]和[mid, end]就是错的。

为什么？举个例子。假设当前start=2，end=3，按照前后都是inclusive的设定，本来应该分别返回arr[2]、arr[3]这两个单元素。但是现在divide的时候，mid就是5/2=2（本来应该是2.5，现在相当于索引向前去了一点儿）：

• 如果用[start, mid]和[mid+1, end]：就变成了[2, 2]和[3, 3]，前面返回arr[2]，符合预期，后面返回arr[3]，符合预期；
• 如果用[start, mid-1]和[mid, end]：就变成了[2, 1]和[2, 3]，前面返回null，后面还是start=2，end=3，一直这么下去，无限递归了；

所以左闭右闭很蛋疼，究其原因，大概就是上面说的：本来应该是2.5，现在相当于索引向前去了一点儿。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ...
    }
}

快排

快排的思想：

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 遍历数组，所有元素比基准值小的挪到基准前面，所有元素比基准值大的挪到基准后面（和基准相同的数可以到任一边），这就是一次分区（partition）操作。在这个划分退出之后，该基准就处于数组的中间位置。这一轮下来，pivot的位置就排好了。
3. 递归地（recursive）把基准值左右的两个子序列分别排序；

第二步其实类似于选择排序中的“每轮挑选一个元素”，只不过选择排序挑的是最值，它挑的是中间值。但不管怎样，一轮过后，排好了一个元素（中间值）。这个过程是O(n)。按照选择排序的思路，n轮之后，就排好了，不过快排没有经历n轮，它只经历了logN轮，所以是NlogN。为什么是logn轮？和归并排序类比，从树状图可以很直观地感知到。

快排的比较次数为什么比选择排序少

如果和归并排序类比，从“减少比较次数”这个角度来看的话，比如快排每次确定左半边数组pivot应该在的位置的时候，只和左半边的元素进行了比较，没有和右半边的元素进行比较，所以少了很多次比较。也就是说，从第一次划定pivot之后，后面每一个子数组在确定povit时，“左右两边的大小关系”已经被我们利用起来了，每次都少比较了一半的元素。

理解了上面这些，快排的算法其实很好写。值得注意的是，算法在实现第二步（怎么把pivot放到它该在的位置）的时候写得比较隐晦，但很精彩。假设当前pivot选的是位置0的元素，反正所有比它小的元素（假设有5个），都要放在左半边，那就从第二个开始放（因为第一个现在放的是pivot），最终会占用1-5的位置，最后把0（pivot）和5换一下位置（所以快排是不稳定算法），这样0-4五个元素就都是比pivot小的，pivot放在了位置5上。

快排不在乎左右两边本身有序（废话，有序了那不就已然排好了吗……），只要分别比pivot小/大就行。

    private void quickSort(int[] array, int start, int end) {
        // 确定出pivot
        int pivot = divide(array, start, end);
        if (pivot == -1) {
            return;
        }

        quickSort(array, start, pivot);
        quickSort(array, pivot + 1, end);
    }

    // 返回pivot index，如果划分到底了就返回-1。end exclusive
    private int divide(int[] array, int start, int end) {
        // 退出条件
        if (start >= end) {
            return -1;
        }

        // 设定基准值（pivot）的位置
        int pivotPos = start;
        // nextSwapPos是第n个交换的位置，也就是比pivot小的那n个元素的位置。用上面的例子来说，n最大为5
        int nextSwapPos = pivotPos + 1;
        
        for (int i = nextSwapPos; i < end; i++) {
            // 所有比pivot小的，依次从第二个位置开始放
            if (array[i] < array[pivotPos]) {
                swap(array, i, nextSwapPos);
                nextSwapPos++;
            }
        }

        // 最后把第一个位置的pivot换走就行
        int pivotPosition = nextSwapPos - 1;
        swap(array, pivotPos, pivotPosition);
        return pivotPosition;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

快排也是分治，只不过和归并逆过来：

• 归并是先递归，再处理子数组（排序）；
• 快排是先处理子数组（小的放左边，大的放右边），再递归；

所以快排的时间复杂度和归并可以用同样的分析方法：每层比较n次一共logn层，所以O(nlogn)。

最坏情况

O(n^2)

同样是分治，之所以归并无论如何都是O(nlogn)，是因为归并和堆排一样，无论什么情况，都能把树的高度控制为logn。而快排如果每次无法分成比较均匀的两份，就会影响最终树的高度。最差情况，本身就是有序序列，每次所选的pivot最终都会落在两端而非中间：

• 从形象的角度来说：树的高度为n，每层比较次数依然是n，所以就是O(n^2)，相当于一棵二叉树退化成了单链表；
• 从比较次数来说：每次都是以O(n)的复杂度比较pivot，比较了n轮而非logn轮；

相关题型

参考下面的最小k个数。

堆排

堆排大概是面试中最容易碰到的一种排序了，倒不是让实现堆排，而是很多问题都可以借助堆排来搞定（直接利用PriorityQueue），所以理解堆排的思想很重要。

堆 heap

堆是一个数据结构，堆排是利用堆做排序的一个算法：

• 堆（heap）：是本身具有大小关系的完全二叉树（除了最后一层其余层都是满的）。父节点要么比所有子节点大，要么比所有子节点小，因此也可以分为最大堆或最小堆；和常用的树是二叉树一样，常用的堆也是二叉堆（binary heap）；
• 堆排：利用堆进行排序；

堆（Heap）是计算机科学中的一种特别的完全二叉树。满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

堆始于J. W. J. Williams在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。

所以堆指的是叠罗汉把人堆起来的意思？

堆和bst乍看相似，实际差别很大：

• bst是根大于左小于右，所以左右有严格的大小关系；
• 堆是根一定大于/小于左右，左右之间没什么关系，只有根是最值。但仔细想想，左右之间还是有关系的：假设构建的是小根堆，如果左子节点小于右子节点，那么可以断定左子节点一定小于右子树的每一个节点，反之亦然。这也就意味着如果当前root不是最小值，你想找最小值，去左子树找就行了，不用去和右子树比较；

所以堆在找最值的过程中帮助我们减少了比较次数，这正是降低时间复杂度的方式。无论快排还是归并，都是利用左右分治，每一次分治后都比上一次减少了一半的比较次数。

最小堆不保证左子树一定都小于右子树（或者右子树一定都小于左子树），但如果左子节点小于右子节点，那么最小值一定不用去右子树找了。

堆排 heap sort

堆排是利用堆做排序的一个算法。

堆排的主流程本身是简单的，和选择排序一样：

1. 每次挑一个最值；
2. 挑n次；

所以堆排其实也是一个for循环，把最值一一挑出来。不同的是，在每次挑最值的时候，选择排序是O(n)的复杂度，而堆只需要logN。

如果利用jdk里的PriorityQueue的话，主流程会特别简单：

    // nlogn
    private int[] heapSort(int[] array) {
        // big to small
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        
        // O(n)
        for (int i : array) {
            // O(logn)
            pq.offer(i);
        }
        
        return getArray(pq);
    }

    private int[] getArray(PriorityQueue<Integer> pq) {
        int[] result = new int[pq.size()];
        int i = 0;
        while (!pq.isEmpty()) {
            result[i++] = pq.poll();
        }

        return result;
    }

我们每完成一次堆，就代表找出了一次最值。所以整个算法麻烦的地方在于：怎么在每次循环里，把剩余元素构建成一个堆。

构建堆 nlogn

通常堆是通过一维数组来实现的。只要画个二叉树并标记好位置序号（按照数组起始位置为0标记），就能发现：\\

父节点i的左子节点在位置
(
2
i
+
1
)； \\


父节点i的右子节点在位置
(
2
i
+
2
)；
{\displaystyle } \\

子节点k的父节点在位置
⌊
(
k
−
1
)
/
2
⌋;

之前我做了一种错误的构建方式是：只要倒着比较根、左子节点、右子节点三个节点的值即可，把最值挑出来，作为根，并重复这个过程，最后的root就是最值。即：直接for i in [len - 1, 0]，对于每一个i，比较i、2i-1、2i+1三处节点的最值即可。所以只需要从第一个有子节点的节点开始进行上述比较即可：for i in [(len - 1) / 2（向下取整）, 0]。

这样做是错误的，最后的root确实是最值，但仅仅找出了最值，构造出来的完全二叉树并不是堆！其弊端接下来就会显现——它不能在接下来的步骤中，在O(logn)的时间内贡献出一个新的最值。仔细想想每一轮这么做的时间复杂度其实都是O(n)，再加上堆排本身的O(n)遍历，算法就是O(n^2)了。那和选择排序有什么区别……

上面的思路框架是对的，但是在构建“堆”上出错了，由于它构造出来的不是堆，每次贡献一个新的最值都需要O(n)，不能达到O(logn)的复杂度。实际上按照堆的定义，每一个子树的root也要是最值，以最小堆为例，如果根小于左右子节点，被换了下来，还要继续和原本子节点的子节点进行比较，因为这个节点可能实在是太小了，还要继续下降，要把每一个子树都调整为最小堆。虽然每次挑最小值很快（左右子节点中较小的那个就是，O(1)），但是挑完之后要用O(logn)的时间复杂度把当前分支全都调整成最小二叉堆，这样才能在下次还能够以O(1)的复杂度挑到最小值。从而整个挑最值的过程是O(logn)。

而且还能比较的更少一些：因为叶子节点本身不存在左右子节点，或者说如果把叶子节点看做一个堆，它已经符合堆的定义了。但是从代码实现的角度来看，没有必要，少了几次比较，却增加了代码的出错概率。

真正的堆构建：

    private void maxHeapify(int[] array, int i) {
        int lIndex = 2 * i + 1;
        int rIndex = 2 * i + 2;

        // 如果没有左子节点，那不用heapify了
        if (lIndex >= array.length) {
            return;
        }

        int maxIndex = lIndex;
        if (rIndex < array.length) {
            // 如果有右子节点，看看左右谁大
            maxIndex = array[lIndex] > array[rIndex] ? lIndex : rIndex;
        }

        // 如果root不够大，交换
        if (array[i] < array[maxIndex]) {
            swap(array, i, maxIndex);
            // 交换过后，要继续heapify，直到没有子节点可以比较
            maxHeapify(array, maxIndex);
        }

    }
    
    
    // 构建堆的主函数框架：倒着来，相当于自底向上把二叉树构建为二叉堆
    for (int i = array.length - 1; i >= 0; i--) {
        maxHeapify(array, i);
    }

Java传数组其实传的是数组的地址，所以可以在原数组上swap。

构建堆的主函数框架是为数组倒着来构建的，相当于自底向上把二叉树构建为二叉堆。

很不错的动图：

• https://www.runoob.com/w3cnote/heap-sort.html

构建新堆 logn

来看看真正的堆排怎么就可以在O(logn)的复杂度上贡献出新的最值！这就是堆排精髓的地方：在root不符合定义之后，并不需要把整棵树都重新构造一遍！想把它恢复为一个堆，只需要调整一个枝即可！假设之前的堆只是root被替换了，想要重新将其恢复为一个堆，只需要比较这一个root节点和它的子节点，如果不够大导致和子节点换了位置（下沉一层），继续和它的子节点比。最终比较的次数，是完全二叉树的高度，也就是logn。最坏情况，就是从顶层下沉logn层来到了底层，此时又成了一个正确的堆。这种构建堆的方法只需要O(logn)的复杂度！和一开始笨笨的构建堆的方法比起来，其实相当于这次只调整了整颗完全二叉树的“一枝”，而非整棵树。

所以：

1. 堆只需要和root的左右子树比较一下就知道谁是最小值了；
2. 而它能够稳定以O(1)的复杂度贡献一个最值的秘密就在于：root和最小子节点交换过后，我们继续让当前值下沉，把它继续构建为一个堆的时候，它只需要跟当前枝一直比下去，最多比的次数就是树的高度，而不需要考虑别的枝。每次恢复都是O(logn)，获取最值是O(1)，所以总体是O(logn)；

所以，堆排的完整思路是：

1. 初始化：创建一个最小/大堆，复杂度为O(nlogn)；
2. 堆排
   1. 每获取一个堆，就移除它的根节点（数组第0个数据），一共n次。（可以拿走，也可以把它放到本次用来构建堆的数据的最后，这样就不用开辟新数组了）
   2. 把刚刚的最后一个数据拿来放到新的堆的root，并利用上述“下沉”步骤构建一个完整的堆，复杂度为O(logn)

所以堆排最终的复杂度为O(n) * O(logn) + O(n) * O(logn) = O(nlogn)。

PriorityQueue

Java的PriorityQueue实现了heap。每当取出root，就要把最后一个数据放到root上重新做siftDown操作，就是把值一直下沉。不过它用的是while循环（当不需要siftDown或者siftDown的位置超出len/2时，就不需要循环了），而非递归，因为它是一个尾递归。反之，如果插入数据，就插入到最后一个位置，然后不断做siftUp，就是把值不断上升。

非“尾调用”之所以没法优化，是因为函数调用之后还有要执行的步骤，所以需要保存函数本身的上下文，这就是函数调用压栈弹栈的作用。而你怎么能把函数调用栈优化掉呢？

“尾调用可以优化”，因为后面反正也没啥要执行的了，直接把函数续上就行了。尾递归就是无限续杯，所以尾递归可以优化为while。

这就是堆的好处：无论是删数据还是插数据，只需要O(n)

如果用PriorityQueue实现排序，其实就是offer n个元素，再poll n次。

相关题型

最小k个数

最小k个数这一题，看看找出最小的k个数的复杂度：

• 如果先排序，再取前k个：nlogn
• 如果每轮取一个，取k轮（类似选择排序）：kn

二者不好比较大小，主要看k大还是logn大，如果k比较小，显然nk是合适的，毕竟n意味着数据规模可以无限大，k就是常数。

但是仔细想想kn这个算法，就像选择排序一样，第一轮比较完后，第二轮挑min的时候完全没利用上第一轮的信息，这样就多比较了很多次！能不能利用上呢？如果把之前挑的几个min值放在长度为k的队列里（排好序），那么之后每次和队列里最大的比就行了！小于最大的才需要入队。怎么找到队列里最大的？最大堆啊！让队列维持在k的长度，那么每次heapify只需要logk就行。

时间复杂度：n * logk，进一步缩小了常量。

    public int[] smallestK(int[] arr, int k) {

        if (k == 0) {
            return new int[]{};
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 0; i < arr.length; i++) {
            if (pq.size() < k) {
                pq.offer(arr[i]);
            } else {
                if (pq.peek() > arr[i]) {
                    pq.poll();
                    pq.offer(arr[i]);
                }
            }
        }

        // pq转int[]
        int[] result = new int[k];
        int i = 0;
        while (k-- > 0) {
            result[i++] = pq.poll();
        }

        return result;
    }

还有一种最快的思路，借助了快排的思想：pivot每次会给左右两边分个界，左边都是小的，右边都是大的。那么

• 如果pivot左边正好有k个，那这k个就是要求的k个（正好题目不要求这k个有序）；如果左边加上pivot正好有k个，那也不用排了，这k个就是要求的k个min；
• 如果pivot左边已经超k个了，那只需要排左边的就行了，左边排出k个。右边的都不用管，因为他们一定都比左边的大，不是要求的值；
• 如果左边加上pivot也不到k个，那说明右边还需要再排k - left.length个

class Solution {
    public int[] smallestK(int[] arr, int k) {

        quickSort(arr, 0, arr.length, k);
        return Arrays.copyOfRange(arr, 0, k);
    }

    // 在quicksort这一步产生了变异，不再是左右都排了，而是视情况而定
    private void quickSort(int[] array, int start, int end, int k) {
        int pivot = divide(array, start, end);
        if (pivot == -1) {
            return;
        }

        // 注意这里要看的是当前长度。pivot不是当前长度，pivot - start + 1才是
        // 如果把pivot + 1当成了长度，说明把start当成了0，但实际上并不是每一段的start都是0
        int length = pivot - start + 1;

        // 例如k=5，如果pivot左边（不含pivot，所以是length - 1）有5个数，那这5个一定就是最小的，直接结束
        // 如果加上pivot后（length）正好5个，也不用排了，这5个一定是最小的
        if (length - 1 == k || length == k) {
            return;
        }

        // 如果pivot左边（length - 1）就已经超了k，那就只排左边，排k个出来
        if (length - 1 > k) {
            quickSort(array, start, pivot, k);
        }

        // 如果加上pivot后（length）没超k，那就左边不用动了（反正也不要求有序，只要比较小就行），pivot也不用动了，
        // 右边离k还差k - length
        if (length < k) {
            quickSort(array, pivot + 1, end, k - length);
        }
    }

    // 确定pivot位置，算法不变
    private int divide(int[] array, int start, int end) {
        // 退出条件
        if (start >= end) {
            return -1;
        }

        // 设定基准值（pivot）的位置
        int pivotPos = start;
        // nextSwapPos是第n个交换的位置，也就是比pivot小的那n个元素的位置。用上面的例子来说，n最大为5
        int nextSwapPos = pivotPos + 1;
        
        for (int i = nextSwapPos; i < end; i++) {
            // 所有比pivot小的，依次从第二个位置开始放
            if (array[i] < array[pivotPos]) {
                swap(array, i, nextSwapPos);
                nextSwapPos++;
            }
        }

        // 最后把第一个位置的pivot换走就行
        int pivotPosition = nextSwapPos - 1;
        swap(array, pivotPos, pivotPosition);
        return pivotPosition;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

分析时间复杂度的话，想想快排划分后的空间，现在递归层次变浅了，因为有一半不需要管；每层比较次数也不到n了，反正就很快。据说时间复杂度的期望是O(n)，不好证明。

真是一道好题，加强了堆排的概念，更是加强了快排的概念。