【算法】排序算法

排序算法总结

	时间复杂度	空间复杂度	稳定性
选择排序	$O(n^2)$	$O(1)$	NO
冒泡排序	$O(n^2)$	$O(1)$	YES
插入排序	$O(n^2)$	$O(1)$	YES
归并排序	$O(NlogN)$	$O(N)$	YES
快速排序	$O(NlogN)$	$O(logN)$	NO
堆排序	$O(NlogN)$	$O(1)$	NO

插入排序的最优时间复杂度为 $O(N)$ ，并且是稳定的，适合于数据量小的场景。
快速排序的常数项经过试验是最低的，但是是不稳定的，适合于不需要稳定的数据量大的场景
堆排序的时间复杂度在常数项比快速排序略高，但空间复杂度较低，也是不稳定的
归并排序的空间复杂度是后三者中最高的，但是是稳定的
当元素个数小于 60 时：使用插入排序，插入排序是稳定的，并且最优时间复杂度为 O(N)
当元素个数大于 60 时：根据数据类型选择排序方式：
- 基础类型：使用快速排序，它的常数项经过试验是最低的，并且不需要保证稳定性
- 引用类型：使用归并排序，因为需要保证稳定性

选择排序

遍历数组的 i ～ N-1 范围内的元素，选出该范围内的最小值与 i 位置进行交换；重复上述过程 N-1 次直到完成排序。

总结：从前往后缩小范围遍历，选择当前范围内最小的数，放在当前范围的队首。队伍前面的数字都是排好序的小数，队伍后面的数字都是待排序的。

时间复杂度 O(N^2)
额外空间复杂度O(1)

代码：

public class SelectionSort {
  public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }

    for (int i = 0; i < arr.length; i++) {
      int minIndex = i;
      for (int j = i + 1; j < arr.length; j++) {
        // 寻找 i ~ N-1 位置上的最小值索引, 全部遍历完找到索引后再进行交换
        minIndex = (arr[minIndex] < arr[j]) ? minIndex : j;
      }
      swap(arr, i, minIndex);
    }
  }

  public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
  }
}

补充：一种交换数据a和b的方式：连续三次异或。前提是a和b在内存中处于不同的空间，并且 arr[a] 不能等于 arr[b]，否则得到的结果是0。

public void swap(int[] arr, int i, int j) {
  // 这种方式的弊端: arr[a] 和 arr[b] 不能相等
  arr[i] = arr[i] ^ arr[j]; 
  arr[j] = arr[i] ^ arr[j];
  arr[i] = arr[i] ^ arr[j];
}

冒泡排序

遍历数组 0～i 范围内的元素，比较当前元素与其后元素的大小，若当前元素较大则与其交换（像冒泡一样不断将比较大的元素向数组队尾移动），从而将该范围内的最大值元素后移放到 i 位置。

总结：从前往后缩小范围遍历，选择当前范围内最大的数，放在当前范围的队尾。队伍前面的数字都是待排序的，队伍后面的数字都是排好序的大数。

时间复杂度 O(N^2)
额外空间复杂度O(1)

代码：

package com.zhao;

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j+1])
                    swap(arr, j, j+1);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        // 这种方式的弊端: arr[a] 和 arr[b] 不能相等
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

冒泡排序优化：每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可

public static void bubble_v2(int[] a) {
    int n = a.length - 1;
    while (true) {
        int last = 0; // 表示最后一次交换索引位置，下次只需要遍历到这个位置就可以了，因为后面肯定是排好序的
        for (int i = 0; i < n; i++) {
            System.out.println("比较次数" + i);
            if (a[i] > a[i + 1]) {
                Utils.swap(a, i, i + 1);
                last = i;
            }
        }
        n = last;
        if (n == 0) {
            break;
        }
    }
}

插入排序

遍历 0 ～ i 范围内的元素，从后往前判断当前元素是否小于前一个元素，若小于则将该元素移动到当前位置，直到前一个元素小于当前元素，此时再将该元素插入到这个位置（其之前位置的元素都依次移动到了后面）。类似扑克牌中新来的牌不断判断与上一个牌的大小，直到将牌插入到符合条件的位置。

总结：从前往后遍历，将当前范围内的数字排好序，新来的数据插入到前面排好序的数字的适当位置中。队伍前面的数字都是排好序的小数，队伍后面的数字都是待排序的。

时间复杂度 O(N^2)
额外空间复杂度O(1)

最优情况下的时间复杂度为 O(N)

代码：

package com.zhao;

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        // i 代表待插入元素的索引
        for (int i = 1; i < a.length; i++) {
            int t = a[i]; // 代表待插入的元素值
            int j = i;
            System.out.println(j);
            while (j >= 1) {
                if (t < a[j - 1]) { // j-1 是上一个元素索引，如果 > t，后移
                    a[j] = a[j - 1];
                    j--;
                } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
                    break;
                }
            }
            a[j] = t;
            System.out.println(Arrays.toString(a) + " " + j);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        // 这种方式的弊端: arr[a] 和 arr[b] 不能相等
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

