【算法】内部排序

清疚 2023-10-07 22:56 8阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *   *  2.1.比较类排序
     *   *  2.1.1.交换排序
         *   *  2.1.1.1.冒泡排序
             *  2.1.1.2.快速排序
         *  2.1.2.插入排序
         *   *  2.1.2.1.直接插入排序
             *  2.1.2.2.折半插入排序
             *  2.1.2.3.希尔排序
         *  2.1.3.选择排序
         *   *  2.1.3.1.简单/直接选择排序
             *  2.1.3.2.堆排序
         *  2.1.4.归并排序
         *   *  2.1.4.1.二路归并排序
             *  2.1.4.2.二路归并排序递归版
     *  2.2.非比较类排序
     *   *  2.2.1.基数排序
 *  3.总结
 *  4.其它

> 本文参考：  
> 《数据结构教程》第 5 版 李春葆 主编

## 1.概述 ##

（1）**排序(sort)是计算机内经常进行的一种操作，即指将一组“无序”的记录序列按照其关键字调整为递增**或**递减**的**有序记录序列**。为了方便起见，本文仅讨论递增排序的情况。

（2）若整个排序过程都放在内存中处理，排序时不涉及数据的内、外存交换，则称之为**内部排序(internal sort)**；反之，则称为**外部排序(external sort)**。显然，内排序适用于元素个数不多的情况，而外排序则适用于元素个数很多，不能一次性将其全部放入内存的情况。内排序是外排序的基础，本文只讨论内排序，并且下文将内排序统称为排序。

（3）当待排序元素的关键字均不相同时，显然排序结果是唯一的，否则排序的结果不一定唯一。如果待排序的表中**存在有多个关键字相同的元素**，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是**稳定的 (stable)**；反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法**是不稳定的 (unstable)**。注意，排序算法的稳定性是针对所有输入实例而言的。也就是说，在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

（4）排序算法通常可以分成以下两大类：

*  **比较类排序**：通过比较来决定元素的相对次序，由于其平均时间复杂度不能低于 O(nlog2n)，所以也称为**非线性时间比较类排序。**
 *  **非比较类排序**：不通过比较来决定元素间的相对次序，可以以**线性时间**运行，因此也称为线性时间**非比较类排序**。

（5）具体的分类细节如下图所示：  
![在这里插入图片描述][b14cbc70a5c24ca8b94206f70f6fb494.png]

## 2.代码实现 ##

### 2.1.比较类排序 ###

#### 2.1.1.交换排序 ####

交换排序的基本思想时两两比较待排序元素的关键字，发现这两个元素的次序相反即可进行交换，直到没有反序的元素为止。本届介绍两种交换排序算法：**冒泡排序**和**快速排序**。

##### 2.1.1.1.冒泡排序 #####

（1）冒泡排序 (bubble sort) 也称为**气泡排序**，其基本思想时通过**无序区**中相邻元素关键字间的比较和位置的交换使关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”，如下图所示：  
![在这里插入图片描述][13785dbbad404d54a26cc95f502c178c.png]

注意：冒泡排序每趟产生的有序区一定是**全局有序区**，也就是说每趟产生的有序区中的所有元素都归位了。

（2）使关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”，一般称之为**小数上浮法**；另一种则与之相反，使关键字最大的元素逐渐”下沉“，称之为**大数下沉法**。它们之间区别并不大，只是在代码实现上略有区别而已：

class Solution {
 
 	//小数上浮法
 public int[] bubbleSort(int[] nums) {
 
 int n = nums.length;
 for (int i = 0; i < n - 1; i++) {
 
 for (int j = n - 1; j > i; j--) {
 
 if (nums[j - 1] > nums[j]) {
 
 //交换 nums[j - 1] 和 nums[j]
 int tmp = nums[j];
 nums[j] = nums[j - 1];
 nums[j - 1] = tmp;
 }
 }
 }
 return nums;
 }
 }

class Solution {
 
 	//大数上浮法
 public int[] bubbleSort(int[] nums) {
 
 int n = nums.length;
 for (int i = 0; i < n - 1; i++) {
 
 for (int j = 0; j < n - i - 1; j++) {
 
 if (nums[j] > nums[j + 1]) {
 
 //交换 nums[j] 和 nums[j + 1]
 int tmp = nums[j];
 nums[j] = nums[j + 1];
 nums[j + 1] = tmp;
 }
 }
 }
 return nums;
 }
 }

（2）改进：在有些情况下，在第 i (i < length - 1) 趟时已经排好序了，但仍执行后面几趟的比较。实际上，一但算法中的某一趟比较时不出现任何元素交换，则说明已经排好序了，就可以直接结束本算法。所以，改进的冒泡排序算法如下（以小数上浮法为例）：

