@[toc] --- ## 稳定排序 稳定排序指的是**在排序过程中，相同元素的相对位置不会改变**。具体来说，如果原序列中有两个相同的元素，它们的位置关系是a在b前面，而在排序后，a和b的位置关系仍然是a在b前面 ### 插入排序 插入排序是一种简单的排序算法，它的核心思想是**将未排序的元素依次插入到已排序的序列中的合适位置**，从而构建出完整的有序序列。其实现方式类似于我们打扑克牌时的整理方法，将新摸到的牌插入到已有的牌中的合适位置。 下面是插入排序的基本思路： 1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素（也就是未排序序列的第一个元素），在已经排序的元素序列中从后向前扫描 3. 如果已排序的元素大于新元素，则将该元素移到下一个位置 4. 重复步骤 3，直到已排序的元素小于或等于新元素 5. 将新元素插入到该位置后 6. 重复步骤 2~5，直到所有元素均被排序完毕 下面是插入排序的代码示例： ```java public class InsertionSort { public static void sort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // 移动比 key 大的元素到其后面一位 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // 将 key 插入到正确的位置 arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {5, 2, 4, 6, 1, 3}; sort(arr); System.out.println(Arrays.toString(arr)); // 输出：[1, 2, 3, 4, 5, 6] } } ``` 插入排序的平均时间复杂度为 $O(n^2)$。最好情况下，当输入的数组已经有序时，插入排序的时间复杂度为 $O(n)$，最坏情况下，当输入的数组逆序时，插入排序的时间复杂度为 $O(n^2)$。 插入排序的优点是简单易懂，实现较为容易，对于小规模的数据集具有较好的性能。然而，对于大规模数据集来说，插入排序的时间复杂度较高，不如其他高级排序算法如快速排序、归并排序等。 ### 冒泡排序 冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，**一次比较两个元素，如果他们的顺序错误就把他们交换过来**。走访数列的工作是**重复地进行直到没有再需要交换，也就是说该数列已经排序完成**。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。 ```java public void bubbleSort(int[] nums) { if (nums == null || nums.length <= 1) { return ; } // 只需要排 nums.length - 1 次（而不是 nums.length 次） for (int i = 0; i < nums.length - 1; i ++) { // flag 表示该次冒泡排序是否存在交换操作，如果没有，说明数组已经全局有序了 boolean flag = false; for (int j = 0; j < nums.length - 1; j ++) { if (nums[j] > nums[j + 1]) { flag = true; int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } if (!flag) { break; } } } ``` 平均时间复杂度 O(N^2) 最好情况（全局有序）：O(N) ### 归并排序 归并排序是一种基于**分治法**的排序算法。为了排序长度为n的数组，需要先排序两个长度为n/2的子数组，然后合并这两个排序的子数组，于是整个数组也就排序完毕。 归并排序可以用迭代代码实现。例如，输入一个长度为8的数组[4，1，5，6，2，7，8，3]，可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组，然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组，最后合并相邻的长度为4的子数组，此时整个数组排序完毕 <img src="https://cs-wiki.oss-cn-shanghai.aliyuncs.com/img/20220314092756.png" style="zoom:50%;" /> ```java class Solution { public int[] sortArray(int[] nums) { mergeSort(nums, 0, nums.length - 1); return nums; } // 归并排序 nums[l, r] public void mergeSort(int[] nums, int l, int r) { if (l >= r) { return; } int mid = l + ((l + r) >> 1); // 1. 归并排序 nums[l, mid]; mergeSort(nums, l, mid); // 2. 归并排序 nums[mid + 1, r]; mergeSort(nums, mid + 1, r); // 3. merge nums[left, mid] 和 nums[mid + 1, right] 两个数组 merge(nums, l, r); } private void merge(int[] nums, int l, int r) { // temp 是汇总 2 个有序区的临时区域 int[] temp = new int[r - l + 1]; // tmp 下标 int index = 0; int mid = l + ((r - l) >> 1); int i = l; int j = mid + 1; while (i <= mid && j <= r) { if (nums[i] <= nums[j]) { temp[index ++] = nums[i ++]; } else { temp[index ++] = nums[j ++]; } } while (i <= mid) { temp[index ++] = nums[i ++]; } while (j <= r) { temp[index ++] = nums[j ++]; } // 将排序后的到数组 nums 中 for (int k = 0; k < temp.length; k ++) { nums[l + k] = temp[k]; } } } ``` 由于长度为 n 的数组每次都被分为两个长度为 n/2 的数组，因此不管输入什么样的数组，归并排序的时间复杂度都是 $O(nlogn)$。归并排序需要创建一个长度为 n 的辅助数组。如果用递归实现归并排序，那么递归的调用栈需要 $O(logn)$ 的空间。因此，归并排序的空间复杂度是 $O(n)$。 手写归并排序的代码本身就是很常见的面试题。因此，应深刻理解归并排序的过程，熟悉归并排序的迭代和递归的代码实现。同时，归并排序是应用分治法来解决问题的，类似的思路可以用来解决很多其他的问题 ### 计数排序 计数排序是一种线性时间的整数排序算法。<u>如果数组的长度为n，整数范围（**数组中最大整数与最小整数的差值**）为k，对于 **k 远小于 n** 的场景（如对某公司所有员工的年龄排序），那么计数排序的时间复杂度优于其他基于比较的排序算法</u>（如归并排序、快速排序等）。 ⭐ 计数排序的基本思想是**先统计数组中每个整数在数组中出现的次数，然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中**。 例如，如果输入整数数组[2，3，4，2，3，2，1]，扫描一次整个数组就能知道数组中1出现了1次，2出现了3次，3出现了2次，4出现了1次，于是先后在数组中填入 1 个1、3 个 2、2 个 3及 1 个4，就可以得到排序后的数组 [1，2，2，2，3，3，4]。 ```java public int[] sortArray(int[] nums) { // 数组中最大整数与最小整数（用来计算整数范围） int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int num : nums) { min = Math.min(min, num); max = Math.max(max, num); } // 根据整数范围 max - min 来构建数组 counts[] // 统计数组中数字出现的次数 count[num - min] 对应 num 出现的次数 int[] counts = new int[max - min + 1]; for (int num : nums) { counts[num - min]++; } int i = 0; for (int num = min; num <= max; num ++) { while (counts[num - min] > 0) { // 原地修改 nums 数组 nums[i ++] = num; // num 对应的出现次数 -- counts[num - min] --; } } return nums; } ``` 上述代码先扫描数组nums得到整数的最大值和最小值，并根据整数范围创建辅助数组counts。数组counts用来统计每个整数出现的次数。 如果数组的长度为 n（第一个循环时间复杂度 O(n)），整数的范围为 k（第一个循环时间复杂度 O(k)），那么计数排序的时间复杂度就是 $O(n+k)$。由于需要创建一个长度为 $O(k)$ 的辅助数组counts，因此空间复杂度为 $O(k)$。 - 当 k 较小时，无论从时间复杂度还是空间复杂度来看计数排序都是非常高效的算法。 - 当k很大时，计数排序可能就不如其他排序算法（如快速排序、归并排序）高效。 ## 不稳定排序 ### 选择排序 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 重复第二步，直到所有元素均排序完毕。 ```java public void sort(int[] nums) { if (nums == null || nums.length <= 1) { return ; } // 只需要排 nums.length - 1 次（而不是 nums.length 次） for (int i = 0; i < nums.length - 1; i ++) { // 从前往后找到比 nums[i] 小的最小数 int min = i; for (int j = i + 1; j < nums.length; j ++) { if (nums[j] < nums[min]) { min = j; } } if (min != i) { int temp = nums[i]; nums[i] = nums[min]; nums[min] = temp; } } } ``` 选择排序无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。 ### 快速排序 快速排序是一种非常高效的算法，从其名字可以看出这种排序算法最大的特点就是快。当表现良好时，快速排序的速度比其他主要对手（如归并排序）快2～3倍。 快速排序的基本思想是**分治法**，排序过程如下： - 在输入数组中随机选取一个元素作为中间值（pivot），然后对数组进行分区（partition），使所有比中间值小的数据移到数组的左边，所有比中间值大的数据移到数组的右边。 - 接下来对中间值左右两侧的子数组用相同的步骤排序，直到子数组中只有一个数字为止。 这个过程可以用如下所示的递归代码实现： ```java // sort nums[left, right] private void quickSort(int[] nums, int left, int right) { if (left >= right) { return ; } // 选取基准元素下标 int pivot = partition(nums, left, right); quickSort(nums, left, pivot - 1); quickSort(nums, pivot + 1, right); } ``` 上述算法中的 `Partition` 以一个确定的基准元素对数组进行划分，将该基准元素放在最终所在的位置（使所有比基准元素小的数据移到数组的左边，所有比基准元素大的数据移到数组的右边）： ```java // 选取基准元素下标 private int partition(int[] nums, int left, int right) { if (left == right) { return left; } // 一般都是用最左元素作基准元素 int pivot = left; while (left < right) { while (left < right && nums[right] >= nums[pivot]) { right --; } while (left < right && nums[left] <= nums[pivot]) { left ++; } // 交换 if (left < right) { swap(nums, left, right); } } // 将基准数放到最终的位置（基准数归位） swap(nums, pivot, left); return pivot; } private void swap(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } ``` > 注意下图中框出来的符号： > >  我们可以引入**随机化**来加速快排的过程。<u>所谓随机化就是随机 pivot 的取值（并非固定的最左边的数），可以在循环一开始的时候，随机交换第 1 个元素（最左边的元素）与它后面的任意 1 个元素的位置</u>： ```java int index = left + new Random().nextInt(right - left + 1); swap(nums, left, index); int pivot = left; ``` 快排在最坏情况下时间复杂度为 `O(n^2)`，最好情况下为 `O(nlogn)`，平均情况下也是 `O(nlogn)` > 快速排序中的 partition 函数经常被用来选择数组中第k大的数字，这是一道非常经典的算法面试题 ### 堆排序 堆排序是一种基于比较的排序算法，它利用了堆这种数据结构来实现排序。堆是一种完全二叉树，它分为最大堆和最小堆两种形式。在最大堆中，每个节点的值都大于或等于它的子节点；而在最小堆中，每个节点的值都小于或等于它的子节点。 堆排序的核心思想是**将待排序的序列构建成一个最大堆，然后将堆顶元素（即最大值）和序列的最后一个元素交换位置，然后将除最后一个元素外的序列重新构建成最大堆，重复执行这个过程直到整个序列有序**。 Java 代码示例： ```java public class HeapSort { public static void sort(int[] arr) { int n = arr.length; // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 从最后一个元素开始依次将堆顶元素和序列最后一个元素交换 for (int i = n - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 重新构建最大堆 heapify(arr, i, 0); } } // 将指定位置的节点进行堆化 private static void heapify(int[] arr, int n, int i) { int largest = i; // 最大值的位置 int left = 2 * i + 1; // 左孩子的位置 int right = 2 * i + 2; // 右孩子的位置 // 如果左孩子比最大值大，则更新最大值的位置 if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右孩子比最大值大，则更新最大值的位置 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值的位置不是 i，则交换 i 和最大值的位置，然后继续堆化最大值所在的节点 if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } } ``` 时间复杂度为 O(nlogn)，其中构建最大堆的时间复杂度为 O(n)，重构最大堆的时间复杂度为 O(logn)，一共进行 n 次重构，因此总时间复杂度为 O(nlogn)。 ## 总结对比 下表展示了常见排序算法的平均时间复杂度、最好时间复杂度和最坏时间复杂度： | 算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 是否稳定 | | -------- | -------------- | -------------- | -------------- | -------- | | 插入排序 | O(n^2) | O(n) | O(n^2) | 稳定 | | 冒泡排序 | O(n^2) | O(n) | O(n^2) | 稳定 | | 归并排序 | O(n log n) | O(n log n) | O(n log n) | 稳定 | | 计数排序 | O(n+k) | O(n+k) | O(n+k) | 稳定 | | 选择排序 | O(n^2) | O(n^2) | O(n^2) | 不稳定 | | 快速排序 | O(n log n) | O(n log n) | O(n^2) | 不稳定 | | 堆排序 | O(n log n) | O(n log n) | O(n log n) | 不稳定 | 其中，n 表示待排序元素的数量，k 表示数据的取值范围。