归并排序

归并排序 = 递归 + 合并的排序。

算法大致流程：

将整个数组平均划分为两部分
先将左侧的半个数组排序
再将右侧的半个数组排序
开辟一个和目标数组相同大小的数组空间
定义两个指针Left和Right，分别指向左侧数组和右侧数组的第一个元素，再定义一个指针i，指向新数组的第一个元素
不断遍历左右数组移动指针，判断Left和Right指向的元素大小：
1. 若Left小于等于Right，则将新数组的当前位置i赋值为Left指向的元素
2. 若Left大于Right，则将新数组的当前位置i赋值为Right指向的元素
不断执行步骤6，每次要么移动Left，要么移动Right，直到某一个指针达到数组末尾；再将另一半数组的后面的所有元素拷贝到新数组的末尾。

将整个数组递归执行上述 1-7 的过程，从完整的数组不断递归地平均拆分，直到递归到最底层的前一层：

process(arr, Left, Left+1)
process(arr, Left+1, Right)
merge(arr, Left, Right)

其中，Left = Right -2，process(arr, Left, Left+1) 里会将 [Left, Left+1] 范围内的两个数字进行排序, 再调用 process(arr, Left+1, Right)里会将 [Left+1, Right] 范围内的两个排序（此时 Left+1 位置上的数组已经经过了前一步的排序），因此归并排序最底层的合并排序只有两个数字进行比大小。（该过程可参考下文代码）

经过上述步骤后，即将 [Left, Left+1, Right] 范围内的三个数字进行了排序，递归开始返回，不断的将更大范围内的数组进行归并排序，直到递归返回到第二层时数组被分为了两半，左侧数组和右侧数组都进行了排序，再对二者进行一次 merge，即完成了整个数组的归并排序。

例如：第一条递归分支一直从 process(arr, 0, 2) --> process(arr, 0, 1) --> process(arr, 0, 0) + process(arr, 1, 1) + merge(arr, 0, 1, 0)。此时递归到了底部，process(arr, 0, 0) 和 process(arr, 1, 1) 都直接 return ，剩余 merge(arr, 0, 1, 0) 将合并左右数组 arr[0] 与 arr[1] 这两个数字，将二者合并到一个新的数组中。

递归行为的时间复杂度估算公式：

https://www.bilibili.com/video/BV13g41157hK?p=3

其中，b为数组被平均分的份数（二分归并排序算法里等于2），a为每次拆分时调用几个递归分支（二分归并排序算法里等于2），O(N^d) 为递归到底部时进行的操作的时间复杂度，根据不同的应用场景有不同的复杂度，例如在求数组最大值时，d=0；在归并排序里，d=1

举例：

在二分递归求数组最大值问题时，T(N) = 0.5 * T(N / 2) + O(1)
在数组二分归并排序问题时，T(N) = 0.5 * T(N / 2) + O(N)

根据上图中的计算公式，归并排序算法的时间复杂度为 O(N*log(N))

总结：归并排序就是不断递归地将数组拆分成更小的数组，直到最底层时拆分成的两个数组中每个数组只有一个数字，对这两个数字进行排序并合并后返回，不断返回后合并出的数组就越来越长，直到整个数组被合并排序。

归并排序的时间复杂度：

时间复杂度 O(N*log(N))
额外空间复杂度O(N)

代码：

package com.zhao;

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        process(arr, 0, arr.length-1);
    }

    public static void process(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        // 计算中点, 能避免范围溢出
        int mid = left + ((right - left) >> 1);

        // 两条递归分支
        process(arr, left, mid);
        process(arr, mid + 1, right);

        // 两条递归分支会一直递归到: 划分的两个数组各有一个元素, 将这两个元素进行排序并合并
        merge(arr, left, right, mid);
    }

    public static void merge(int[] arr, int left, int right, int mid) {
        int[] tmp = new int[right - left + 1];

        int i = 0;
        // 指向左数组的第一个
        int p1 = left;
        // 指向右数组的第一个
        int p2 = mid + 1;
        // 递归到最底部时，left == mid == right - 1。此时左数组为[left]；右数组为[right]

        // 双指针一起向右移动,将当前较小的元素拷贝到tmp中,只会有其中的某一个数组的指针先到数组尾部
        while (p1 <= mid && p2 <= right) {
            tmp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 将另一个数组的剩下所有元素拷贝到tmp中,只会有一个满足条件
        while (p1 <= mid) {
            tmp[i++] = arr[p1++];
        }
        while (p2 <= right) {
            tmp[i++] = arr[p2++];
        }

        // tmp中的元素拷贝回原数组
        for (int n = 0; n < tmp.length; n++) {
            arr[left + n] = tmp[n];
        }
    }
}

补充：使用递归的方法计算数组中最大值时，只需要将合并操作 merge 替换成求两个数字最大值的操作 Math.max(left, right)

归并排序的扩展：小和问题和逆序对问题

https://www.bilibili.com/video/BV13g41157hK?p=3