//改进后的冒泡排序
 class Solution {
 
 public int[] improvedBubbleSort(int[] nums) {
 
 int n = nums.length;
 boolean isExchange;
 for (int i = 0; i < n - 1; i++) {
 
 isExchange = false;
 for (int j = n - 1; j > i; j--) {
 
 if (nums[j - 1] > nums[j]) {
 
 //交换 nums[j - 1] 和 nums[j]
 int tmp = nums[j];
 nums[j] = nums[j - 1];
 nums[j - 1] = tmp;
 //本趟发生了交换，将 isExchange 标记为 true
 isExchange = true;
 }
 }
 //如果本趟没有发生交换，则说明数组 nums 已经排好序，此时可直接返回 nums
 if (!isExchange) {
 
 return nums;
 }
 }
 return nums;
 }
 }

##### 2.1.1.2.快速排序 #####

（1）快速排序 (quick sort) 是由冒泡排序改进而得的，它的基本思想如下：

*  在待排序的 n 个元素中任取一个元素（通常取第一个元素，也可随机选取）作为基准，把该元素放入适当位置后，数据序列被此元素划分成两部分。所有关键字比该元素关键字小的元素放置在**前一部分**，所有比它大的元素放置在**后一部分**，并把该元素排在这两部分的中间（称为该元素归位），这个过程称为**一趟快速排序**，即**一趟划分**；
 *  之后对产生的两个部分分别重复上述过程，直至每部分内只有一个元素或者空为止。简而言之，每趟使序列的一个元素放入适当为止，将序列一分为二，对子序列按**递归方式**继续这种划分，直至划分的子序列的长位 1 或 0（递归出口）。

（2）以 nums = \{6, 8, 7, 9, 0, 1, 3, 2, 4, 5\} 为例，其快速排序的过程如下所示：  
![在这里插入图片描述][40c14e7feda346ce926f7fd41aeb0cdb.png]

（2）具体的代码实现如下：

class Solution {
 
 Random random = new Random();
 
 public void quickSort(int[] nums, int left, int right) {
 
 int i;
 if (left < right) {
 
 i = randomPartition(nums, left, right);
 quickSort(nums, left, i - 1);
 quickSort(nums, i + 1, right);
 }
 }
 
 public int randomPartition(int[] nums, int left, int right) {
 
 	 //随机从 nums[left...right] 中选取一个元素作为基准
 int i = random.nextInt(right - left + 1) + left;
 int tmp = nums[i];
 nums[i] = nums[left];
 nums[left] = tmp;
 return partition(nums, left, right);
 }
 
 public int partition(int[] nums, int left, int right) {
 
 int i = left, j = right;
 //以 nums[left] 为基准
 int benchmark = nums[left];
 while (i < j) {
 
 //从右向左扫描，找到一个小于 benchmark 的元素 nums[j]
 while (i < j && benchmark <= nums[j]) {
 
 j--;
 }
 nums[i] = nums[j];
 //从左向右扫描，找到一个大于 benchmark 的元素 nums[i]
 while (i < j && nums[i] <= benchmark) {
 
 i++;
 }
 nums[j] = nums[i];
 }
 nums[i] = benchmark;
 return i;
 }
 }

（3）此外，非递归的快速排序的代码如下：

class Solution {
 
 Random random = new Random();
 
 public int[] quickSort(int[] nums, int left, int right) {
 
 Deque<Integer> stack = new ArrayDeque<>();
 stack.push(right);
 stack.push(left);
 while (!stack.isEmpty()) {
 
 int l = stack.pop();
 int r = stack.pop();
 if (l < r) {
 
 int pivot = randomPartition(nums, l, r);
 if (pivot - 1 > l) {
 
 stack.push(pivot - 1);
 stack.push(l);
 }
 if (pivot + 1 < r) {
 
 stack.push(r);
 stack.push(pivot + 1);
 }
 }
 }
 return nums;
 }
 
 public int randomPartition(int[] nums, int left, int right) {
 
 //随机从 nums[left...right] 中选取一个元素作为基准
 int i = random.nextInt(right - left + 1) + left;
 int tmp = nums[i];
 nums[i] = nums[right];
 nums[right] = tmp;
 return partition(nums, left, right);
 }
 
 public int partition(int[] nums, int left, int right) {
 
 int i = left, j = right;
 int benchmark = nums[left];
 while (i < j) {
 
 while (i < j && benchmark <= nums[j]) {
 
 j--;
 }
 nums[i] = nums[j];
 while (i < j && nums[i] <= benchmark) {
 
 i++;
 }
 nums[j] = nums[i];
 }
 nums[i] = benchmark;
 return i;
 }
 }

#### 2.1.2.插入排序 ####

插入排序的基本思想是：每次将一个待排序的元素按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部元素插入完成为止。本节介绍三种插入排序算法：**直接插入排序**、**折半排序**和**希尔排序**。

