Java实现八大排序算法

àì夳堔傛蜴生んèń 2023-07-03 10:47 3阅读 0赞

### 文章目录 ###

*  1 排序算法的分类
 *  2 算法实现
 *   *  2.1 插入排序
     *   *  1 直接插入排序
         *  2 折半插入排序
         *  3 希尔排序（shell排序/缩小增量排序）
     *  2.2 交换排序
     *   *  1 冒泡排序
         *  2 快速排序
     *  2.3 选择排序
     *   *  1 简单选择排序
         *  2 堆排序
     *  2.4 归并排序
     *  2.5 基数排序
 *  3 算法执行效率

# 1 排序算法的分类 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70_pic_center]

3、外部排序

*  多路归并排序

1.  算法的稳定性  
    若待排序表中有两个元素  R i ， R j R\_i，R\_j Ri，Rj ，其对应的关键字相同  k e y i = k e y j key\_i = key\_j keyi=keyj 且在排序前  R i 在 R j R\_i 在 R\_j Ri在Rj 的前面，若使用某排序算法排序后，  R i 仍 然 在 R j R\_i 仍然在 R\_j Ri仍然在Rj 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。  
    算法的稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的， 那么选择排序算法时的稳定与否就无关紧要。
2.  在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类:
    
     *  内部排序，是指在排序期间元素全部存放在内存中的排序
     *  外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。

通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类

# 2 算法实现 #

## 2.1 插入排序 ##

### 1 直接插入排序 ###

**a 算法原理**

设有 n 个元素的顺序表  L \[ 1 … n \] L\[1\\dots n\] L\[1…n\]，假设下标从 1 开始，按升序排序：

1. 将一组数据分成两组，分别为有序组、无序组（第一次取首元素为有序组，剩余 n-1 个元素为无序组）
2. 取出无序组第一个元素 L \[ i + 1 \] L\[i+1\] L\[i\+1\]，按从后向前的顺序，与有序组的元素逐个比较： 
 ①若 L \[ i + 1 \] < L \[ x \] ， 1 ≤ x ≤ i L\[i+1\] < L\[x\]，1\\leq x\\leq i L\[i\+1\]<L\[x\]，1≤x≤i，则将 L \[ x \] L\[x\] L\[x\]后移一位 
 ②若 L \[ i + 1 \] ≥ L \[ x \] ， 1 ≤ x ≤ i L\[i+1\] \\geq L\[x\]，1\\leq x\\leq i L\[i\+1\]≥L\[x\]，1≤x≤i，则停止比较，将 L \[ i + 1 \] L\[i+1\] L\[i\+1\]插入到 L \[ x \] L\[x\] L\[x\]后
3. 重复步骤 2， 直至无序组元素为空，则元素最终有序

**b 性能分析**

*  空间效率：仅使用常数个辅助单元，空间复杂度为 O ( 1 ) O(1) O(1)
 *  时间效率
    
     *  最好情况  
        元素顺序与排序结果相同，每插入一个元素仅需比较一次而不需移动，且比较次数为 n-1，故时间复杂度为 O ( n ) O(n) O(n)
     *  最坏情况  
        元素顺序与排序结果相反，则第 i+1 个元素需向前比较 i 次，且前 i 个元素每个都要移动一次，则总比较次数、总移动次数均为 ∑ i = 2 n ( i − 1 ) ， 结 果 为 2 ∗ ∑ i = 2 n ( i − 1 ) = 2 ∗ ( 1 + 2 + . . . + ( n − 1 ) ) = 2 ∗ n ( n − 1 ) 2 = n 2 − n \\displaystyle \\sum\_\{i=2\}^n(i-1)，结果为2 \* \\displaystyle \\sum\_\{i=2\}^n(i-1) = 2 \* (1+2+...+(n-1)) =2\*\\frac\{n(n-1)\}\{2\}=n^2-n i=2∑n(i−1)，结果为2∗i=2∑n(i−1)=2∗(1\+2\+...\+(n−1))=2∗2n(n−1)=n2−n，故时间复杂度为 O ( n 2 ) O(n^2) O(n2)
 *  稳定性：每次都是从后向前先比较再移动，待插入元素不会插入到值相等元素前面，元素间相对位置不变，因此直接插入排序是稳定的排序算法