小和问题和逆序对问题本质上都是归并排序，二者是等价的。求每一个数左边比当前数小的数字的累积等价于求每一个数右边比当前数大的个数 * 自身大小。

不断递归拆分数组，直到递归返回、数组开始合并时：
在合并排序前使用双指针判断左侧数组当前元素是否小于右侧数组当前元素：
- 若小于，说明左侧当前元素比右侧数组当前元素之后的所有元素都要小（因为右侧数组都是排好序的，所以可以直接用索引数量计算出小和，不用再遍历判断大小了），那么就把左侧当前元素大小 * 右侧当前元素之后的元素数量，即可得到左侧当前元素相对右侧数组而言的的小和数
- 若等于，则此时不计算小和，把右侧数组的当前元素拷贝到临时数组中（之所以优先拷贝右侧是因为这样在排序后，之后的循环再比较大小时就不会把右侧数组中等于该元素大小的数字计算在内，因为相等的数字不在小和范围内）
- 若大于，则不计算小和，将右侧数组的当前元素拷贝到临时数组中，右侧指针移动，进入下一次循环
左右数组中的某一个遍历完毕后，即可将另一个数组的剩余元素拷贝到临时数组中，这之后的步骤就同归并排序一样了。

这种思想既不会漏算小和，又不会重算小和，因为某个元素只有在和右侧的数组 merge 时才会计算右侧数组内有几个数比其大，然后一旦 merge 后，其在合并后的组内就不会再去重复计算组内有没有比他大的。因此不会漏算，也不会重算。

小和问题的代码：

package com.zhao;

public class SmallSum {
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length-1);
    }

    public static int process(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }

        int mid = left + ((right - left) >> 1);
        // 返回三者的和
        return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, right, mid);
    }

    public static int merge(int[] arr, int left, int right, int mid) {
        int result = 0;

        int[] tmp = new int[right - left + 1];

        int i = 0;
        int p1 = left;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= right) {
            // 若当前元素arr[p1]小于右侧数组的当前元素arr[p2]
            // 计算小和 = 当前元素的大小 * 右侧数组当前所有往右的数字的个数
            // 因为右侧数组已经排好序了, 所以可以直接用索引个数计算小和, 而不用再遍历判断了
            result += arr[p1] < arr[p2] ? arr[p1] * (right - p2 + 1) : 0;

            // 计算完小和后进行合并排序, 将p1和p2中较小的那一个拷贝到tmp中
            // 相等的情况下优先把右侧数组的数字拷贝, 这样就能避免重复算的情况
            tmp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 后面就和归并排序一样了
        while (p1 <= mid) {
            tmp[i++] = arr[p1++];
        }
        while (p2 <= right) {
            tmp[i++] = arr[p2++];
        }

        for (int n = 0; n < tmp.length; n++) {
            arr[n + left] = tmp[n];
        }

        return result;
    }
}

逆序对问题的代码：

快速排序

快速排序前奏一：荷兰国旗问题

类似问题：将一个数组中奇数数字放到数组左边，偶数数字放到数组右边。

问题二：小于等于 num 的数放在数组的左边，等于 num 的数放在数组的中间，大于 num 的数放在数组的右边。

排序效果：像荷兰国旗一样，将数组分为三个区域，左侧区域为小于 num 的数字；中间区域为等于 num 的数字；右侧区域为等于 num 的数字。

本质是一种分区思想，将数组分为三个区域。

思路：

定义一个小于区域，在其内存储小于 num 的数字，定义一个大于区域，在其内存储大于 num 的数字，定义一个等于区域，在其内存储等于 num 的数字。
定义三个指针，一个指针 i 不断向右移动，另一个指针 left 指向小于区域右侧的下一个数字（该数字不在小于区域内），最后一个指针指向大于区域内最左侧的数字（该数字在大于区域内）。
遍历数组，判断当前元素 arr[i] 和 num 的大小关系：
- 如果 arr[i] 等于 num，则指针 i 右移一位，不做其他操作
- 如果 arr[i] 小于 num，则先将 i 位置的元素和 left 位置的元素（小于区域的右侧下一个元素）进行交换，然后指针 i 和 left 右移一位
- 如果 arr[i] 大于 num，则将 i 位置的元素和 right 位置的元素（大于区域内左侧的元素）进行交换，然后指针 right 左移一位，指针 i 不移动（因为右侧交换之后并不能确定右侧换过来的这个数是不是比 num 小，还需要再进下一次循环判断交换后的 i 位置的数字是否小于 num）
遍历的终止条件：i == right

代码：

public static void hollandFlag(int[] arr, int num) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int left = -1;           // 指向小于区域的最右位置
    int right = arr.length;  // 指向大于区域的最左位置

    for (int i = 0; i < arr.length;) {
        if (arr[i] < num) {
            // 令小于区域的右边下一个元素和当前元素交换, 两个指针都右移一位
            // 如果不交换, 则和 num 相等的区域中就会混杂着小于区域的数字
            // 因此为了区分小于区域和等于区域,必须要交换
            swap(arr, i++, ++left);
        } else if (arr[i] > num) {
            // 右侧只交换, i先不进行--, 因为右侧交换之后并不能确定右侧换过来的这个数是不是比num小
            // 还需要再进下一次循环判断交换后的i位置的数字是否小于num
            swap(arr, i, --right);
            System.out.println("right = " + right);
        } else {
            // arr[i] == num 时, i++, 不做其他操作
            i++;
        }

        // 判断当前的 i 是否已经等于了 right, 如果已经等于了, 说明双向奔赴结束
        if (i == right) {
            break;
        }
        System.out.println(Arrays.toString(arr));
    }
}