##### 2.1.2.1.直接插入排序 #####

（1）假设待排序的元素存放在数组 R\[O…n - 1\]中，在排序过程的某一中间时刻，R 被划分成两个子区间 R\[0…i - 1\] 和 R\[i…n - 1\]，其中前一个子区间是已排好序的**有序区 (ordered region)**，后一个子区间则是当前未排序的部分，不妨称其为**无序区 (disordered region)**，初始时 i = 1，有序区只有 R\[0\]一个元素。

![在这里插入图片描述][40b4e593590d4a89b8a51ad64445512d.png]

（2）直接插入排序 (straight insertion sort)的一趟操作是将当前无序区的开头元素 R\[i\] (1 ≤ i ≤ n - 1) 插入到有序区 R\[0…i - 1\] 中的适当位置，使 R\[0…i\] 变为新的有序区，如下图所示。这种方法通常称为**增量法**，因为它每次使有序区增加一个元素。

（3）对于**第 i 趟排序**，将无序区的第一个元素 R\[i\] 插入到有序区的过程如下：

*  先将 R\[i\] 暂放到 tmp 中，j 在有序区中从后向前找（初值为 i - 1），凡是关键字大于 tmp.key 的记录均后移一个位置；
 *  若找到某个 R\[j\]，其关键字小于或等于 tmp.key，则将 tmp 放在它们后面，即置R\[j + 1\] = tmp；

> 说明：直接插入排序每趟产生的有序区并不一定是**全局有序区**，也就是说有序区中的元素并不一定放在最终的位置上。当一个元素在整个排序结束前就已经放在其最终位置上称为**归位 (homing)**。

（4）以 nums = \{9, 8, 7, 6, 5, 4, 3, 2, 1, 0\} 为例，其直接插入排序的过程如下所示：  
![在这里插入图片描述][5bd101e340774749a5cdf219c581ca65.png]

（5）具体的代码实现如下：

class Solution {
 
 	public int[] insertSort(int[] nums) {
 
 int n = nums.length;
 for (int i = 1; i < n; i++) {
 
 if (nums[i - 1] > nums[i]) {
 
 int tmp = nums[i];
 int j = i - 1;
 //查找 nums[i] 应该插入的位置
 do {
 
 nums[j + 1] = nums[j];
 j--;
 } while (j >= 0 && nums[j] > tmp);
 //在下标为 j + 1 的位置上插入 nums[i]
 nums[j + 1] = tmp;
 }
 }
 return nums;
 }
 }

##### 2.1.2.2.折半插入排序 #####

（1）直接插人排序中将无序区的开头元素 R\[i\] (1≤ i ≤ n - 1) 插入到有序区 R\[0…i - 1\] 是采用**顺序比较**的方法。由于有序区的元素是有序的，可以采用二分搜索方法先在 R\[0…i-1\] 中找到插入位置，再通过移动元素进行插入，这样的插入排序称为**折半插入排序 (binary insertion sort) 或二分插入排序**。

> 说明：有关二分搜索算法的相关知识可以查看[【算法】二分搜索][Link 1]这篇文章。

（2）第 i 趟在 R\[low…high\]（初始时 low = 0，high = i - 1）中采用折半查找方法查找插入 R\[i\] 的位置为 R\[high + 1\]，再将 R\[high + 1…i - 1\]元素后移一个位置，并置 R\[high + 1\] = R\[i\]。此外需要注意的是**和直接插入排序一样，折半插入排序每趟产生的有序区并不一定是全局有序区。**

（3）具体的代码实现如下：

class Solution {
 
 public int[] binaryInsertSort(int[] nums) {
 
 int n = nums.length;
 for (int i = 1; i < n; i++) {
 
 if (nums[i - 1] > nums[i]) {
 
 int tmp = nums[i];
 int left = 0;
 int right = i - 1;
 //在 nums[left...right] 中查找 nums[i] 应该插入的位置
 while (left <= right) {
 
 int mid = left + (right - left) / 2;
 if (nums[mid] > tmp) {
 
 right = mid - 1;
 } else {
 
 left = mid + 1;
 }
 }
 //集中将元素进行后移
 for (int j = i - 1; j >= right + 1; j--) {
 
 nums[j + 1] = nums[j];
 }
 //在下标为 right + 1 的位置上插入 nums[i]
 nums[right + 1] = tmp;
 }
 }
 return nums;
 }
 }

##### 2.1.2.3.希尔排序 #####

（1）希尔排序(shell sort)也是一种插入排序方法，实际上是一种分组插入方法。其基本思想如下：