**c 适用范围**

元素顺序越接近有序，比较次数、移动次数越少，越接近逆序比较次数、移动次数越多。可见，直接插入排序适用于元素基本有序的情况

public class InsertSortDemo { 
 static final int SIZE = 20;
 public static void insertSort(int[] array) { 
 int temp = 0, j;
 for (int i = 1; i < array.length; i++) { 
 temp = array[i]; // 从无序组取出第一个元素
 j = i - 1; // i-1 即为有序组最后一个元素（与待插入元素相邻）的下标
 // 按从后向前的顺序，将待插入元素与有序组元素逐个比较
 while (j >=0 && temp < array[j]) { 
 array[j+1] = array[j]; // 若不是合适位置，有序组元素向后移动
 j--;
 }
 array[j+1] = temp; // 找到合适位置，将元素插入
 }
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 
 insertSort(array);
 System.out.println("排序后的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 }
 }

排序前的数组为：
    196 112 168 103 158 193 153 159 142 148 
    128 167 116 148 158 170 173 168 197 112 
    排序后的数组为：
    103 112 112 116 128 142 148 148 153 158 
    158 159 167 168 168 170 173 193 196 197 
    
    Process finished with exit code 0

### 2 折半插入排序 ###

折半插入是对直接插入的改进，唯一不同的是插入元素时比较元素的方法。

直接插入排序：比较元素是从后向前逐个比较，以确定插入位置  
折半插入排序：先在有序表中使用折半查找确定元素 L \[ i \] L\[i\] L\[i\]在有序表中的位置，然后再将 L \[ i \] L\[i\] L\[i\]插入到合适位置

由于使用了折半查找，元素的比较次数减少，约为 O ( n l o g 2 n ) O(nlog\_2n) O(nlog2n)，元素的比较次数与初始状态无关，仅取决于元素个数 n，而元素的移动次数没有改变，和初始状态有关。因此，折半插入排序时间复杂度为 O ( n 2 ) O(n^2) O(n2)，是稳定的排序算法，适用于元素个数不多的排序

void InsertSort(int A[], int arrayLength)
 { 
 int i, j, low, mid, high;
 for(i = 2; i <= arrayLength; i++)
 { 
 A[0] = A[i];	//A[0]用来暂存元素L[i]
 low = 1;
 high = i-1;
 while(low <= high)
 { 
 mid = (high + low) / 2;
 if(A[0] < A[mid]) high = mid - 1;
 else low = mid + 1;
 }
 for(j = i-1; j >= high+1; j--)
 A[j+1] = A[j];
 A[high+1] = A[0];
 }
 }

### 3 希尔排序（shell排序/缩小增量排序） ###

**a 算法原理**

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），对每个子序列进行直接插入排序。然后缩减增量对子序列进行排序…，直至增量为 1 时，将整个元素序列变为有序。

先取小于元素个数 n 的增量 gap，表中所有距离为 gap 的元素归为一组，对分好组的子序列进行直接插入排序；不断缩小 gap ，重复进行分组、排序的过程，直到 gap 为1，最终整个序列有序。

gap的一般取法：首先取 g a p = ⌊ n / 2 ⌋ ， 然 后 取 g a p = ⌊ g a p / 2 ⌋ gap=\\lfloor n/2 \\rfloor，然后取gap=\\lfloor gap/2 \\rfloor gap=⌊n/2⌋，然后取gap=⌊gap/2⌋

**b 性能分析**

*  空间效率：仅使用常数个辅助单元，空间复杂度为 O ( 1 ) O(1) O(1)
 *  时间效率：取决于所选用的增量函数，这属于数学上尚未解决的难题。一般来说时间复杂度为 O ( n 1.3 ) O(n^\{1.3\}) O(n1.3)，最坏情况下为 O ( n 2 ) O(n^2) O(n2)
 *  稳定性：相同关键字的元素可能划分到不同子序列，各个子序列排序后关键字相同的元素相对位置可能改变，因此希尔排序是不稳定的排序算法

**c 适用范围**

直接插入排序适用于元素基本有序和数据量不大的顺序表，希尔排序是基于此两点对直接插入排序的改进，当数据量较多时可选用希尔排序，且它仅适用与线性表为顺序存储的情况。

array\[10\] = \{198, 104, 146, 153, 198, 132, 103, 170, 185, 184\}

1.  gap = 10 / 2 = 5  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]
2.  gap = 5 / 2 = 2  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]
3.  gap = 2 / 2 = 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]  
希尔排序适用于大规模且无序的数据

