• 面试官：同学，冒泡太简单了，要不手写一个【快速排序】吧...

    概要

            快速排序由C. A. R. Hoare在1960年提出，是八大排序算法中最常用的经典排序算法之一。其广泛应用的主要原因是高效，核心算法思想是分而治之。

            快速排序经常会被作为面试题进行考察，通常的考察思路是快排思想、编码实践之手写快排以及进一步对快排的优化。

    相关文章：
    常见十大排序算法，动图演示（Python3实现）_Java Punk的博客-CSDN博客回顾所学发现见到最多的还是各种排序算法https://blog.csdn.net/weixin_44259720/article/details/103385439更多相关文章，请登录我的博客主页进行查看。

    正文

            事实上，Java 标准库中 Arrays. sort() 方法的源码也正是使用了优化后的快速排序，这也是面试的一个考点，下面会带大家分析源码。可见，掌握快排算法对于数据结构与算法入门极为重要。

    一、原理

            快速排序（Quick Sort）是从冒泡排序算法演变而来的，实际上是在冒泡排序基础上的递归和分治法，核心思想是分治，即：每一轮选择数组中某个数作为基数，通过一趟排序将要排序的数据分割成独立的两部分，其中比基数小的放一边，比基数大的放在另一边，循环递归，最终使整个数组变成有序。

            快速排序核心是选定一个基数进行划分排序，关于基数选择有很多方式，而基数选择直接关系到快排的效率。事实上，选取基准元素应该遵循平衡子问题的原则，即：使得划分后的两个子序列的长度尽量相同。

            本篇以最常见的使用数组首元素（P）作为基数进行快速排序原理说明。

    二、方法描述

            先安排一个测试类，然后再展开来讲解排序方法：

    iOS版快速排序（也含冒泡）
    zip 0星 超过10%的资源 62KB
    下载
    1.     @Test
    2.     void all_process_T(){
    3.         int[] arr1 = {1,2,3,5,8,11,10,6,9,7,54,23,27,17,22,13};
    4.         int[] arr2 = {1,2,3,5,8,11,10,6,9,7,54,23,27,17,22,13};
    5.  
    6.         this.quickSort_1(arr1, 0, arr1.length - 1);
    7.         System.out.println("arr1 = " + JSON.toJSONString(arr1));
    8.         this.quicksort_2(arr2, 0, arr2.length - 1);
    9.         System.out.println("arr2 = " + JSON.toJSONString(arr2));
    10.     }

    • 写法一：分开的写法，原理更好理解；

    1.     public void quickSort_1(int[] arr,int left,int right){
    2.         if (left >= right)
    3.             return;
    4.         int mid = this.partition(arr, left, right);
    5.         this.quickSort_1(arr, left, mid-1);
    6.         this.quickSort_1(arr, mid+1, right);
    7.     }
    8.  
    9.     private int partition(int[] arr, int left, int right) {
    10.         // 划分参考数索引，默认为第一个数，可优化
    11.         int base = arr[left];
    12.         // 以左边为key，所以从右边开始找
    13.         while (left < right) {
    14.             // 右边找
    15.             while (left < right && arr[right] >= base ) {
    16.                 right--;
    17.             }
    18.             // 找到以后，与左边元素交换
    19.             if (left < right) {
    20.                 arr[left++] = arr[right];
    21.             }
    22.             // 左边找
    23.             while (left < right && arr[left] <= base ) {
    24.                 left++;
    25.             }
    26.             // 找到以后，与右边元素交换
    27.             if (left < right) {
    28.                 arr[right--] = arr[left];
    29.             }
    30.         }
    31.         // 最后，将参考数字赋值给left，完成最终交换
    32.         arr[left] = base;
    33.         return left;
    34.     }

    • 写法二：合并在一起的写法；

    1.     public static void quicksort_2(int[] arr, int left, int right) {
    2.         //数组最左边小于最右边不合法,直接退出
    3.         if (left > right) {
    4.             return;
    5.         }
    6.         //定义变量i指向最左边
    7.         int i = left;
    8.         //定义变量j指向最右边
    9.         int j = right;
    10.         //定义左边为基准元素base
    11.         int base = arr[left];
    12.         //只要i和j没有指向同一个元素,就继续交换
    13.         while (i != j) {
    14.             //从右向左寻找第一个小于基准元素的数
    15.             while (arr[j] >= base && i < j) {
    16.                 j--;
    17.             }
    18.             //从左向右寻找第一个大于基准元素的数
    19.             while (arr[i] <= base && i < j) {
    20.                 i++;
    21.             }
    22.             //执行到这里证明找到了i和j指向的元素
    23.             //交换i和j指向的元素
    24.             int temp = arr[i];
    25.             arr[i] = arr[j];
    26.             arr[j] = temp;
    27.         }
    28.         //将i和j共同指向的元素与基准元素交换
    29.         arr[left] = arr[i];
    30.         arr[i] = base;
    31.         //对左边进行快速排序
    32.         quicksort_2(arr, left, i - 1);
    33.         //对右边进行快速排序
    34.         quicksort_2(arr, i + 1, right);
    35.     }

    三、Arrays.sort源码解析

             Arrays 其实调用了 DualPivotQuicksort. sort() 方法进行排序：

    1. public static void sort(int[] a) {
    2.     DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    3. }

            DualPivotQuicksort.sort() 方法在预处理部分，主要做了三件事：

    1. 判断数组长度是否超过快排阈值：如果超过286，则进行进一步判断，否则直接调用快速排序的方法。而进入快速排序的方法中也会有长度判断，如果数组长度小于47，会使用插入排序（下面代码展示有说明）；
    2. 创建运行记录空间（run）：主要用于记录数组的形状，是否大体呈有序状态。如果峰值过多，说明数组趋于乱序状态，依然使用快速排序方法；
    3. 如若最后一轮迭代仅剩一个数自成一个子序列，那么则在 run 中添加一个哨兵，值为 right + 1；如若数组已然有序，则直接返回。

            因为涉及 sort() 排序代码比较多，所以我只节选了一部分进行展示，感兴趣的小伙伴可自行源码。

    1. final class DualPivotQuicksort {
    2.  
    3.     // 合并排序中的最大运行长度。
    4.     private static final int MAX_RUN_LENGTH = 33;
    5.  
    6.     // 合并排序中的最大运行次数。
    7.     private static final int MAX_RUN_COUNT = 67;
    8.  
    9.     // 如果要排序的数组长度小于该常数，则插入排序优先于快速排序。
    10.     private static final int INSERTION_SORT_THRESHOLD = 47;
    11.  
    12.     // 如果要排序的数组长度小于此常数，则优先使用快速排序合并排序。
    13.     private static final int QUICKSORT_THRESHOLD = 286;
    14.  
    15.     /**
    16.      * 如果可能合并，使用给定的工作区数组切片对数组的指定范围排序。
    17.      */
    18.     static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
    19.         // 在小数组上使用快速排序, 常量 QUICKSORT_THRESHOLD = 286
    20.         if (right - left < QUICKSORT_THRESHOLD) {
    21.             sort(a, left, right, true);
    22.             return;
    23.         }
    24.  
    25.         // run[i] 表示第i轮外循环迭代的起始位置
    26.         int[] run = new int[MAX_RUN_COUNT + 1];
    27.         int count = 0; run[0] = left; // count 表示轮数-1, run[0] 初始值为 left 
    28.  
    29.         // 检查这个数组是否大体呈有序态
    30.         for (int k = left; k < right; run[count] = k) {
    31.             // 升序
    32.             if (a[k] < a[k + 1]) { 
    33.                 while (++k <= right && a[k - 1] <= a[k]);
    34.             } 
    35.             // 降序
    36.             else if (a[k] > a[k + 1]) {
    37.                 while (++k <= right && a[k - 1] >= a[k]);
    38.                 // 如果是降序，那么对降序序列进行交换，转换为升序序列
    39.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
    40.                     int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
    41.                 }
    42.             } 
    43.             // 相等
    44.             else { 
    45.             	// 统计相等元素【a[k]】的频数，如果超过MAX_RUN_LENGTH（默认33）则使用快速排序
    46.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
    47.                     if (--m == 0) {
    48.                         sort(a, left, right, true);
    49.                         return;
    50.                     }
    51.                 }
    52.             }
    53.  
    54.             // 如果数组的结构化指标（即凹凸点个数）超过了阈值，其实就是乱序，那么还是选择快速排序
    55.             if (++count == MAX_RUN_COUNT) {
    56.                 sort(a, left, right, true);
    57.                 return;
    58.             }
    59.         }
    60.  
    61.         // 检查特殊情况
    62.         if (run[count] == right++) {
    63.         	// 数组长度为1时，设置一个哨兵
    64.             run[++count] = right;
    65.         } 
    66.         // 数组已呈有序状态
    67.         else if (count == 1) { 
    68.             return;
    69.         }
    70.  
    71.         // 太长了，不写了，自己看源码吧 ...
    72.     }
    73.  
    74.     /**
    75.      * 通过双枢轴快速排序对数组的指定范围排序。
    76.      */
    77.     private static void sort(int[] a, int left, int right, boolean leftmost) {
    78.         int length = right - left + 1;
    79.         // 在微小数组上使用插入排序, 常量 INSERTION_SORT_THRESHOLD = 47
    80.         if (length < INSERTION_SORT_THRESHOLD) {
    81.             // ...
    82.         }
    83.         // 否则，使用快速排序，代码太多不展示了，直接看源码吧 ...
    84.     }
    85.  
    86. }

  • 相关阅读:
    Ubuntu 常用命令
    Shell-01Shell初相识
    Unity 3D模型展示框架篇之ILRuntime整合与应用
    码蹄集部分题目（2024OJ赛13期；贪心集训+递归集训）
    EMQX Newsletter 2022-08｜企业版 5.0 开发进行中、EMQX Kubernetes Operator 2.0 即将发布
    python-运算符
    Python 中堪称神仙的6个内置函数
    最大int
    【Java SE】对象的构造及初始化
    宁德时代最好的电池，给他了
  • 原文地址：https://blog.csdn.net/weixin_44259720/article/details/123355134