* 先取一个小于 n 的整数 d1 作为第一个增量，把表的全部元素分成 d1 个组，将所有距离为 d 的倍数的元素放在同一个组中，如下图所示： 
 ![在这里插入图片描述][e587fa68105a428eb80113f5cd40e040.png]
 * 在各组内进行直接插入排序；然后取第 2 个增量 d2 (< d1)，重复上述的分组和排序，直到所取的增量 d1= 1 (dt < dt-1<…<d2<d1)，即所有元素放在同一组中进行直接插入排序为止。所以希尔排序称为**减少增量的排序方法**。

（2）每一段希尔排序从元素 R\[d\] 开始起，采用直接插入排序，直到元素 R\[n - 1\] 为止。每个元素的比较和插入都在同组内部进行，对于元素 R\[i\]，同组的前面的元素有 \{R\[j\] | j = i - d ≥ 0\}。

> 说明：希尔排序每趟并不产生**有序区**，在最后一趟排序结束前，所有元素并不一定归位的，但是在希尔排序每趟完成后数据越来越接近有序。

（3）以 nums = \{9, 8, 7, 6, 5, 4, 3, 2, 1, 0\} 为例，其**希尔排序**的过程如下所示：

![在这里插入图片描述][edfd343949ae48a7a00a94e7f34c3b99.png]

（4）具体的代码实现如下：

class Solution {
 
 public int[] shellSort(int[] nums) {
 
 int n = nums.length;
 int d = n / 2;
 while (d > 0) {
 
 //对相隔 d 个位置的一组数据使用直接插入排序
 for (int i = d; i < n; i++) {
 
 if (nums[i - d] > nums[i]) {
 
 int tmp = nums[i];
 int j = i - d;
 do {
 
 nums[j + d] = nums[j];
 j -= d;
 } while (j >= 0 && nums[j] > tmp);
 nums[j + d] = tmp;
 }
 }
 d /= 2;
 }
 return nums;
 }
 }

#### 2.1.3.选择排序 ####

（1）**选择排序**的基本思想是每一趟从待排序的元素中选出关键字最小的元素，顺序放在已排好序的有序区的最后，直到全部元素排序完毕。  
（2）由于选择排序方法每一趟总是从无序区中选出全局最小（或最大）的关键字，所以**适合于从大量的元素中选择一部分排序元素**。本节介绍两种选择排序方法，即**简单选择排序**（或称直接选择排序）和**堆排序**。

##### 2.1.3.1.简单/直接选择排序 #####

（1）简单选择排序(simple selection sort)的基本思想如下：

* 第 i 趟排序开始时，当前有序区和无序区分别为 R\[0…i - 1\] 和 R\[i…n - 1\] (0 ≤ i < n - 1)，该趟排序时从当前无序区中选出关键字最小的元素 R\[k\]，将它与无序区的第 1 个元素 R\[i\] 交换，使 R\[0…i\] 和 R\[i + 1…n - 1\] 分别变为新的有序区和新的无序区，如下图所示： 
 ![在这里插入图片描述][9f7e68fae17b47f99d076242f992b907.png]
 * 因为每趟排序使有序区中增加了一个元素，且有序区中元素的关键字均不大于无序区中元素的关键字，即第 i 趟排序之后 R\[0…i\] 的所有关键字均小于等于 R\[i + 1…n - 1\] 中的所有关键字，所以进行 n - 1 趟排序之后 R\[0…n - 2\] 的所有关键字小于等于 R\[n - 1\].key，也就是说，经过 n - 1 趟排序之后整个表 R\[0…n - 1\]递增有序。

> 说明：简单选择排序每趟产生的有序区一定要是全局有序区，也就是说，每趟产生的有序区中所有元素都归位了。

（3）以 nums = \{2, 1, 3, 4, 5\} 为例，其**简单选择排序**的过程如下所示：

![在这里插入图片描述][7fd74d550c844da09e7276e98370cb27.png]

（4）具体的代码实现如下：

class Solution {
 
 public int[] selectSort(int[] nums) {
 
 int n = nums.length;
 for (int i = 0; i < n - 1; i++) {
 
 int k = i;
 for (int j = i + 1; j < n; j++) {
 
 if (nums[k] > nums[j]) {
 
 k = j;
 }
 }
 if (k != i) {
 
 	//交换 nums[i] 和 nums[k]
 int tmp = nums[k];
 nums[k] = nums[i];
 nums[i] = tmp;
 }
 }
 return nums;
 }
 }

##### 2.1.3.2.堆排序 #####

（1）堆排序(heap sort)是一种树形选择排序方法，它的特点是将 R\[1…n\]（R\[i\] 的关键字为 ki）看成是一棵完全二叉树的顺序存储结构，如下图所示。利用**完全二叉树中双亲节点和孩子节点之间的位置关系**在无序区中选择关键字最大（或最小）的元素。