import java.util.Arrays;
 
 public class ShellSortDemo { 
 static final int SIZE = 20;
 
 public static void shellSort(int[] array) { 
 int j, temp, k = 0;
 for (int gap = array.length / 2; gap >= 1; gap /= 2) { 
 // 对子序列进行插入排序
 for (int i = gap; i < array.length; i++) { 
 temp = array[i]; // 取无序组第一个元素，此元素即为待插入元素
 j = i - gap; // i-gap 为有序组最后一个元素
 // 按从后向前的顺序，将待插入元素与有序组元素逐个比较
 while (j >= 0 && temp < array[j]) { 
 array[j+gap] = array[j];// 若不是合适位置，有序组元素向后移动
 j -= gap;
 }
 array[j+gap] = temp; // 找到合适位置，将元素插入
 }
 
 System.out.print("第" + ++k + "步排序结果：");
 Arrays.stream(array).mapToObj(item -> item + " ").forEach(System.out::print);
 System.out.println();
 }
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 
 shellSort(array);
 System.out.println("排序后的数组为：");
 for (int i = 0; i < array.length; i++) { 
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 }
 }

排序前的数组为：
    199 136 110 131 193 102 141 102 193 122 
    120 175 162 102 117 197 119 105 136 162 
    第1步排序结果：120 136 110 102 117 102 119 102 136 122 199 175 162 131 193 197 141 105 193 162 
    第2步排序结果：102 119 102 102 117 120 136 105 131 122 197 141 110 136 162 199 175 162 193 193 
    第3步排序结果：102 102 102 105 110 119 117 120 131 122 136 136 162 141 175 162 193 193 197 199 
    第4步排序结果：102 102 102 105 110 117 119 120 122 131 136 136 141 162 162 175 193 193 197 199 
    排序后的数组为：
    102 102 102 105 110 117 119 120 122 131 
    136 136 141 162 162 175 193 193 197 199 
    
    Process finished with exit code 0

## 2.2 交换排序 ##

### 1 冒泡排序 ###

**a 算法原理**

从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称之为一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”（或关键字最大的元素如石头一般下沉至水底）。

下一趟冒泡时，前一趟确定的最小元素不再参与比较，每一趟冒泡，序列中的最小元素（或最大元素）放到了序列的最前端（最后端），因此，**每一趟冒泡都至少有一个元素的最终位置被确定**，最多做 n-1 趟冒泡就能把所有元素排好序。

为增进算法性能，可设置一个标志变量 `flag`，在每一趟冒泡前，置其值为 false，若有元素发生交换，则置其值为 true，每一趟冒泡结束，检测其值是否改变，若没有改变，则元素已有序，直接退出排序，否则进行新一轮冒泡。否则的话每次排序都要进行 n-1 趟冒泡，在对元素基本有序的元素进行排序时就会浪费时间。

**b 性能分析**

*  空间效率：仅使用常数个辅助单元，空间复杂度为 O ( 1 ) O(1) O(1)
 *  时间效率
    
     *  最好情况：元素已经有序，只需进行 n-1 次比较即可，没有元素移动，时间复杂度为 O ( n ) O(n) O(n)
     *  最坏情况：元素顺序与排序结果逆序，要进行 n-1 趟排序，第 i 趟排序要比较 n-i 次，且每次比较都需要交换元素，且每次交换操作次数为3（`temp = a; a = b; b = temp;`），共移动 3(n-i)次，故总次数为 ∑ i = 1 n − 1 ( n − i ) + 3 ∗ ( n − i ) = 2 n ( n − 1 ) \\displaystyle \\sum\_\{i=1\}^\{n-1\}(n-i)+3\*(n-i)=2n(n-1) i=1∑n−1(n−i)\+3∗(n−i)=2n(n−1)，故时间复杂度为 O ( n 2 ) O(n^2) O(n2)
 *  稳定性：假设升序排序，只有后一个元素大于前一个元素才会发生交换，相同关键字元素相对位置不变，因此冒泡排序是稳定的排序算法

public class BubbleSortDemo { 
 static final int SIZE = 30;
 
 public static void bubbleSort(int[] array) { 
 int temp;
 for (int i = 1; i < array.length; i++) { 
 for (int j = 0; j < array.length - i; j++) { 
 // 将数组升序排序
 if (array[j] > array[j+1]) { 
 temp = array[j];
 array[j] = array[j+1];
 array[j+1] = temp;
 }
 }
 }
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 
 bubbleSort(array);
 System.out.println("排序后的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 }
 }

排序前的数组为：
    108 163 175 158 102 116 137 136 163 153 
    196 190 156 167 189 191 188 178 187 169 
    排序后的数组为：
    102 108 116 136 137 153 156 158 163 163 
    167 169 175 178 187 188 189 190 191 196 
    
    Process finished with exit code 0

### 2 快速排序 ###

**a 算法原理**

每趟排序选择一个`基准元素 base`(通常选取序列首元素)，通过一趟排序将先前序列划分成两个子序列，使得前一个子序列 L \[ 1... k − 1 \] L\[1...k-1\] L\[1...k−1\]的所有元素小于 base，后一个子序列 L \[ k + 1... n \] L\[k+1...n\] L\[k\+1...n\]的所有元素大于 base，base 最终落在 L \[ k \] L\[k\] L\[k\]的位置，然后递归地对所有子序列进行同样操作，直到最后序列有序。

--------------------

**①排序方法一**

假设有一个由若干数据组成的序列，

1. 取第一个数据为基准数据 base，指针 i 指向base后第一个数据，指针 j 指向最后一个数据；
2. 当 i < j 时：先递减 j，从后向前搜索小于 base 的数据，再递增 i ，从前向后搜索大于 base 的数据，若找到，则交换；继续递减 j，递增 i 进行同样的操作，直至 i == j
3. 当 i == j 时：交换 base 和 array\[i\]，则 base 左侧的数据都小于 base，base 右侧的数据都大于base，此时一次排序结束，序列被分成两个子序列
4. 对每个序列重复使用步骤1、2、3

array\[10\] = \{ 150 107 182 178 183 154 141 138 182 169 \}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 3]

--------------------

**①排序方法二**

假设有一个由若干数据组成的序列，

1. 取第一个数据为基准数据 base，指针 i 指向 base，指针 j 指向最后一个数据；
2. 当 i < j 时： 
 先递减 j，从后向前搜索小于 base 的数据，若找到，则交换 array\[i\]、array\[j\]； 
 再递增 i ，从前向后搜索大于 base 的数据，若找到，则交换 array\[i\]、array\[j\]； 
 继续递减 j，递增 i 进行同样的操作，直至 i == j
3. 当 i == j 时：将 array\[i\] 的值置为 base，则 base 左侧的数据都小于 base，base 右侧的数据都大于base，此时一次排序结束，序列被分成两个子序列
4. 对每个序列重复使用步骤1、2、3

快速排序的性能与**子序列划分的对称程度**有关，越趋于对称（元素越无序），则性能越好，否则越差（元素越有序）。最坏情况下，一个子序列含有 n-1 个元素，另一个子序列含有 0 个元素，而且每次划分都是此种情况，则递归调用次数最多，运行时间最长。理想情况下，每次划分都是对称的，即左右子序列元素个数基本相同。

*  空间效率：需要使用递归工作栈来保存函数调用，栈容量与递归调用的最大深度一致。最好情况下为 O ( l o g 2 n ) O(log\_2n) O(log2n)，最坏情况下为 O ( n ) O(n) O(n)
 *  时间效率：元素越有序，性能越差，最差的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
 *  稳定性：两个子序列元素交换可能使相同关键字元素相对位置改变，因此快速排序是不稳定的排序算法。

**快速排序算法是所有内部排序算法中平均性能最好的**。

**c 适用范围**

元素无序程度越高越适用。

import java.util.Arrays;
 
 public class QuickSortDemo { 
 static final int SIZE = 20;
 static int k = 0;
 
 public static void quickSort(int[] array, int left, int right) { 
 // 数组长度为 0 或 1 时直接退出
 if (array == null || left > right || (array.length - 1 <= 0))
 return;
 
 int base = array[left]; // base：基准数据
 int i = left, j = right;// 让 i 指向数据最左侧，让 j 指向数据最左侧
 int temp;
 while (i != j) { 
 // 从右向左搜寻小于 base 的数据
 while (array[j] >= base && i < j)
 j--;
 // 从左向右搜寻大于 base 的数据
 while (array[i] <= base && i < j)
 i++;
 
 // 交换搜寻到的数据
 if (i < j) { 
 temp = array[i];
 array[i] = array[j];
 array[j] = temp;
 }
 }
 
 // 将基准数放到中间的位置（基准数归位）
 array[left] = array[i];
 array[i] = base;
 /*temp = array[i]; array[i] = array[left]; array[left] = temp;*/
 // 一次排序结束，此时 base 左侧的数据全小于 base，右侧的数据全大于base
 
 quickSort(array, left, i - 1); // 快排 base 左侧数据
 quickSort(array, i + 1, right);// 快排 base 右侧数据
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 }
 
 quickSort(array, 0, array.length - 1);
 System.out.println("\n排序后的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 System.out.printf("%d ", array[i]);
 }
 }
 }

排序前的数组为：
    100 156 179 151 179 175 122 113 106 155 149 173 144 106 147 128 103 172 170 159 
    排序后的数组为：
    100 103 106 106 113 122 128 144 147 149 151 155 156 159 170 172 173 175 179 179 
    Process finished with exit code 0

## 2.3 选择排序 ##

### 1 简单选择排序 ###

此算法与直接插入排序有异曲同工之处。

**a 算法原理**

**理解方式一：**

设有 n 个元素的顺序表  L \[ 1 … n \] L\[1\\dots n\] L\[1…n\]，假设下标从 1 开始，按升序排序：

第  i ( 1 ≤ i ≤ n ) i(1\\leq i\\leq n) i(1≤i≤n) 趟排序，从后 n-i+1 个元素中选取最小元素，将其与 L \[ i \] L\[i\] L\[i\]交换位置。

**理解方式二：**

<table> 
 <thead> 
 <tr> 
 <th> 有 序 列 表 L [ 1... i ] 有序列表L[1...i] 有序列表L[1...i]</th> 
 <th> 无 序 列 表 L [ i + 1... n ] 无序列表L[i+1...n] 无序列表L[i+1...n]</th> 
 </tr> 
 </thead> 
 <tbody></tbody> 
</table>

1.  将一组数据分成两组，分别为有序组、无序组（第一次有序组无元素，无序组元素个数为n）
2.  选出无序组中最小元素 L \[ m i n \] ， i + 1 ≤ m i n ≤ n L\[min\]，i+1\\leq min\\leq n L\[min\]，i\+1≤min≤n，将其与有序组尾元素 L \[ i \] L\[i\] L\[i\]后一个元素交换位置
3.  重复第 2 步 n-1 次

**b 性能分析**

*  空间效率：仅使用常数个辅助单元，空间复杂度为 O ( 1 ) O(1) O(1)
 *  时间效率：元素的比较次数与数组初始状态无关，因为挑选最小元素时，需要与无序组每个元素进行比较，固定次数为 ∑ i = 1 n − 1 = n ( n − 1 ) / 2 \\displaystyle \\sum\_\{i=1\}^\{n-1\}=n(n-1)/2 i=1∑n−1=n(n−1)/2。最坏情况下（元素顺序与排序结果逆序），每个元素都需要交换，则最多交换次数为 3 ( n − 1 ) 3(n-1) 3(n−1)，故时间复杂度为 O ( n 2 ) O(n^2) O(n2)
 *  稳定性：元素交换时可能会使相同关键字的元素交换，因此不稳定

**c 适用范围**  
元素越有序越适用，只需比较，无需交换。元素逆序，最不适用，每次都要交换元素。

public class SelectSortDemo { 
 static final int SIZE = 20;
 public static void selectSort(int[] array) { 
 int index, temp;
 
 for (int i = 0; i < array.length - 1; i++) { 
 index = i;
 for (int j = i + 1; j < array.length; j++) { 
 // 若剩余 n-(i+1) 个数据中有小于 a[i]的，则记录该元素下标
 if (array[j] < array[index])
 index = j;
 }
 
 if (index != i) { 
 temp = array[i];
 array[i] = array[index];
 array[index] = temp;
 }
 }
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 
 selectSort(array);
 System.out.println("排序后的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 System.out.printf("%d ", array[i]);
 if ((i + 1) % 10 == 0)
 System.out.println();
 }
 }
 }

排序前的数组为：
    117 118 164 136 182 143 169 181 120 159 
    131 116 149 138 140 166 166 141 138 158 
    排序后的数组为：
    116 117 118 120 131 136 138 138 140 141 
    143 149 158 159 164 166 166 169 181 182 
    
    Process finished with exit code 0

### 2 堆排序 ###

堆排序的关键是首先构造堆结构。堆结构是一种树结构,准确地说是一个**完全二叉树**。在这个树中每个结点对应于原始数据的一个记录,并且每个结点应满足以下条件:

<table> 
 <thead> 
 <tr> 
 <th>大顶堆</th> 
 <th>小顶堆</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>非叶结点的数据 &gt;= 其左、右子结点的数据</td> 
 <td>非叶结点的数据 &lt;= 其左、右子结点的数据</td> 
 </tr> 
 <tr> 
 <td>下标从1开始： L [ i ] ≥ L [ 2 i ] &amp; L [ i ] ≥ L [ 2 i + 1 ] L[i]\geq L[2i]\&amp;L[i]\geq L[2i+1] L[i]≥L[2i]&amp;L[i]≥L[2i+1] 下标从0开始： L [ i ] ≥ L [ 2 i + 1 ] &amp; L [ i ] ≥ L [ 2 i + 2 ] L[i]\geq L[2i+1]\&amp;L[i]\geq L[2i+2] L[i]≥L[2i+1]&amp;L[i]≥L[2i+2]</td> 
 <td>下标从1开始： L [ i ] ≤ L [ 2 i ] &amp; L [ i ] ≤ L [ 2 i + 1 ] L[i]\leq L[2i]\&amp;L[i]\leq L[2i+1] L[i]≤L[2i]&amp;L[i]≤L[2i+1] 下标从0开始： L [ i ] ≤ L [ 2 i + 1 ] &amp; L [ i ] ≤ L [ 2 i + 2 ] L[i]\leq L[2i+1]\&amp;L[i]\leq L[2i+2] L[i]≤L[2i+1]&amp;L[i]≤L[2i+2]</td> 
 </tr> 
 </tbody> 
</table>

**a 算法原理**

将表中元素构造成一个大顶堆，将堆顶元素(最大元素)与堆底元素交换，此时最大元素送到末尾。由于堆顶元素与堆底元素交换，堆结构被破坏，再重新构造堆，再交换…**重复构造堆、交换元素的过程**，则最后元素有序。

此算法中有两个关键点，一是**构造初始堆**，而是交换元素后**调整堆**。

--------------------

从根节点开始，从左到右、从上到下对每个节点编号，起始序号为 0 或 1，下面以 1 开始

1.  构造堆：从`最后一个非叶节点开始`到`第一个非叶节点结束`构造堆（从右到左，从下到上）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 5]
2.  调整堆  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 7]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 8]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 9]  
    ![在这里插入图片描述][20200530175707296.jpg]  
    ![在这里插入图片描述][20200530175707646.jpg]

