常用排序算法原理分析及Java代码实现

妖狐艹你老母 2023-10-09 14:59 9阅读 0赞

**参考链接：**

*  [十大经典排序算法(冒泡、选择、插入、希尔、快排..........)\_HH~LL的博客-CSDN博客\_十大排序算法][.........._HH_LL_-CSDN]
 *  [排序算法详细讲解（超酷）\_mu'mu的博客-CSDN博客\_排序算法][mu_mu_-CSDN]
 *  [数据结构——八大排序算法（面试必备）\_Baret-H的博客-CSDN博客\_八大排序算法][Baret-H_-CSDN]
 *  [六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序\_双鱼211的博客-CSDN博客\_六大算法][211_-CSDN]
 *  [超详细十大经典排序算法总结（java代码）c或者cpp的也可以明白\_Top\_Spirit的博客-CSDN博客\_排序算法][java_c_cpp_Top_Spirit_-CSDN]

**排序算法作为数据结构中重要的组成部分，必须要掌握。**

## 1. 相关术语介绍 ##

**排序：**将一序列对象根据某个关键字进行排序。

**稳定排序：**如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

**非稳定排序**：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

**内排序**：所有排序操作都在内存中完成；

**外排序**：由于数据太大，因此需要把数据放在磁盘中，而排序需要通过磁盘和内存的数据传输才能进行；

**时间复杂度：**排序所耗费的时间；

**空间复杂度：**排序所耗费的内存；

**比较类排序：**通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为**非线性时间比较类排序**。

**非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为**线性时间非比较类排序**。

## 2. 排序算法分类以及对应复杂度 ##

### 2.1 排序算法分类 ###

#### 2.1.1 按照比较类排序、非比较类排序进行分类 ####

*  **比较类排序：**

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。

**优势**：适用于各种规模的数据，不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

*  **非比较类排序**

计数排序、基数排序、桶排序则属于非比较排序 。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr\[i\]之前有多少个元素，则唯一确定了arr\[i\]在排序后数组中的位置 。

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置，所以对数据规模和数据分布有一定的要求。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

#### 2.1.2 按照内部排序、外部排序进行分类 ####

![img][]

其他分类待完善

### 2.2 不同排序算法的复杂度以及稳定性 ###

![image][]

**图片名词解释：**

*  **n**: 数据规模
 *  **k**: “桶”的个数
 *  **In-place**: 占用常数内存，不占用额外内存
 *  **Out-place**: 占用额外内存

## 3. 冒泡排序/相邻比序法---交换排序 ##

### 3.1 算法思想 ###

冒泡排序是一种简单的排序算法。它通过重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换的，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。即：从要排序序列的第一个元素开始，一次比较相邻元素的值，发现逆序则交换，将值较大的元素逐渐从前向后移动。

### 3.2 实现逻辑 ###

主要通过两层循环实现

*  外层循环代表需要比较几轮/趟，即每次将最大的一个数放到最后所需要的次数。
 *  内层循环代表两两需要对比多少次，比如n个数据第1次两两比较需要n-1次，第2次两两比较需要n-2次，以此类推。

**举例：**

![img][img 1]

### 3.3 Java代码实现 ###

package sort;
     
     import java.util.Arrays;
     import java.util.Random;
     
     /**
      * @ClassName BubbleSort
      * @Description 冒泡排序
      * @Author Jiangnan Cui
      * @Date 2022/10/19 0:11
      * @Version 1.0
      */
     public class BubbleSort {
         public static void main(String[] args) {
             int[] arr = {4,2,6,3,5,9,8,7,0,1};
             System.out.println("原始数组为：" + Arrays.toString(arr));
             bubbleSort(arr);
             System.out.println("冒泡排序后数组为：" + Arrays.toString(arr));
             int[] arr2 = {4,2,6,3,5,9,8,7,0,1};
             bubbleSort2(arr2);
             System.out.println("冒泡排序优化后数组为：" + Arrays.toString(arr2));
     
             System.out.println("测试冒泡快速排序数组性能：");
             testSort(10);
             testSort(100);
             testSort(1000);
             testSort(10000);
             testSort(100000);
             testSort(1000000);
             testSort(10000000);
             testSort(100000000);
         }
     
         /**
          * @MethodName bubbleSort
          * @Description 冒泡排序
          * @param: arr
          * @return: int[]
          * @Author Jiangnan Cui
          * @Date 0:31 2022/10/19
          */
         public static int[] bubbleSort(int[] arr){
             // 数组中不包含或只包含1个元素时，直接返回
             if(arr.length == 0 || arr.length == 1){
                 return arr;
             }
             // 数组中多于1个元素时进行冒泡排序
             // 外层循环控制循环躺数
             for (int i = 0; i < arr.length - 1; i++) {
                 // 内层循环控制两两两比较次数
                 for (int j = 0; j < arr.length - 1 - i; j++) {
                     // 前一个元素大于后一个元素时，进行交换
                     if (arr[j] > arr[j + 1]) {
                         swap(j, j+1, arr);
                     }
                 }
             }
             return arr;
         }
     
         /**
          * @MethodName bubbleSort2
          * @Description 冒泡排序优化：如果某趟排序中，没有发生交换，则可结束排序
          * @param: arr
          * @return: int[]
          * @Author Jiangnan Cui
          * @Date 0:31 2022/10/19
          */
         public static int[] bubbleSort2(int[] arr){
             // 数组中不包含或只包含1个元素时，直接返回
             if(arr.length == 0 || arr.length == 1){
                 return arr;
             }
             boolean flag = false;// 标志位，用来表示没有发生过交换
             // 数组中多于1个元素时进行冒泡排序
             // 外层循环控制循环躺数
             for (int i = 0; i < arr.length - 1; i++) {
                 // 内层循环控制两两两比较次数
                 for (int j = 0; j < arr.length - 1 - i; j++) {
                     // 前一个元素大于后一个元素时，进行交换
                     if (arr[j] > arr[j + 1]) {
                         swap(j, j+1, arr);
                         flag = true;
                     }
                 }
                 // 某趟没有发生过交换，直接结束排序
                 if(!flag){
                     break;
                 } else{
                     flag = false;// 发生过交换时，重置标志位，方便下次判断
                 }
             }
             return arr;
         }
     
         /**
          * @MethodName swap
          * @Description 交换数组中的两个元素
          * @param: i
          * @param: j
          * @param: arr
          * @Author Jiangnan Cui
          * @Date 0:19 2022/10/19
          */
         private static void swap(int i, int j,int[] arr) {
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     
         /**
          * @MethodName testSort
          * @Description 测试排序方法性能
          * @param: length 测试数组的长度
          * @return: int[]
          * @Author Jiangnan Cui
          * @Date 16:04 2022/10/23
          */
         private static void testSort(int length){
             if(length <= 0){
                 throw new RuntimeException("数组长度不满足要求！！！");
             }
             // 定义一个数组
             int[] arr = new int[length];
             // 利用生成的随机数给数组赋值
             Random random = new Random();
             for (int i = 0; i < arr.length - 1; i++) {
                 // 如果不传递参数，随机数的范围是int范围
                 int num = random.nextInt();
                 arr[i] = num;
             }
             // 记录排序之前开始时间，单位为毫秒ms
             long startTime = System.currentTimeMillis();
             // 排序
             bubbleSort(arr);
             // 记录排序之后结束时间，单位为毫秒ms
             long endTime = System.currentTimeMillis();
             System.out.println("数组长度为" + length + "时，排序耗时：" + (endTime - startTime) + "ms");
         }
     }

**输出结果：**

原始数组为：[4, 2, 6, 3, 5, 9, 8, 7, 0, 1]
     冒泡排序后数组为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
     冒泡排序优化后数组为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

### 3.4 复杂度分析 ###

**时间复杂度：**总共执行次数n-1,n-2,......，2,1，等差数列求和为n\*(n-1)/2，即最高次项为n^2，故时间复杂度为O(n^2）；

*  最佳情况：O(n)，即第1趟循环时发现已经排好序了
 *  最差情况：O(n^2)，所有情况均执行。
 *  平均情况：O(n^2)

**空间复杂度：**有限个变量占用空间i、j，故时间复杂度为O(1)；

**稳定性分析：**相同元素比较时不交换顺序，故稳定。

## 4. 快速排序 ##

**快速排序（Quicksort）是对冒泡排序的一种改进。**冒泡排序一次只能消除一个逆序，快速排序中的一次交换可能消除多个逆序。

### 4.1 基础快速排序(一路：递归+非递归) ###

#### 4.1.1 算法思想 ####

从待排序的数据中选取一个元素为**基准值**，然后将小于基准值的元素放到基准值的前面，将大于等于基准值的元素放到基准值的后面。这样就将待排序的数据分为俩个子表，将这个过程称为一趟快速排序。对分割后的子表继续按照上面的方法进行操作，直至所有子表的表长不超过1为止，此时待排序数据序列就变成了一个有序表。

那么现在就得思考**如何取基准值**？大家都希望基准值是数据序列中值为中间的元素，可是现在序列还是一个无序表，又怎么找呢？因此基准值的三种较为常用的取法中，**三数取中法**是更为合适的。

**基准值较常使用的取法共有三种：**

1.  最左侧的元素
2.  最右侧的元素
3.  三数取中法：最左侧的元素、最右侧的元素和中间的元素进行比较，选择值不大不小的元素作为基准值。

**关于基准值的选取：**

1. 选择边界上（左或者右），注意在接近有序的数组上，快排退化成O(n^2)时间复杂度，左右区间严重不平衡

2. 随机选择

3. 几数取中（例如三数取中）(array\[left\], array\[mid\], array\[right\] 大小是中间的为基准值)

2和3基准值的选择方法在接近有序的数组上，都能避免递归过程中，快速排序分区严重不平衡的问题。

问题：当数组中重复元素较多时，就会导致分区后某个区间元素过多，会递归过程中，递归树严重不平衡，快排时间复杂度倒退到O(n^2)。

为解决此问题，衍生出了两种解决方法：二路快排和三路快排

#### 4.1.2 实现逻辑 ####

**具体实现：**

1.  选择基准值：从待排序序列中选择一个数，作为基准值(pivot)；
2.  分区：遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
3.  采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

**过程演示：**

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

1.  以基准值选取最左侧的元素为例，对整个数组进行分区，j为分区点，橙色为小于基准值的区间（arr\[l+1,j\]），紫色为大于基准值的区间（arr\[j+1,i)），其中，i为正在遍历的元素，j为小于基准值区间元素的最后一个值，j+1为大于基准值区间元素的第一个值。
2.  将遍历的元素与基准值进行比较，有两种情况：

*  case1: 如果arr\[i\] >= v，则橙色区域长度不变、紫色区域长度加1，同时i++，继续向右遍历；

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

*  case2: 如果arr\[i\]<v，则将紫色区域第一个大于等于v的元素与当前元素进行交换，使橙色区域长度加1，紫色区域长度不变，但位置向右移动一位，同时i++，继续向右遍历；

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

1.  第一次将整个集合扫描完，整个区间被分为三部分：

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]

此时交换arr\[j\]和arr\[l\]，继续在两个区间上重复上述过程。

#### 4.1.3 Java代码实现 ####

package sort;
     
     import java.util.ArrayDeque;
     import java.util.Arrays;
     import java.util.Deque;
     import java.util.Random;
     
     /**
      * @ClassName QuickSort
      * @Description 快递排序
      * @Author Jiangnan Cui
      * @Date 2022/10/20 23:30
      * @Version 1.0
      */
     public class QuickSort {
         public static void main(String[] args) {
             int[] arr = {4,2,6,3,5,9,8,7,0,1};
             System.out.println("原始数组为：" + Arrays.toString(arr));
             quickSort1Recursion(arr);
             System.out.println("基础(一路)快速递归排序后数组为：" + Arrays.toString(arr));
             int[] arr2 = {4,2,6,3,5,9,8,7,0,1};
             quickSort1NonRecursion(arr2);
             System.out.println("基础(一路)快速非递归排序后数组为：" + Arrays.toString(arr2));
     
             System.out.println("测试一路快速排序数组性能：");
             testSort(10);
             testSort(100);
             testSort(1000);
             testSort(10000);
             testSort(100000);
             testSort(1000000);
             testSort(10000000);
             testSort(100000000);
         }
     
         /**
          * 基础快速排序递归基础版（一路快速排序）
          * @param arr
          */
         public static void quickSort1Recursion(int[] arr){
             quickSort1RecursionInternal(arr, 0, arr.length - 1);
         }
     
         /**
          * @MethodName quickSort1RecursionInternal
          * @Description 在arr[left,..,right]上利用分治算法递归快速排序
          * @param: arr 待排序数组
          * @param: left 左边界下标索引
          * @param: right 右边界下标索引
          * @Author Jiangnan Cui
          * @Date 23:33 2022/10/20
          */
         private static void quickSort1RecursionInternal(int[] arr, int left, int right) {
             // 如果左边界索引>右边界索引时，说明区间不合法 或 只有一个元素时，直接结束
             if(left >= right){
                 return;
             }
             // 随机在当前数组中选一个数作为基准值，此处以选择最左侧元素作为基准值进行说明
             int base = arr[left];
             // 默认分区点j最开始在最左侧，即j与left位置相同
             int j = left;
             // i表示当前正在遍历的元素，从left的下一个元素开始遍历，到达右边界时截止
             for (int i = left + 1; i <= right; i++) {
                 // 将遍历的元素与基准值进行比较，如果遍历的元素值比基准值小，放在左侧
                 if(arr[i] < base){
                     // 将大于等于基准值区间第一个元素与当前元素进行交换
                     swap(arr, j+1, i);
                     // j继续向右移动
                     j++;
                 }
                 // 此处默认遍历的元素值比基准值大时位置不动，即只有小于时才移动左侧
             }
             // 遍历完成后，最后一次将基准值和最后一个小于v的元素作交换，基准值就落在了最终的位置
             swap(arr, left, j);
             // 分别在左右侧区间上进行快速排序
             quickSort1RecursionInternal(arr, left, j - 1);
             quickSort1RecursionInternal(arr, j + 1, right);
         }
     
         /**
          * @MethodName quickSort1NonRecursion
          * @Description 2.借助栈来实现非递归分治快排：注意栈是先进后出
          * @param: arr
          * @Author Jiangnan Cui
          * @Date 11:13 2022/10/22
          */
         public static void quickSort1NonRecursion(int[] arr) {
             // 利用栈来存取元素
             Deque<Integer> stack = new ArrayDeque<>();
             // 栈中保存当前集合的开始位置和终止位置
             int l = 0;
             int r = arr.length - 1;
             stack.push(r);
             stack.push(l);
             // 当栈不为空时进行操作，说明子区间还没有处理完毕
             while (!stack.isEmpty()) {
                 // 从栈中取出元素
                 int left = stack.pop();
                 int right = stack.pop();
                 // 区间只有一个元素
                 if (left >= right) {
                     // 结束本次循环
                     continue;
                 }
                 // 分区
                 // 随机在当前数组中选一个数作为基准值，此处以选择最左侧元素为例
                 int v = arr[left];
                 // 默认最开始j在最左侧，即j与left位置相同
                 int j = left;
                 // i表示当前正在遍历的元素，从left的下一个元素开始遍历，到达右边界时截止
                 for (int i = left + 1; i <= right; i++) {
                     // 将遍历的元素与基准值进行比较，如果遍历的元素值比基准值小，放在左侧
                     if(arr[i] < v){
                         // 将大于等于基准值区间第一个元素与当前元素进行交换
                         swap(arr, j+1, i);
                         // j继续向右移动
                         j++;
                     }
                     // 此处默认遍历的元素值比基准值大时位置不动，即只有小于时才移动左侧
                 }
                 // 遍历完成后，最后一次将基准值和最后一个小于v的元素作交换，基准值就落在了最终的位置
                 swap(arr, left, j);
                 // 依次将右区间的开始和结束位置入栈
                 stack.push(right);
                 stack.push(j + 1);
                 // 再将左侧区间的开始和结束位置入栈
                 stack.push(j - 1);
                 stack.push(left);
             }
         }
     
         /**
          * @MethodName swap
          * @Description 交换数组中的两个元素
          * @param: i
          * @param: j
          * @param: arr
          * @Author Jiangnan Cui
          * @Date 23:30 2022/10/20
          */
         private static void swap(int[] arr, int i, int j) {
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     
         /**
          * @MethodName testSort
          * @Description 测试排序方法性能
          * @param: length 测试数组的长度
          * @return: int[]
          * @Author Jiangnan Cui
          * @Date 16:04 2022/10/23
          */
         private static void testSort(int length){
             if(length <= 0){
                 throw new RuntimeException("数组长度不满足要求！！！");
             }
             // 定义一个数组
             int[] arrTest = new int[length];
             // 利用生成的随机数给数组赋值
             Random random = new Random();
             for (int i = 0; i < arrTest.length - 1; i++) {
                 // 如果不传递参数，随机数的范围是int范围
                 int num = random.nextInt();
                 arrTest[i] = num;
             }
             // 记录排序之前开始时间，单位为毫秒ms
             long startTime = System.currentTimeMillis();
             // 排序
             quickSort1Recursion(arrTest);
             // 记录排序之后结束时间，单位为毫秒ms
             long endTime = System.currentTimeMillis();
             System.out.println("数组长度为" + length + "时，排序耗时：" + (endTime - startTime) + "ms");
         }
     }

### 4.2 二路快速排序 ###

#### 4.2.1 算法思想 ####

二路快排在分区的时候将相等元素分到左右两个子区间：

![在这里插入图片描述][92845f82dd804197b81df3a12422ca78.png_pic_center]

#### 4.2.2 Java代码实现--- hoare版本(左右指针法) ####

**参考视频：**[java快速排序讲解\_哔哩哔哩\_bilibili][java_bilibili]

package sort;
     
     import java.util.Arrays;
     import java.util.Random;
     
     /**
      * @ClassName QuickSort2
      * @Description TODO
      * @Author Jiangnan Cui
      * @Date 2022/10/22 11:47
      * @Version 1.0
      */
     public class QuickSort2 {
         public static void main(String[] args) {
             int[] arr = {4,2,6,3,5,9,8,7,0,1};
             System.out.println("原始数组为：" + Arrays.toString(arr));
             quickSort2Recursion(arr);
             System.out.println("二路快速递归排序后数组为：" + Arrays.toString(arr));
     
             System.out.println("测试二路快速排序数组性能：");
             testSort(10);
             testSort(100);
             testSort(1000);
             testSort(10000);
             testSort(100000);
             testSort(1000000);
             testSort(10000000);
             testSort(100000000);
         }
     
         /**
          * @MethodName quickSort2Recursion
          * @Description 二路快速排序
          * @param: arr
          * @Author Jiangnan Cui
          * @Date 10:38 2022/10/23
          */
         public static void quickSort2Recursion(int[] arr){
             quickSort2RecursionInternal(arr, 0, arr.length -1 );
         }
     
         /**
          * @MethodName quickSort2Recursion
          * @Description 在arr[left,...,right]上利用分治算法递归二快速排序
          * @param: arr 待排序数组
          * @param: left 左边界下标索引
          * @param: right 右边界下标索引
          * @return: int
          * @Author Jiangnan Cui
          * @Date 23:42 2022/10/20
          */
         private static void quickSort2RecursionInternal(int[] arr, int left, int right) {
             // 如果左边界索引>右边界索引时，说明区间不合法 或 只有一个元素时，直接结束
             if(left >= right){
                 return;
             }
             // 随机在当前数组中选一个数作为基准值，此处以选择最左侧元素作为基准值进行说明
             // 需要注意的是：若选择最左边的数据作为基准值(pivot)，则需要j先走；若选择最右边的数据作为基准值(pivot)，则需要i先走
             int base = arr[left];
             // 定义变量i，指向最左边，从左向右遍历
             int i = left;
             // 定义变量j，指向最右边，从右向左遍历
             int j = right;
             // 当i和j不相遇的时候，在循环中进行检索
             while(i != j){
                 // j从右向左检索比基准数小的，如果检索到比基准数小的就停下; 如果检索到比基准数大的，就继续向左检索
                 while(arr[j] >= base && i < j){
                     j--;// 继续向左检索
                 }
                 // i从左检索检索比基准数大的，如果检索到比基准数大的就停下; 如果检索到比基准数小的，就继续向右检索
                 while(arr[i] <= base && i < j){
                     i++;// 继续向右检索
                 }
                 // 如果i停下了，j也停下了，就交换这两个索引位置的元素
                 swap(arr,i,j);
             }
             // 如果上面的while循环的条件不成立(即i==j，i和j相遇了)，会跳出循环，执行下面语句：交换基准数和这个相遇位置的元素
             swap(arr,left,i);
             // 基准数就在这里归位了，基准数左边的数都比基准数小，基准数右边的数都比基准值大
             // 排基准数的左边，注意最后递归quickSort2RecursionInternal时要考虑i-1和j+1会不会越界
             if(left < i){
                 quickSort2RecursionInternal(arr, left, i - 1);
             }
             // 排基准数的右边
             if(j < right){
                 quickSort2RecursionInternal(arr, j + 1, right);
             }
         }
     
         /**
          * @MethodName swap
          * @Description 交换数组中的两个元素
          * @param: i
          * @param: j
          * @param: arr
          * @Author Jiangnan Cui
          * @Date 23:30 2022/10/20
          */
         private static void swap(int[] arr, int i, int j) {
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     
         /**
          * @MethodName testSort
          * @Description 测试排序方法性能
          * @param: length 测试数组的长度
          * @return: int[]
          * @Author Jiangnan Cui
          * @Date 16:04 2022/10/23
          */
         private static void testSort(int length){
             if(length <= 0){
                 throw new RuntimeException("数组长度不满足要求！！！");
             }
             // 定义一个数组
             int[] arrTest = new int[length];
             // 利用生成的随机数给数组赋值
             Random random = new Random();
             for (int i = 0; i < arrTest.length - 1; i++) {
                 // 如果不传递参数，随机数的范围是int范围
                 int num = random.nextInt();
                 arrTest[i] = num;
             }
             // 记录排序之前开始时间，单位为毫秒ms
             long startTime = System.currentTimeMillis();
             // 排序
             quickSort2Recursion(arrTest);
             // 记录排序之后结束时间，单位为毫秒ms
             long endTime = System.currentTimeMillis();
             System.out.println("数组长度为" + length + "时，排序耗时：" + (endTime - startTime) + "ms");
         }
     }

**输出结果：**

原始数组为：[4, 2, 6, 3, 5, 9, 8, 7, 0, 1]
     二路快速递归排序后数组为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
     测试二路快速排序数组性能：
     数组长度为10时，排序耗时：0ms
     数组长度为100时，排序耗时：0ms
     数组长度为1000时，排序耗时：0ms
     数组长度为10000时，排序耗时：1ms
     数组长度为100000时，排序耗时：9ms
     数组长度为1000000时，排序耗时：78ms
     数组长度为10000000时，排序耗时：922ms

#### 4.2.3 挖坑法 ####

**参见：**[六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序\_双鱼211的博客-CSDN博客\_六大算法][211_-CSDN]

#### 4.2.4 前后指针法 ####

**参见：**[六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序\_双鱼211的博客-CSDN博客\_六大算法][211_-CSDN]

### 4.3 三路快速排序 ###

#### 4.3.1 算法思想 ####

将所有重复的元素都放在最终位置，只需要在小于V和大于V的子区间进行快排，所有相等的元素不再处理。

#### 4.3.2 实现逻辑 ####

![在这里插入图片描述][45ac5d351bb84132ad9ab5921129fffd.png_pic_center]

其中：

*  arr\[l\] 表示基准值v
 *  arr\[l+1,It\] 区间为小于V的元素集合，其中，It为最后橙色小于V的区间中最后一个小于V 的元素
 *  arr\[It+1,i) 蓝色区间为等于基准值的区间
 *  arr\[i\] 为当前遍历到的元素
 *  arr\[gt,r\] 紫色区间为大于V的集合，其中，gt 为紫色区间大于V的元素集合中第一个大于V 的元素

**当扫描的元素arr\[i\] < v 时，交换arr\[i\]和第一个等于V的元素It+1**：即将小于基准值的元素放在橙色区间的末尾

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]

**当扫描的元素arr\[i\] = v 时，不用处理，继续向前走**：等于基准值的元素位置不变

![在这里插入图片描述][ce6f90bead3d47c7a481526853d3c921.png_pic_center]

**当扫描的元素arr\[i\] > v 时，交换当前遍历的元素arr\[i\]和紫色区间第一个> v的元素，但是此时不用继续向前走，因为交换过来的元素也是未处理的元素**：

![在这里插入图片描述][888e413cd686481b971af690c9800296.png_pic_center]

**整个集合处理完，交换j和l:**

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]

#### 4.3.3 Java代码实现 ####

package sort;
     
     import java.util.Arrays;
     import java.util.Random;
     
     /**
      * @ClassName QuickSort2
      * @Description 三路快速排序
      * @Author Jiangnan Cui
      * @Date 2022/10/22 11:47
      * @Version 1.0
      */
     public class QuickSort3 {
         public static void main(String[] args) {
             int[] arr = {4,2,6,3,5,9,8,7,0,1};
             System.out.println("原始数组为：" + Arrays.toString(arr));
             quickSort3Recursion(arr);
             System.out.println("三路快速递归排序后数组为：" + Arrays.toString(arr));
     
             System.out.println("测试三路快速排序数组性能：");
             testSort(10);
             testSort(100);
             testSort(1000);
             testSort(10000);
             testSort(100000);
             testSort(1000000);
             testSort(10000000);
             testSort(100000000);
         }
     
         /**
          * @MethodName quickSort3Recursion
          * @Description 三路快速排序
          * @Author Jiangnan Cui
          * @Date 10:40 2022/10/23
          */
         public static void quickSort3Recursion(int[] arr){
             quickSort3RecursionInternal(arr, 0, arr.length - 1);
         }
     
         /**
          * @MethodName quickSort3RecursionInternal
          * @Description 在arr[left,..,right]上利用分治算法递归三路快速排序
          * @param: arr
          * @param: left 左边界下标索引
          * @param: right 左边界下标索引
          * @return:
          * @Author Jiangnan Cui
          * @Date 10:12 2022/10/23
          */
         private static void quickSort3RecursionInternal(int[] arr, int left, int right) {
             // 如果左边界索引>右边界索引时，说明区间不合法 或 只有一个元素时，直接结束
             if(left >= right){
                 return;
             }
             // 随机在当前数组中选一个数作为基准值，此处以选择最左侧元素作为基准值进行说明
             int base = arr[left];
             // lt指向最后一个<v的元素
             int lt = left;
             // i(lt+1)指向第一个=v的元素
             int i = lt + 1;
             // gt(right+1)指向第一个>v的元素
             int gt = right + 1;
             // i从左向后遍历，直至和gt重合时，表明所有元素都处理完毕
             while(i < gt){
                 if(arr[i] < base){// 比基准值小时
                     // 将遍历元素与=v的第一个元素交换
                     swap(arr,i,lt + 1);
                     // 继续向右遍历
                     i++;
                     // lt右移
                     lt++;
                 }else if(arr[i] > base){// 比基准值大时
                     // 将遍历元素与=v的最后一个元素交换
                     swap(arr,i,gt - 1);
                     // gt左移，此处i进行+1操作，因为交换过来的gt-1还未处理
                     gt--;
                 }
             }
             // 遍历完成后，最后一次将基准值和最后一个小于v的元素作交换，基准值就落在了最终的位置
             swap(arr,left,lt);
             // 对左右区间重复进行快速排序
             quickSort3RecursionInternal(arr,left,lt - 1);
             quickSort3RecursionInternal(arr,gt,right);
         }
     
         /**
          * @MethodName swap
          * @Description 交换数组中的两个元素
          * @param: i
          * @param: j
          * @param: arr
          * @Author Jiangnan Cui
          * @Date 23:30 2022/10/20
          */
         private static void swap(int[] arr, int i, int j) {
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     
         /**
          * @MethodName testSort
          * @Description 测试排序方法性能
          * @param: length 测试数组的长度
          * @return: int[]
          * @Author Jiangnan Cui
          * @Date 16:04 2022/10/23
          */
         private static void testSort(int length){
             if(length <= 0){
                 throw new RuntimeException("数组长度不满足要求！！！");
             }
             // 定义一个数组
             int[] arrTest = new int[length];
             // 利用生成的随机数给数组赋值
             Random random = new Random();
             for (int i = 0; i < arrTest.length - 1; i++) {
                 // 如果不传递参数，随机数的范围是int范围
                 int num = random.nextInt();
                 arrTest[i] = num;
             }
             // 记录排序之前开始时间，单位为毫秒ms
             long startTime = System.currentTimeMillis();
             // 排序
             quickSort3Recursion(arrTest);
             // 记录排序之后结束时间，单位为毫秒ms
             long endTime = System.currentTimeMillis();
             System.out.println("数组长度为" + length + "时，排序耗时：" + (endTime - startTime) + "ms");
         }
     }

### 4.4 复杂度分析 ###

快速排序的过程类似于二叉树其高度为logN，每层约有N个数，如下图所示：

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

除了使用递归的方法之外，还有使用**非递归**的方法，是通过**栈**实现的。

*  时间复杂度：O(nlogn)
 *  空间复杂度：O(logn)
 *  稳定性：不稳定

其它排序算法待完善。。。。。。

[.........._HH_LL_-CSDN]: https://blog.csdn.net/weixin_50901244/article/details/120119619
[mu_mu_-CSDN]: https://blog.csdn.net/qq_51419787/article/details/123786370
[Baret-H_-CSDN]: https://blog.csdn.net/qq_45173404/article/details/116090861
[211_-CSDN]: https://blog.csdn.net/weixin_50886514/article/details/119045154
[java_c_cpp_Top_Spirit_-CSDN]: https://blog.csdn.net/weixin_41190227/article/details/86600821
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/e786e0711e1a44dcb19705c8c90c6cca.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[img]: https://img-blog.csdnimg.cn/2bb18f2c7b9c4cf8a334441ebf9bad22.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAbXUnbXU=,size_20,color_FFFFFF,t_70,g_se,x_16
[image]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMzMwNDMxNjgtMTg2NzgxNzg2OS5wbmc?x-oss-process=image/format,png
[img 1]: https://img-blog.csdnimg.cn/img_convert/64a433df4682ef91c63729e198cc1c7e.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/686d5cb91ae9404aaa25d48534c98b38.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: https://img-blog.csdnimg.cn/13391f84c2794970965919e5b68e1a38.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: https://img-blog.csdnimg.cn/ae5e4c67fc3046fd8af2f2cc85a8b63c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: https://img-blog.csdnimg.cn/8790327f1b4f4a7f84b1ee5db6f80e50.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]: https://img-blog.csdnimg.cn/2e1a6d1cb7944512b94fe5a4914e65c6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[92845f82dd804197b81df3a12422ca78.png_pic_center]: https://img-blog.csdnimg.cn/92845f82dd804197b81df3a12422ca78.png#pic_center
[java_bilibili]: https://www.bilibili.com/video/BV1it41167v2
[45ac5d351bb84132ad9ab5921129fffd.png_pic_center]: https://img-blog.csdnimg.cn/45ac5d351bb84132ad9ab5921129fffd.png#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]: https://img-blog.csdnimg.cn/a112c97a2bde4300b5ab57d3e9f7204b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[ce6f90bead3d47c7a481526853d3c921.png_pic_center]: https://img-blog.csdnimg.cn/ce6f90bead3d47c7a481526853d3c921.png#pic_center
[888e413cd686481b971af690c9800296.png_pic_center]: https://img-blog.csdnimg.cn/888e413cd686481b971af690c9800296.png#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASEh-TEw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]: https://img-blog.csdnimg.cn/194e9a148d5644b484c6d6ae04c04fb2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASEh-TEw=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDg4NjUxNA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/5e1f258993a94acb8115a5e6b9f80d90.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDg4NjUxNA==,size_16,color_FFFFFF,t_70