![在这里插入图片描述][4679efa12d7c4bb398e5e04e19f2036d.png]

（2）堆的定义是 R\[1…n\] 中的 n 个关键字序列 k1，k2，…，kn 称为堆，当且仅当该序列满足如下性质（简称为**堆性质**）：

*  ki ≤ k2i 且 ki ≤ k2i+1; 或
 *  ki ≥ k2i 且 ki ≥ k2i+1; (1 ≤ i ≤ ⌊n / 2⌋)

满足第 ① 种情况的堆称为**小根堆**，对于上图而言，就是树中分支任何节点的关键字都小于等于其孩子节点的关键字。满足第 ② 种情况的堆称为**大根堆**，对于上图而言，就是树中分支任何节点的关键字都大于等于其孩子节点的关键字。下面主要讨论大根堆。

（3）堆排序的排序过程与简单选择排序类似，只是挑选最大或最小元素时采用的方法不同，这里采用大根堆，每次挑选最大元素归位。挑选最大元素是采用筛选方法实现的。sift 算法对 nums\[low…high\] 进行筛选，使得以 R\[low\] 为根节点的左子树和右子树均为大根堆，其代码实现如下。

//对 nums[low...high] 进行筛选，使得以 nums[low] 为根节点的左子树和右子树均为大根堆
 public void sift(int[] nums, int low, int high) {
 
 // nums[j] 是 nums[i] 的左孩子
 int i = low;
 int j = (i == 0) ? 1 : 2 * i;
 int tmp = nums[i];
 while (j <= high) {
 
 //如果右孩子更大，则将 j 指向右孩子
 if (j < high && nums[j] < nums[j + 1]) {
 
 j++;
 }
 //根节点小于最大孩子节点
 if (tmp < nums[j]) {
 
 nums[i] = nums[j];
 nums[j] = tmp;
 i = j;
 j = 2 * i;
 } else {
 
 //如果跟节点大于等于最大孩子关键字，筛选结束
 break;
 }
 }
 }

（4）这样一来，**通过调用 ⌊n / 2⌋ 次 sift 算法构建好初始堆 R\[1…n\] 后，根节点 R\[1\] 一定是最大关键字节点**，将其放到排序序列的最后，也就是将堆中的根与最后一个叶子交换。由于最大元素已归位，整个待排序的元素个数减少一个。由于根节点的改变，这 n - 1 个节点 R\[1… n - 1\] 不一定为堆，但其左子树和右子树均为堆，在调用一次 sift 算法将这 n - 1 个节点 R\[1…n - 1\] 调整成堆，其根节点为次大的元素，将它放到排序序列的倒数第 2 个位置，即将堆中的根与最后一个叶子交换，待排序的元素个数变为 n - 2 个，即 R\[1…n - 2\]，再调整，再将根节点归位，如此这样，直到二叉树只剩一个根为止。

（5）具体的代码实现如下：

class Solution {
          
        public int[] heapSort(int[] nums) {
        
            int n = nums.length;
            //循环建立初始堆，调用 sift 算法 ⌊n / 2⌋ 次
            for (int i = (n - 1) / 2; i >= 0; i--) {
        
                sift(nums, i, n - 1);
            }
            for (int i = n - 1; i >= 0; i--) {
        
                //将 nums[i] 与根 nums[0] 交换
                int tmp = nums[0];
                nums[0] = nums[i];
                nums[i] = tmp;
                //对 nums[0...i - 1] 进行筛选，得到 i 个节点的堆
                sift(nums, 0, i - 1);
            }
            return nums;
        }
    }

#### 2.1.4.归并排序 ####

归并排序 (merge sort) 是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表，即二路归并。

##### 2.1.4.1.二路归并排序 #####

（1）二路归并排序 (2-way merge sort) 的基本思路如下：将 R\[0…n - 1\] 看成是 n 个长度为 1 的有序序列，然后进行两两归并，得到 ⌈n / 2⌉ 个长度为 2（最后一个有序序列的长度可能为 2）的有序序列，在进行两两归并，得到 ⌈n / 4⌉ 个长度为 4（最后一个有序序列的长度可能小于 4）的有序序列，…，直到得到一个长度为 n 的有序序列。

> 说明：归并排序每趟产生的有序区只是**局部有序的**，也就是说在最后一趟排序结束前所有元素并不一定归位了。

（2）**一次二路归并**：将两个位置相邻的记录有序子序列归并为一个记录的有序序列，如下图所示：

![在这里插入图片描述][4075c39dd22d46afa36aea6520d913be.png]  
代码实现如下：

