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

参考链接：

• 十大经典排序算法(冒泡、选择、插入、希尔、快排..........)_HH~LL的博客-CSDN博客_十大排序算法

• 排序算法详细讲解（超酷）_mu'mu的博客-CSDN博客_排序算法

• 数据结构——八大排序算法（面试必备）_Baret-H的博客-CSDN博客_八大排序算法

• 六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序_双鱼211的博客-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)。非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置，所以对数据规模和数据分布有一定的要求。

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

其他分类待完善

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

图片名词解释：

• n: 数据规模

• k: “桶”的个数

• In-place: 占用常数内存，不占用额外内存

• Out-place: 占用额外内存

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

3.1 算法思想

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

3.2 实现逻辑

主要通过两层循环实现

• 外层循环代表需要比较几轮/趟，即每次将最大的一个数放到最后所需要的次数。

• 内层循环代表两两需要对比多少次，比如n个数据第1次两两比较需要n-1次，第2次两两比较需要n-2次，以此类推。

举例：

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，代表没有数据。

过程演示：

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

2. 将遍历的元素与基准值进行比较，有两种情况：

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

• case2: 如果arr[i]

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

此时交换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 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 算法思想

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

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

参考视频：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博客_六大算法

4.2.4 前后指针法

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

4.3 三路快速排序

4.3.1 算法思想

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

4.3.2 实现逻辑

其中：

• 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：即将小于基准值的元素放在橙色区间的末尾

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

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

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

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 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个数，如下图所示：

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

• 时间复杂度：O(nlogn)

• 空间复杂度：O(logn)

• 稳定性：不稳定

​​​​​​​

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