![在这里插入图片描述][20200530175707310.jpg]

**b 性能分析**

*  空间效率：仅使用常数个辅助单元，空间复杂度为 O ( 1 ) O(1) O(1)
 *  时间效率：建堆时间为 O ( n ) O(n) O(n)，之后有 n-1 次向下调整，每次调整次数为树的高度 h( O ( h ) = O ( l o g 2 n ) O(h)=O(log\_2n) O(h)=O(log2n))，故时间复杂度为 O ( l o g 2 n ) ∗ O ( n − 1 ) = O ( n l o g 2 n ) O(log\_2n)\*O(n-1)=O(nlog\_2n) O(log2n)∗O(n−1)=O(nlog2n)
 *  稳定性：元素交换时可能会使相同关键字的元素交换，因此不稳定

**c 适用范围**  
元素越有序越适用，只需比较，无需交换。元素逆序，最不适用，每次都要交换元素。

import java.util.Arrays;
 
 public class HeapSortDemo { 
 static final int SIZE = 20;
 static int k = 0;
 
 public static void heapSort(int[] array) { 
 // 数组长度为 0 或 1 时直接退出
 if (array == null || (array.length - 1 <= 0))
 return;
 
 // i 初始化值为最后一个非叶节点序号
 for (int i = array.length / 2 - 1; i >= 0; i--) { 
 //从最后一个非叶结点开始，从下到上，从右到左调整堆结构
 adjustHeap(array, i, array.length);
 }
 
 int temp;
 for (int i = array.length - 1; i > 0; i--) { 
 // 交换堆顶元素与末尾元素
 temp = array[i];
 array[i] = array[0];
 array[0] = temp;
 
 // 除末尾元素外，继续调整剩余元素
 adjustHeap(array, 0, i);
 }
 }
 
 public static void adjustHeap(int[] array, int i, int length) { 
 int temp = array[i];
 // 将完全二叉树从根节点开始，从上到下、从左到右对每个节点编号，起始序号为 0（root）
 // 则，序号为 i 的节点：左子树序号为 2*i+1，右子树序号为 2*i+2
 
 // 从 i 开始调整堆，然后调整 i 的左子树...
 // j 起始为 i 左子树，j 下一次变化为 j 的左子树，以此类推
 for (int j = i * 2 + 1; j < length; j = j * 2 + 1) { 
 // 若 i 有右子树，且右子树 > 左子树，则令 j 指向 i 右子树
 if (j + 1 < length && array[j] < array[j + 1])
 j++;
 
 // 若 i 的子树 > i，则令 i 为较大值
 if (array[j] > temp) { 
 array[i] = array[j];
 i = j; // 令 i 指向被改变的子树
 } else { 
 break;
 }
 
 // 将 i 的原始值赋给被改变的子树
 array[i] = temp;
 }
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 }
 
 heapSort(array);
 System.out.println("\n排序后的数组为：");
 Arrays.stream(array).mapToObj(e -> e + " ").forEach(System.out::print);
 }
 }