// 交换 a 和 b 位置上的元素
public static void swap(int[] arr, int a, int b) {
    if (a == b) {
        return;
    }

    // 这种方式的弊端: arr[a] 和 arr[b] 不能相等
    arr[a] = arr[a] ^ arr[b];
    arr[b] = arr[a] ^ arr[b];
    arr[a] = arr[a] ^ arr[b];
}

快速排序中同样使用这种分区的思想，并将该思想和递归操作合并。

快速排序前奏二：数组奇偶分离

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

借助这道题总结出分区类型题目的解决模板套路。注意下面 left 和 right 的设置方式：

public void exchange(int[] nums) {
    // 左边界内的 [... left] 都是奇数，left + 1 是交换的下一个
    int left = -1;
    // 右边界内的 [ right ...] 都是偶数， right - 1 是要交换的下一个
    int right = nums.length - 1;
    int cur = 0;

    // 当cur==right时，代表左分区和右分区都计算完毕，结束循环
    while (cur < right) {
        // 如果是奇数，和左分区的下一个 left + 1 交换
        if (nums[cur] & 1 == 1) { // 等价于 nums[cur] % 2 == 1
            swap(nums, left + 1, cur);
            // 交换后开始下一个位置判断
            cur++;
            left++;
        } else {
            // 如果是偶数，和右分区的下一个 right - 1 交换
            swap(nums, right - 1, cur);
            right--;
            // 右分区交换后不能cur++，还要进行下一轮的判断交换后的数字满不满足奇数
        }
    }
}

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

快速排序思想

快速.排序共有三个版本，版本一二分别对应了荷兰国旗中的问题一、问题二；版本三对应了问题二的随机取数字版本。

快速排序的思想是：递归 + 分区。即在递归过程中，首先将当前子数组进行分区，然后再在分好的小于区域内进行递归、接着在分好的大于区域内进行递归。这样最后递归完成时，整个数组就排好了序。

三个版本分区方式

版本一没有等于区域，小于等于 num 的数字都在小于区域，并且小于区域最右边的是等于的数
版本二加入了等于区域，将整个数组划分为了小于区域、等于区域和大于区域
版本三的分区方式与版本二相同，区别在于取 num 的方式变为了随机取。

在快速排序的某个分区中，每次比较的数字 num 为该分区中数组的某一个数字（版本一二中 num 为数组的最后一个元素，版本三中数字改为随机选取）

算法流程

选取一个数字作为 num 和其他数字比较。在版本一二中，该数字选取数组中的最后一个元素；版本三种该数字随机选取数组中的某一个元素
随机选取数字的具体实现方式为：在当前 [left, right] 范围内生成一个随机数索引值，并将该元素与当前范围内的 right 位置的元素进行交换，这样后续的分区方法内只用统一的用 arr[right] 进行比较即可
先将整个数组进行分区，得到小于区域、等于区域、大于区域。此时等于区域后续就不需要再排序了
接着递归地将小于区域和大于区域进行分区，同样分为小于区域、等于区域、大于区域
相当于小于区域内再继续划分，此时划分出来的数字肯定都比原数组里的等于区域小了，所以不会重复排序
递归完成后，每个划分好的子数组都完成了分区，这样整个数组就完成了排序

细节：其中，在分区后需要记录等于区域的左右边界，后续小于区域和大于区域内的递归划分需要用到这两个边界值，只在左右边界之外的区域内进行递归分区

关于取数字 num 的方式

版本二的快排本身已经足够优秀，但是因为可能人为制造糟糕数据（故意让最后一个元素最大，造成每次都要遍历所有元素），因此最坏情况的时间复杂度为 O(N^2)。

为了应付这种最坏情况，版本三的快排采用了随机取数字的方式：随机方式消除了极端情况，使得算法整体的时间复杂度为 O(N*logN)。