//对 nums[left...mid] 和 nums[mid + 1...right] 中的元素进行归并
 public void merge(int[] nums, int left, int mid, int right) {
 
 int[] p = new int[right - left + 1];
 int i = left, j = mid + 1, k = 0;
 while (i <= mid && j <= right) {
 
 if (nums[i] <= nums[j]) {
 
 p[k++] = nums[i++];
 } else {
 
 p[k++] = nums[j++];
 }
 }
 while (i <= mid) {
 
 p[k++] = nums[i++];
 }
 while (j <= right) {
 
 p[k++] = nums[j++];
 }
 //将 p 中的元素复制到 nums[left...right]
 for (k = 0, i = left; i <= right; k++, i++) {
 
 nums[i] = p[k];
 }
 }

（3）一趟二路归并，段长度为 `mergeLen`，其代码实现如下：

//对整个排序序列进行一趟归并
 public void mergePass(int[] nums, int mergeLen) {
 
 int n = nums.length;
 int i;
 //归并长度为 mergeLen 的两相邻子表
 for (i = 0; i + 2 * mergeLen - 1 < n; i += 2 * mergeLen) {
 
 merge(nums, i, i + mergeLen - 1, i + 2 * mergeLen - 1);
 }
 //余下两个子表，后者的长度小于 mergeLen
 if (i + mergeLen - 1 < n - 1) {
 
 merge(nums, i, i + mergeLen - 1, n - 1);
 }
 }

（4）二路归并排序即进行 ⌈log2n⌉ 趟二路归并，具体的代码实现如下：

public int[] mergeSort(int[] nums) {
 
 int n = nums.length;
 for (int mergeLen = 1; mergeLen < n; mergeLen *= 2) {
 
 mergePass(nums, mergeLen);
 }
 return nums;
 }

（5）完整代码如下：

class Solution {
 
 	public int[] mergeSort(int[] nums) {
 
 	 int n = nums.length;
 	 for (int mergeLen = 1; mergeLen < n; mergeLen *= 2) {
 
 	 mergePass(nums, mergeLen);
 	 }
 	 return nums;
 	}
 	
 	public void mergePass(int[] nums, int mergeLen) {
 
 	 int n = nums.length;
 	 int i;
 	 //归并长度为 mergeLen 的两相邻子表
 	 for (i = 0; i + 2 * mergeLen - 1 < n; i += 2 * mergeLen) {
 
 	 merge(nums, i, i + mergeLen - 1, i + 2 * mergeLen - 1);
 	 }
 	 //余下两个子表，后者的长度小于 mergeLen
 	 if (i + mergeLen - 1 < n - 1) {
 
 	 merge(nums, i, i + mergeLen - 1, n - 1);
 	 }
 	}
 
 	public void merge(int[] nums, int left, int mid, int right) {
 
 	 int[] p = new int[right - left + 1];
 	 int i = left, j = mid + 1, k = 0;
 	 while (i <= mid && j <= right) {
 
 	 if (nums[i] <= nums[j]) {
 
 	 p[k++] = nums[i++];
 	 } else {
 
 	 p[k++] = nums[j++];
 	 }
 	 }
 	 while (i <= mid) {
 
 	 p[k++] = nums[i++];
 	 }
 	 while (j <= right) {
 
 	 p[k++] = nums[j++];
 	 }
 	 //将 p 中的元素复制到 nums[left...right]
 	 for (k = 0, i = left; i <= right; k++, i++) {
 
 	 nums[i] = p[k];
 	 }
 	}
 }

（6）以 nums = \{18, 2, 20, 34, 12, 32, 6, 16, 1, 5\} 为例，其**二路归并排序**的过程如下所示：

![在这里插入图片描述][f1ebe4754f2c4fdcbde1c1c4dd177d64.png]

##### 2.1.4.2.二路归并排序递归版 #####

下面是二路归并排序递归版的代码：

class Solution {
 
 public void mergeSort(int[] nums) {
 
 if (nums == null || nums.length <= 1) {
 
 return;
 }
 mergePass(nums, 0, nums.length - 1);
 }
 
 private void mergePass(int[] nums, int left, int right) {
 
 if (left >= right) {
 
 return;
 }
 int mid = left + (right - left) / 2;
 mergePass(nums, left, mid);
 mergePass(nums, mid + 1, right);
 merge(nums, left, mid, right);
 }
 
 //对 nums[left...mid] 和 nums[mid + 1...right] 中的元素进行归并
 public void merge(int[] nums, int left, int mid, int right) {
 
 int[] tmp = new int[right - left + 1];
 int i = left;
 int j = mid + 1;
 int k = 0;
 while (i <= mid && j <= right) {
 
 if (nums[i] <= nums[j]) {
 
 tmp[k++] = nums[i++];
 } else {
 
 tmp[k++] = nums[j++];
 }
 }
 while (i <= mid) {
 
 tmp[k++] = nums[i++];
 }
 while (j <= right) {
 
 tmp[k++] = nums[j++];
 }
 //将 tmp 中的元素复制到 nums[left...right]
 for (k = 0, i = left; i <= right; k++, i++) {
 
 nums[i] = tmp[k];
 }
 }
 }