排序前的数组为：
    114 113 178 147 132 101 121 139 184 116 140 143 187 168 187 127 168 193 147 192 
    排序后的数组为：
    101 113 114 116 121 127 132 139 140 143 147 147 168 168 178 184 187 187 192 193 
    Process finished with exit code 0

## 2.4 归并排序 ##

一个待排序的原始数据序列进行合并排序的基本思路是,首先将含有n个结点的待排序数据序列看作由n个长度为1的有序子表组成,将其依次两两合并,得到长度为2的若干有序子表;然后,再对这些子表进行两两合并,得到长度为4的若干有序子表……,重复上述过程,一直到最后的子表长度为,从而完成排序过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 10]

import java.util.Arrays;
 
 public class MergeSortDemo { 
 static final int SIZE = 20;
 public static void mergeSort(int[] array, int low, int high, int[] temp) { 
 if (low < high) { 
 int mid = (low + high) / 2;
 mergeSort(array, low, mid, temp);
 mergeSort(array, mid + 1, high, temp);
 merge(array, low, mid, high, temp);
 }
 }
 
 private static void merge(int[] array, int low, int mid, int high, int[] temp) { 
 // j 为左边序列起始索引，k 为右边序列起始索引
 int i = 0, j = low, k = mid + 1;
 
 // 将两个序列中较小值移入 temp
 while (j <= mid && k <= high) { 
 if (array[j] < array[k])
 temp[i++] = array[j++];
 else
 temp[i++] = array[k++];
 }
 
 // 将左边序列剩余元素移入 temp
 while (j <= mid)
 temp[i++] = array[j++];
 // 将右边序列剩余元素移入 temp
 while (k <= high)
 temp[i++] = array[k++];
 // 用 temp 数组覆盖 array 数组
 for (int l = 0; l < i; l++) { 
 array[low + l] = temp[l];
 }
 }
 
 public static void main(String[] args) { 
 int[] array = new int[SIZE];
 int[] temp = new int[array.length];
 
 System.out.println("排序前的数组为：");
 for (int i = 0; i < SIZE; i++) { 
 // 产生 100~199 之间的随机数
 array[i] = (int) (100 + Math.random() * 100);
 System.out.printf("%d ", array[i]);
 }
 
 mergeSort(array, 0, array.length - 1, temp);
 System.out.printf("\n排序后的数组为：\n%s\n", Arrays.toString(array));
 }
 }