版本三的快速排序代码：

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 在当前区间内随机取一个索引, 令其与 arr[right] 交换
            // 这样分区方法内就可以统一用 arr[right] 进行比较了
            swap(arr, left + (int) (Math.random() * (right - left + 1)), right);

            System.out.println("after swap: " + Arrays.toString(arr));

            // 先分区
            int[] bound = partition(arr, left, right);
            // 需要一个变量存储当前等于区域的数字位置

            System.out.println("after partition: " + Arrays.toString(arr));

            quickSort(arr, left, bound[0] - 1);
            quickSort(arr, bound[1] + 1, right);
        }
    }

    // 分区: 就是荷兰国旗问题
    // 默认以 arr[right] 作为 num 进行比较
    // 返回等于区域的左右边界 bound[0] bound[1]
    public static int[] partition(int[] arr, int left, int right) {
        // i不断遍历, less指向小于区域的右边界, more指向大于区域的左边界
        int i = left;
        int less = left - 1;
        int more = right;

        // 保存 num 的值以免交换后被替换掉
        int num = arr[right];

        // 注意这里要 <= more, 边界条件有=
        // 因为 more 在上一次减一后指向的的元素不包含在大于区域内
        // 所以这个元素需要加入到循环中判断
        while (i <= more) {
            if (arr[i] < num) {
                // less 最后指向的是小于区域的右边界(在小于区域范围内)
                swap(arr, ++less, i++);
            } else if (arr[i] > num) {
                // more 最后指向的是大于区域的左边界(在大于区域范围外)
                swap(arr, i, more--);
            } else {
                i++;
            }
        }

        // 返回 等于区域 的左\右边界
        return new int[]{less + 1, more};
    }
}

快速排序的空间复杂度

最差情况是 O(N)，每一层递归都选在了最差的位置，占用了一个空间保存数据
最好的情况是 O(logN)，每一层递归都选在了比较好的中点位置，就会以一个二叉树的形式向下递归，同时每一层的空间都可以复用（左侧的数组分好区后，方法栈向上弹出，那个中点位置的空间就可以释放，让给右侧的数组压栈使用）

这个中点的位置即是上文代码中保存的每一次分区后等于区域的左右边界位置，其必须要记录，用于记录哪里是小于区域，哪里是大于区域，只在其内进行递归分区，这样就能保证不重复排序。

其作用是在递归调用结束后，方法栈弹出返回到当时调用它的母方法时，能够知道右侧哪个区域将要继续开始向下递归分区。因此这个中点数据的空间是不能省略的，必须要存在用来记录分区的边界

当采用随机取 num 的策略时，整体的空间复杂度就是 O(logN)

快速排序的扩展问题

只要有分区特性（数字按照某种0/1规则分成两/三个区）的题目都可以用快排来做。

快速排序的常见题目

最小的 K 个数

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/

剑指 Offer 40. 最小的k个数：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

方法一：堆

我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。

代码：

// 1. 大根堆不断维护当前小的k个数字，当来新的数字，如果比堆顶大
//（比当前k个小数里的最大的小，说明这个最大的堆顶肯定不在答案里了），弹出堆顶
public int[] getLeastNumbers01(int[] arr, int k) {
    // 注意！！将系统默认的小根堆改成大根堆
    Queue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int i = 0; i < arr.length; i++) {
        if (i < k) {
            maxHeap.offer(arr[i]);
        } else {
            if (maxHeap.peek() > arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            } 
        }
    }

    int[] res = new int[k];
    int i = 0;
    // 弹出前k个元素
    while (!maxHeap.isEmpty()) {
        res[i++] = maxHeap.poll();
    }
    return res;
}

方法二：快排思想

快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。

我们定义函数 randomized_selected(arr, l, r, k) 表示划分数组 arr 的 [l,r] 部分，使前 k 小的数在数组的左侧，在函数里我们调用快排的划分函数，假设划分函数返回的下标是 pos（表示分界值 pivot 最终在数组中的位置），即 pivot 是数组中第 pos - l + 1 小的数，那么一共会有三种情况：

如果 pos - l + 1 == k，表示 pivot 就是第 kk 小的数，直接返回即可；
如果 pos - l + 1 < k，表示第 kk 小的数在 pivot 的右侧，因此递归调用 randomized_selected(arr, pos + 1, r, k - (pos - l + 1))；
如果 pos - l + 1 > k，表示第 kk 小的数在 pivot 的左侧，递归调用 randomized_selected(arr, l, pos - 1, k)。

函数递归入口为 randomized_selected(arr, 0, arr.length - 1, k)。在函数返回后，将前 k 个数放入答案数组返回即可。

代码：

// 2. 改进版快排
public void quickSearch(int[] arr, int left, int right, int k) {
    // 以pos为分界线，左侧都小于等于该值，右侧都大于该值
    int pos = randomPartition(arr, left, right);

    // 如果前number个元素正好是前k个，则完成了排序，返回
    // 此时前面有 pos + 1 个元素
    if (pos == k - 1) {
        return;
    } else if (pos > k - 1) {
        // 如果k在number左边，则只需要对左侧进行分区
        quickSearch(arr, left, pos - 1, k);
    } else {
        // 如果k在number右边，则number左边的都是答案，只需要对右侧进行分区
        quickSearch(arr, pos + 1, right, k);
    }
}

public int randomPartition(int[] arr, int left, int right) {
    swap(arr, left + (int)(Math.random() * (right - left + 1)), right);
    return partition(arr, left, right);
}