此外，有关链表的归并排序可以参考 [LeetCode\_排序\_中等\_148.排序链表][LeetCode_148.]这篇文章。

### 2.2.非比较类排序 ###

#### 2.2.1.基数排序 ####

（1）基数排序 (radix sort) 是通过“分配”和“收集”过程来实现排序，不需要进行关键字间的比较，是一种借助于多关键字排序的思想对单关键字排序的方法。

（2）具体的代码实现如下：

class Solution {
 
 	//基数排序：最低位优先法(Least Significant Digit first, LSD)
 	public int[] radixSort(int[] nums) {
 
 	 int length = nums.length;
 	 // flag = false 表示数组 nums 中不存在 0 或者负数
 	 boolean flag = false;
 	 int minNum = Integer.MAX_VALUE;
 	 for (int num : nums) {
 
 	 minNum = Math.min(minNum, num);
 	 if (num <= 0) {
 
 	 flag = true;
 	 }
 	 }
 	 if (flag) {
 
 	 //将数组 nums 中的所有数都加上 1 - minNum
 	 for (int i = 0; i < length; i++) {
 
 	 nums[i] += 1 - minNum;
 	 }
 	 }
 	 // d 表示当前比较的位数，d = 1 表示比较个位，d = 10 表示比较十位，以此类推
 	 long d = 1;
 	 // maxD 表示数组 nums 中的最大数
 	 int maxD = Arrays.stream(nums).max().getAsInt();
 	 //数组 buf 保存基数排序中一趟分配和收集后的整数
 	 int[] buf = new int[length];
 	 while (maxD >= d) {
 
 	 	//分配
 	 //目前 total[i] = j 表示当前位数下值为 i 的整数的个数为 j
 	 int[] total = new int[10];
 	 for (int num : nums) {
 
 	 int digit = (num / (int) d) % 10;
 	 total[digit]++;
 	 }
 	 //目前 total[i] = j 表示当前位数下的值 ≤ i 的整数的个数为 j
 	 for (int i = 1; i < 10; i++) {
 
 	 total[i] += total[i - 1];
 	 }
 	 for (int i = length - 1; i >= 0; i--) {
 
 	 // digit 表示 nums[i] 的 d 位数上的值
 	 int digit = (nums[i] / (int) d) % 10;
 	 //将 nums[i] 存入数组 buf 中下标为 total[digit] - 1 的位置
 	 buf[total[digit] - 1] = nums[i];
 	 total[digit]--;
 	 }
 	 //收集：将数组 buf 拷贝到数组 nums 中
 	 System.arraycopy(buf, 0, nums, 0, length);
 	 d *= 10;
 	 }
 	 if (flag) {
 
 	 //将数组 nums 中的所有数都减去 minNum + 1
 	 for (int i = 0; i < length; i++) {
 
 	 nums[i] -= 1 - minNum;
 	 }
 	 }
 	 return nums;
 	}
 }

（3）需要注意的是，基数排序对包含负数的数组进行排序，因此，上面的代码在排序之前，先对将 nums 中的元素全部转换为正数，当排序结束后，再将其转换回去。不过在转换过程中需要保证，元素大小不能超出其对应的表示范围！

> 有关 `System.arraycopy()` 方法的相关知识可以参考 [Java 基础——System.arraycopy() 与 Arrays.copyOf() 的联系与区别][Java _System.arraycopy_ _ Arrays.copyOf_]这篇文章。

## 3.总结 ##