排序前的数组为：
    179 116 138 161 101 146 196 114 168 118 162 152 106 158 103 173 103 160 188 128 
    排序后的数组为：
    [101, 103, 103, 106, 114, 116, 118, 128, 138, 146, 152, 158, 160, 161, 162, 168, 173, 179, 188, 196]
    
    Process finished with exit code 0

## 2.5 基数排序 ##

# 3 算法执行效率 #

在排序算法中还有一个特殊的概念,即稳定排序算法。稳定排序算法主要依照相等的关键字维持记录的相对次序来进行排序。通俗地讲,对于两个有相等关键字的数据 D1 和 D2,在待排序的数据中 D1 出现在 D2 之前,在排序过后的数据中 D1 也在 D2 之前,那么这就是一个稳定排序算法。

*  冒泡排序算法、插入排序算法、合并排序算法都是稳定排序算法
 *  选择排序算法、Shell排序算法、快速排序算法、堆排序算法都不是稳定排序算法。

没有一种排序算法是绝对好的,不同的排序算法各有优劣。在实际应用中,需要根据实际的问题来选择合适的排序算法。

*  如果数据量 n 较小,可采用插入排序法、选择排序法;
 *  如果数据量 n 较大时,应采用时间复杂度为 O( n l o g 2 n nlog\_2n nlog2n) 的排序方法,如快速排序、堆排序、合并排序。
 *  如果待排序的原始数据呈随机分布,那么快速排序算法的平均时间最短。