public int partition(int[] arr, int left, int right) {
    // l：左侧区域的最右元素
    int l = left - 1;
    // r：右侧区域的最左元素
    int r = right + 1;
    // 二者一开始都为空，所以在数组范围之外

    int cur = left;
    int num = arr[right];

    // cur == r 时，cur就已经在右侧区域内了
    while (cur < r) {
        if (arr[cur] < num) {
            swap(arr, ++l, cur++);
        } else if (arr[cur] > num) {
            swap(arr, --r, cur);
        } else {
            cur++;
        }
    }
    return cur - 1;
}

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

堆排序

堆结构

堆结构本身比堆排序要重要

堆结构就是用数组实现的完全二叉树结构。

堆结构的节点公式：

节点 i 的父节点为 (i - 1) / 2（左右节点都可以统一用这个公式）
节点 i 的左子节点为 2 * i + 1
节点 i 的右子节点为 2 * i + 2

使用上述公式即直接定位到某个节点的父/子节点

大/小根堆

大根堆：堆中的每一个父节点都要比其子节点上的数字大（不考虑其对称的另一侧分支里的节点数字大小）。
小根堆：堆中的每一个父节点都要比其子节点上的数字小（不考虑其对称的另一侧分支里的节点数字大小）。

堆结构最重要的两个操作：

heapInsert：add 操作，新增一个数据到已知堆中。具体做法是新增的数据不断向上遍历堆结构，将数字插入到合适的父节点位置
heapify：poll 操作，弹出堆里第一个元素（根节点）的值，并重新调整堆结构，令其余部分的元素继续保持大/小根堆结构。具体做法是新的根结点的元素不断向下遍历堆结构，交换其到合适的子节点位置

heapInsert：add 操作。用于新增一个数据到堆中，当新来一个数字时，将其添加到堆结构中，并且满足大根堆（或小根堆）：向上遍历他的每一个父节点，判断其是否大于它的父节点，若大于则和父节点交换，若小于则停止遍历。直到当前数字放到合适的父节点位置，使得当前堆满足大根。

heapify：poll 操作。用于弹出堆中第一个元素，并令其余部分继续保持大/小根堆结构，若用户要求返回并删除当前大根堆的最大元素，并且要求删除后的其他元素依旧符合大根堆：返回当前堆的第一个节点（其肯定是最大元素），然后将当前堆的最后一个元素放到第一个元素的位置。之后开始向下遍历第一个元素的子节点，选出其子节点中最大的数字，并且判断该数字和自身的大小，若子节点数字更大，则交换自身和子节点，若子节点数字更小，则停止遍历；直到该元素被放到合适的子节点位置。

这两个操作的空间复杂度都是 O(logN)，因为 N 个节点的完全二叉树的高度为 O(logN)，上述两个操作都只需要遍历二叉树中的某一条分支即可，因此时间只有 O(logN)

heapInsert 的代码：

public static void heapInsert(int[] arr, int index) {
  // 向上遍历当前节点的父节点,直到满足条件: 父节点的值 > 当前节点的值
  while (arr[(index - 1) / 2] < arr[index]) {
    swap(arr, (index - 1) / 2, index);
    index = (index - 1) / 2; // index 记得变为父节点的值
  }
}

heapify 的代码：

// heapSize 用于表示逻辑上的堆的大小, 其和数组的大小没关系
// 该方法的作用是, 在给定堆结构中, 当某个位置的元素被弹出,替换成了其他数字后
// 要保证新的数组仍然保持堆结构, 那么就需要从这个位置开始向下遍历
// 交换其子节点中最大的元素
public static void heapify(int[] arr, int index, int heapSize){
    if (heapSize > arr.length) {
        return;
    }

    while (2*index+1 < heapSize) {
        // 两个孩子中, 判断谁的值更大
        int largest = (2*index+2 < heapSize) && arr[2*index+1] < arr[2*index+2]
            ? 2*index+2 : 2*index+1;

        // 当前节点和子孩子中, 判断谁的值更大
        largest = arr[index] < arr[largest] ? largest : index;

        // 如果相等, 说明此时已经满足了大根堆的条件, 可以跳出循环
        if (largest == index) {
            break;
        }

        // 交换
        swap(arr, index, largest);
        index = largest;
    }
}

具体应用

若用户要求修改堆结构中任意一个位置的元素的值，并要求修改后的数字仍然满足大根堆，则只需要判断修改后的元素是比原先大还是小：

若修改后的元素比原先大，则进行 heapInsert 操作，将当前元素向上交换到合适的父节点位置
若修改后的元素比原先小，则进行 heapify 操作，将当前元素向下交换到合适的子节点位置

小根堆在 Java 中就是优先级队列默认的实现方式： PriorityQueue<Interger>，其两个方法：

add() ：本质上就是 heapInsert 操作，将一个数字添加到已存在的小根堆中
poll()：本质上就是 heapify 操作，首先弹出当前小根堆的根结点元素，并令剩余数字依旧保持小根堆结构。

但是其不能支持“修改堆中某个结构后以很轻的代价重新调整堆的结构”，只支持“弹出堆的根结点元素后重新调整堆的结构”，若想实现这些个性化的功能还需要自己定义堆结构。