<table> 
 <thead> 
 <tr> 
 <th>排序算法</th> 
 <th>最好时间复杂度</th> 
 <th>平均时间复杂度</th> 
 <th>最坏时间复杂度</th> 
 <th>空间复杂度</th> 
 <th>是否稳定</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>冒泡排序</td> 
 <td>O(n)</td> 
 <td>O(n2)</td> 
 <td>O(n2)</td> 
 <td>O(1)</td> 
 <td>是</td> 
 </tr> 
 <tr> 
 <td>直接插入排序</td> 
 <td>O(n)</td> 
 <td>O(n2)</td> 
 <td>O(n2)</td> 
 <td>O(1)</td> 
 <td>是</td> 
 </tr> 
 <tr> 
 <td>简单/直接选择排序</td> 
 <td>O(n2)</td> 
 <td>O(n2)</td> 
 <td>O(n2)</td> 
 <td>O(1)</td> 
 <td>否</td> 
 </tr> 
 <tr> 
 <td>折半插入排序</td> 
 <td>O(n)</td> 
 <td>O(n2)</td> 
 <td>O(n2)</td> 
 <td>O(1)</td> 
 <td>是</td> 
 </tr> 
 <tr> 
 <td>希尔排序</td> 
 <td>O(n)</td> 
 <td>≈O(n1.3)</td> 
 <td>O(n2)</td> 
 <td>O(1)</td> 
 <td>否</td> 
 </tr> 
 <tr> 
 <td>快速排序</td> 
 <td>O(nlog2n)</td> 
 <td>O(nlog2n)</td> 
 <td>O(n2)</td> 
 <td>O(log2n)</td> 
 <td>否</td> 
 </tr> 
 <tr> 
 <td>堆排序</td> 
 <td>O(nlog2n)</td> 
 <td>O(nlog2n)</td> 
 <td>O(nlog2n)</td> 
 <td>O(1)</td> 
 <td>否</td> 
 </tr> 
 <tr> 
 <td>二路归并排序</td> 
 <td>O(nlog2n)</td> 
 <td>O(nlog2n)</td> 
 <td>O(nlog2n)</td> 
 <td>O(n)</td> 
 <td>是</td> 
 </tr> 
 <tr> 
 <td>基数排序</td> 
 <td>O(d(n + r))</td> 
 <td>O(d(n + r))</td> 
 <td>O(d(n + r))</td> 
 <td>O(r )</td> 
 <td>是</td> 
 </tr> 
 </tbody> 
</table>

> 注意：在基数排序的复杂度中，r 代表关键字的基数，d 代表关键字的长度（即位数），n 代表关键字的个数

## 4.其它 ##

（1）如何对数组进行排序，并且保存它原始的下标？

class ArraySortWithOriginalIndex {
 
 public static void main(String[] args) {
 
 int[] array = {
 7, 2, 5, 1, 9};
 
 // 创建新数组并保存原始下标
 Integer[] indices = new Integer[array.length];
 for (int i = 0; i < array.length; i++) {
 
 indices[i] = i;
 }
 
 // 使用自定义比较器对新数组进行排序，比较的依据为原始数组的值
 Arrays.sort(indices, (a, b) -> (array[a] - array[b]));
 
 // 输出排序后的数组
 int[] sortedArray = new int[array.length];
 for (int i = 0; i < array.length; i++) {
 
 sortedArray[i] = array[indices[i]];
 }
 System.out.println(Arrays.toString(sortedArray)); 	// [1, 2, 5, 7, 9]
 
 // 输出排序后的原始下标
 System.out.println(Arrays.toString(indices)); 		// [3, 1, 2, 0, 4]
 }
 }

[b14cbc70a5c24ca8b94206f70f6fb494.png]: https://img-blog.csdnimg.cn/b14cbc70a5c24ca8b94206f70f6fb494.png
[13785dbbad404d54a26cc95f502c178c.png]: https://img-blog.csdnimg.cn/13785dbbad404d54a26cc95f502c178c.png
[40c14e7feda346ce926f7fd41aeb0cdb.png]: https://img-blog.csdnimg.cn/40c14e7feda346ce926f7fd41aeb0cdb.png
[40b4e593590d4a89b8a51ad64445512d.png]: https://img-blog.csdnimg.cn/40b4e593590d4a89b8a51ad64445512d.png
[5bd101e340774749a5cdf219c581ca65.png]: https://img-blog.csdnimg.cn/5bd101e340774749a5cdf219c581ca65.png
[Link 1]: https://blog.csdn.net/weixin_43004044/article/details/128591151
[e587fa68105a428eb80113f5cd40e040.png]: https://img-blog.csdnimg.cn/e587fa68105a428eb80113f5cd40e040.png
[edfd343949ae48a7a00a94e7f34c3b99.png]: https://img-blog.csdnimg.cn/edfd343949ae48a7a00a94e7f34c3b99.png
[9f7e68fae17b47f99d076242f992b907.png]: https://img-blog.csdnimg.cn/9f7e68fae17b47f99d076242f992b907.png
[7fd74d550c844da09e7276e98370cb27.png]: https://img-blog.csdnimg.cn/7fd74d550c844da09e7276e98370cb27.png
[4679efa12d7c4bb398e5e04e19f2036d.png]: https://img-blog.csdnimg.cn/4679efa12d7c4bb398e5e04e19f2036d.png
[4075c39dd22d46afa36aea6520d913be.png]: https://img-blog.csdnimg.cn/4075c39dd22d46afa36aea6520d913be.png
[f1ebe4754f2c4fdcbde1c1c4dd177d64.png]: https://img-blog.csdnimg.cn/f1ebe4754f2c4fdcbde1c1c4dd177d64.png
[LeetCode_148.]: https://blog.csdn.net/weixin_43004044/article/details/119234987
[Java _System.arraycopy_ _ Arrays.copyOf_]: https://xgqngu.blog.csdn.net/article/details/129899439