<table> 
 <thead> 
 <tr> 
 <th>算法种类</th> 
 <th>时间复杂度(最好)</th> 
 <th>时间复杂度(平均)</th> 
 <th>时间复杂度(最坏)</th> 
 <th>空间复杂度</th> 
 <th>是否稳定</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>直接插入排序</td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>√</td> 
 </tr> 
 <tr> 
 <td>冒泡排序</td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>√</td> 
 </tr> 
 <tr> 
 <td>简单选择排序</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>×</td> 
 </tr> 
 <tr> 
 <td>希尔排序</td> 
 <td>取决于</td> 
 <td>所选用的</td> 
 <td>增量函数</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>×</td> 
 </tr> 
 <tr> 
 <td>快速排序</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( l o g 2 n ) O(log_2n) O(log2n)</td> 
 <td>×</td> 
 </tr> 
 <tr> 
 <td>堆排序</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>×</td> 
 </tr> 
 <tr> 
 <td>2路归并排序</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>√</td> 
 </tr> 
 <tr> 
 <td>基数排序</td> 
 <td> O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))</td> 
 <td> O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))</td> 
 <td> O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))</td> 
 <td> O ( r ) O(r) O(r)</td> 
 <td>√</td> 
 </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210326201509208.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200208222433397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200208221221729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200208221618667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/202002082323272.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200530145615315.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200530172045365.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200530175707524.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200530175707747.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200530175707556.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200530175707620.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[20200530175707296.jpg]: https://img-blog.csdnimg.cn/20200530175707296.jpg
[20200530175707646.jpg]: https://img-blog.csdnimg.cn/20200530175707646.jpg
[20200530175707310.jpg]: https://img-blog.csdnimg.cn/20200530175707310.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200206185721987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70