其扩容机制是当 heapSize 快满时，将 heapSize * 2。这个操作的时间复杂度在每个元素平摊下来后其实很低

堆排序思想

堆排序的思想是：利用大根堆第一个元素最大的特性，令数组不断地组成大根堆，从而每次形成的大根堆里的第一个元素都是当前的最大值。

算法流程：

首先令当前数组的所有数字符合大根堆顺序（令一个数组变成大根堆的方式见后文，本质上就是不断做 heapInsert）
当前大根堆的根节点就是最大的元素，将其与数组的最后一个元素交换位置，此时即得到了整个数组最大的元素
接着将 heapSize–（因为已经有一个数字排好了序，heapSize 将减小），并对交换后的元素进行一次 heapify 操作：不断向下遍历子节点，直到与合适的位置数字进行交换。heapify 后，新的堆就又符合了大根堆结构
再取当前大根堆的根节点上的元素，它就是原数组第二大的数字，将其与大根堆结构中最后一个节点的元素进行交换。此时原数组中最后两个位置的元素就是最大和第二大的元素
再次 heapSize-- ，并对交换后的元素再进行一次 heapify 操作，新的大根堆的根结点的元素就是第三大的元素，将其与大根堆结构中最后一个节点的元素进行交换。
重复上述过程，直到大根堆的 heapSize == 0，此时即完成了排序

堆排序的复杂度：

时间复杂度是 O(N * logN)
额外空间复杂度 O(1)，只需要 swap 交换操作，不用开辟额外空间

代码：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    // 1. 先将数组变为大根堆
    // 1.1 方式一: 依次将每个数字添加到堆结构中, 堆大小从0开始, 依次将新数字 heapInsert 进堆中
    // 编码思路是, 从前往后将每个节点进行 heapInsert
    // 其时间复杂度为 O(N*logN)
    for (int i = 0; i < arr.length; i++) {  // O(N)
        heapInsert(arr, i);                   // O(logN)
    }

    // 1.2 方式二: 从下向上, 先将每个子堆变为大根堆, 然后再将其父节点纳入再进行 heapify
    // 编码思路是, 从后往前将每个节点进行 heapify
    // 该方法速度更快, 其时间复杂度为 O(N)
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }

    // 2. 每次将大根堆的根结点元素与最后一个元素交换
    int heapSize = arr.length;
    while (heapSize > 0) {                    // O(N)
        swap(arr, 0, heapSize-1);             // O(1)
        // 注意 heapSize 先减一再进入 heapify
        heapify(arr, 0, --heapSize);          // O(logN)
    }
    // 整体时间复杂度为 O(N*logN)
}

public static void heapInsert(int[] arr, int index) {
    // 向上遍历当前节点的父节点,直到满足条件: 父节点的值 > 当前节点的值
    while (arr[(index - 1) / 2] < arr[index]) {
        swap(arr, (index - 1) / 2, index);
        index = (index - 1) / 2; // index 记得变为父节点的值
    }
}

// heapSize 用于表示逻辑上的堆的大小, 其和数组的大小没关系
// 该方法的作用是, 在给定堆结构中, 当某个位置的元素被弹出,替换成了其他数字后
// 要保证新的数组仍然保持堆结构, 那么就需要从这个位置开始向下遍历
// 交换其子节点中最大的元素
public static void heapify(int[] arr, int index, int heapSize){
    if (heapSize > arr.length) {
        return;
    }

    while (2*index+1 < heapSize) {
        // 两个孩子中, 判断谁的值更大
        int largest = (2*index+2 < heapSize) && arr[2*index+1] < arr[2*index+2]
            ? 2*index+2 : 2*index+1;

        // 当前节点和子孩子中, 判断谁的值更大
        largest = arr[index] < arr[largest] ? largest : index;

        // 如果相等, 说明此时已经满足了大根堆的条件, 可以跳出循环
        if (largest == index) {
            break;
        }

        // 交换
        swap(arr, index, largest);
        index = largest;
    }
}

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

    arr[a] = arr[a] ^ arr[b];
    arr[b] = arr[a] ^ arr[b];
    arr[a] = arr[a] ^ arr[b];
}

补充：想让一组数字变成一个大根堆/小根堆结构，上文中的编码方式时间复杂度是 O(N * logN)。然后还有一种更快的方式令一个数组变为大根堆/小根堆结构，其时间复杂度为 O(N)

方式一：依次将每个数字添加到堆结构中，堆大小从0开始，依次将新数字 heapInsert 进堆中。当遍历完成后，即得到了大根堆，但这种方法的时间复杂度为 O(N * logN)
方式二：从下向上，先将每个子堆变为大根堆，然后再将其父节点纳入再进行 heapify。其时间复杂度为 O(N)（其时间复杂度的估计方法使用了错位相减法）

方式二就是一种逆向思维，反过来从后往前遍历数组，令其往后的子树符合大根堆，然后再向前遍历，不断扩大子树的大小，令新的子树也符合大根堆。这样的操作时间复杂度更低，因为整个树上一半的节点都是叶子节点，根本不需要做交换：

代码：

// 1. 先将数组变为大根堆
// 1.1 方式一: 依次将每个数字添加到堆结构中, 堆大小从0开始, 依次将新数字 heapInsert 进堆中
// 编码思路是, 从前往后将每个节点进行 heapInsert
// 其时间复杂度为 O(N*logN)
for (int i = 0; i < arr.length; i++) {  // O(N)
    heapInsert(arr, i);                   // O(logN)
}

// 1.2 方式二: 从下向上, 先将每个子堆变为大根堆, 然后再将其父节点纳入再进行 heapify
// 编码思路是, 从后往前将每个节点进行 heapify
// 该方法速度更快, 其时间复杂度为 O(N)
for (int i = arr.length - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
}

堆排序的扩展：几乎有序的数组

解题思路：这个移动距离不超过 k 非常重要，这意味着我们可以在 k 范围内组成一个小根堆，这个小根堆的第一个元素就是这个范围内的最小值，依次移动指针，将每个子 k 区域内的数组组成小根堆，即可不断得到当前范围内的最小值，从而完成排序。

具体流程：

首先取数组的前 k 个数字，组成小根堆（复杂度为 O(k * logk)，或用更快的方式可以达到 O(k)），然后将小根堆第一个位置的元素弹出，放到原数组的0位置，这个数就是整个数组的最小值（因为这道题限制了每个数字的移动距离不会超过 k）
接着向后移动1个位置，再取 k+1 位置上的数 arr[k+1] 与上一步剩下的 k-1 个元素一起再组成新的小根堆后，再取出最新小根堆里的第一个元素（此元素就是整个数组第二小的数）

重复上述过程，直到整个数组被遍历完，即可得到排序后的数组。此过程的时间复杂度为 O(N * logk)，如果这个k很小，那么这个算法的时间复杂度就比较接近 O(N)

具体实现既可以通过自己定义堆结构，又可以直接使用 Java 提供的优先级队列：PriorityQueue<Interger>，其底层就是一个小根堆结构。

小根堆在 Java 中就是优先级队列默认的实现方式： PriorityQueue<Interger>，其两个方法：

add() ：本质上就是 heapInsert 操作，将一个数字添加到已存在的小根堆中
poll()：本质上就是 heapify 操作，首先弹出当前小根堆的根结点元素，并令剩余数字依旧保持小根堆结构。

其扩容机制是当 heapSize 快满时，将 heapSize * 2。这个操作的时间复杂度在每个元素平摊下来后其实很低

使用 PriorityQueue<Interger> 解该题：

package com.zhao;

import java.util.Arrays;
import java.util.PriorityQueue;

public class SortArrayDistanceLessK {
    public static void sortArrayDistanceLessK(int[] arr, int k) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 默认为小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 0 ~ k-1 位置上的数组成小根堆(这里要取k和arr.length的最小值)
        for (int i = 0; i < Math.min(k, arr.length); i++) {
            heap.add(arr[i]);
        }

        int i = 0;
        for (; i < arr.length - k; i++) {
            arr[i] = heap.poll();
            // 注意索引值不是 i+k+1
            // 因为整个小根堆的heapSize==k, 所以 "当前根节点索引+k" 就是小根堆的下一个索引值
            heap.add(arr[i + k]);
        }

        // 上述遍历完毕后, 将大根堆里剩余的数挨个弹出放到数组的最后k个位置
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,1,5,4,6,8,7};

        SortArrayDistanceLessK.sortArrayDistanceLessK(arr, 3);
        System.out.println(Arrays.toString(arr));
    }
}

桶排序

https://www.bilibili.com/video/BV13g41157hK?p=4

词频表 count[10] 中统计某一位小于等于当前数字的个数有多少个，例如下图中，count 数组中 count[2] = 4，代表原数组中个位数小于等于2的数字有4个（21，11，52，62）

这个数组存在的意义是，可以通过其索引上的数字为原数组某一位进行分片，例如按照个位数字的大小按顺序排列，例如下图中的辅助数组 help[] 就是使用 count 数组将原数组按照个位数字的大小进行分片排序，让个位数字为1的在一起，为2的在一起……：

遍历流程：从右往左遍历原数组，将遇到的每一个数字放到辅助数组的 help[count[i]-1] 位置，并且将 count[i]-- 。

结合上面两幅图，举例说明这样做的原因：

例如先按照个位进行分片排序：从右往左遍历到62时，当前数字62肯定是“某一位（个位）上数值相同的数字”中排序最靠后的，因此就将其放到 help 数组中“这一位（个位）所处的分片区域”的最靠后位置 help[count[i]-1] ，即 help[3]。

因为根据 count 数组可知，个位数字小于等于2的数字一共有4个，那么当前从右往左遍历到的数字62就应该是这四个数里的最后一个，即 help[count[2]-1]。

记得接下来要将 count[2]-- ，这样再往左遍历到下一个元素52时，这个排序更靠前一些的数字52就会放到62的前面 help[count[2]-1] = help[2]。

这样做的目的是，让先入桶的先出桶，达到队列的效果。