1.基本介绍
同冒泡排序一样，快速排序（Quicksort）也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。但快速排序是对冒泡排序的一种改进。
2.基本思想
关于基本思想，我们在这里先不考虑是如何具体实现的，先明白最终能达到什么样的效果。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端。
而快速排序则是 在每一轮排序前先挑选出一个基准元素 pivot，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边。
📝 例如，我们规定 基准元素为待排序数组的第一个元素，使用快速排序后的数组结果为：
然后再按此方法对 左子数组 和 右子数组 分别进行快速排序， 整个排序过程可以递归进行，直到最终的子数组都只有一个元素就不需要对该子数组进行排序，递归停止，实际就是通过分而治之的思想减少排序中交换和遍历的次数，以此达到整个数据变成有序序列。
📚 分而治之：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解。
3.元素交换完成排序
明白了基本思想，选定了基准值 pivot，我们主要的问题就是 每轮排序中如何实现基准值的左边都是小于或等于基准值的元素，基准值的右边是大于或等于基准值的元素。
3.1 双边循环法
3.1.1 步骤一：如何完成一轮排序
3.1.1.1 思路分析
- 初始化
- 分别在数组的头尾设置两个指针
左指针 left和右指针 right，其中 left 和 right 的值是数组索引。 - 将头部元素作为
基准值 pivot，其中 pivot 的值是 数组索引。
- 先判断右指针和基准值，如果右指针指向的元素值 大于等于基准位置元素值 或者 不与左指针重合 就向前移动，否则停止移动。
- 再判断左指针和基准值，如果左指针指向的元素值 小于等于基准位置元素值 或者 不与右指针重合 就向后移动，否则停止移动。
- 判断是否左右指针是否重合
- 如果 未重合，交换左指针索引位置的元素值和右指针索引位置的元素值。交换完毕，再回到第二步依次往下执行（重复第2,3,4步的操作）。
📍 左指针找到的是比基准位置元素值大的数，右指针找到的是比基准位置元素值小的数。
将左右指针的索引位置元素值进行交换，就是把大的数放到数组右边，把小的数放到数组左边。那么最终的效果是：
- 数组的左边都是小于或等于基准位置元素值的数
- 数组的右边都是大于或等于基准位置元素值的数
- 如果 重合了，将重合指针索引位置的元素值与基准数位置的值进行交换。此轮排序结束。
❓ 重合了为什么将重合指针索引位置的元素值与基准数位置的值进行交换？
我们先考虑一下 left 和 right 指针重合的两种情况：
1️⃣ right 指针的移动导致两指针重合：
经过上一轮循环后，此时 left 指针所指的元素一定是小于或等于 基准元素值的（即使此时是第一轮循环，left也是指向头部元素，肯定满足小于等于基准元素值），因此我们将 头部元素值 与 left指针指向的值交换依旧可以满足 左子树组是全小于等于 基准元素值的，右子数组是全大于等于基准元素值的，并且两个子数组的分隔索引就是left和right重合的索引位置。
2️⃣ left 指针的移动导致两指针重合：
left指针移动，说明此时在执行思路分析的第三步，因为我们在思路分析的时候是先判断右指针和基准元素值的大小即第二步，所以此时右指针指向的值一定是小于等于基准元素值的。因此left移动后与right指针重合，我们将 头部元素值 与 left指针指向的值交换依旧可以满足 左子树组是全小于等于 基准元素值的，右子数组是全大于等于基准元素值的，并且两个子数组的分隔索引就是left和right重合的索引位置。
💬 我们可以得出一个结论：两指针重合时，一定满足重合位置的元素值一定小于或等于基准元素值。
因此重合后将 left指向的元素 和 头部元素（基准索引值）进行交换：
- 不仅让左子数组依旧全部是 小于等于 基准索引值的 元素
- 而且将 重合后的left和right指向的位置成为了左子数组 和 右子数组 的分隔位置，解决了我们在第三节刚开始时提出的问题 - 每轮排序中如何实现基准值的左边都是小于或等于基准值的元素，基准值的右边是大于或等于基准值的元素。
这个就很巧妙了，我们也就完成了这一轮的排序。
3.1.1.2 图解过程
3.1.1.3 代码实现
package sort; /** * @author 狐狸半面添 * @create 2022-11-29 2:32 */ public class QuickSort { public static void main(String[] args) { int[] arr = {4, 7, 6, 5, 3, 2, 8, 1}; //对 arr 数组进行排序，指定了要对索引在 [0,arr.length-1] 内的元素进行一轮排序 quickSort(arr, 0, arr.length - 1); //输出结果：3 1 2 4 5 6 8 7 for (int i : arr) { System.out.print(i + "\t"); } } /** * 功能：对 数组索引在 [first, last] 范围内的元素进行一轮排序 * * @param arr 待排序的数组 * @param first 待排序数组的第一个元素的索引值，我们规定该索引的元素值也是基准值 * @param last 待排序数组的最后一个元素的索引值 */ public static void quickSort(int[] arr, int first, int last) { //定义一个中间变量 int temp; //定义左指针，初始值为待排序数组的头部 int left = first; //定义右指针，初始值为待排序数组的尾部 int right = last; while (true) { //先判断右指针和基准值，如果右指针指向的元素值 大于等于基准元素值 或者 不与左指针重合 就向前移动，否则停止移动。 while (arr[right] >= arr[first] && left < right) { right--; } //再判断左指针和基准值，如果左指针指向的元素值 小于等于基准元素值 或者 不与右指针重合 就向后移动，否则停止移动。 while (arr[left] <= arr[first] && left < right) { left++; } //判断是否重合 if (left < right) { //1.如果没有重合，就交换左右指针的值，继续下一次循环移动指针 temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } else { //2.如果重合，则将重合指针索引位置的元素值与基准数位置的值进行交换，本轮排序结束 temp = arr[left]; arr[left] = arr[first]; arr[first] = temp; break; } } } }
3.1.2 步骤二：递归完成对子数组的排序
3.1.2.1 思路分析
递归：一个含直接或间接调用本函数语句的函数称之为递归函数，它必须满足以下两个条件：
- 在每一次调用自己时，必须是（在某种意义上）更接近于解
- 必须有一个终止处理或计算的准则
📝 我们以具体示例分析一下，调用步骤一的方法对数组可以完成第一轮排序：
此时的 left 和 right 指针肯定都是指向 基准元素值为“4” 的索引位置的，那么接下来我们需要对基准索引位置的 左子数组 [3,1,2]与 右子数组 [5,6,8,7]分别采取同第一轮排序时相同的策略（方法）分别进行排序：
- 左子数组：基准索引元素值为 3 ，left 指向的元素值时 3 ，right 指向的元素值时 2
- 左子数组：基准索引元素值为 5 ，left 指向的元素值时 5 ，right 指向的元素值时 7
当最后的左子数组和右子数组没有元素或者只有一个元素时就不需要对该左子数组或右子数组进行排序了，这也就是递归终止的条件。
3.1.2.2 图解过程
3.1.2.3 代码实现
实现递归对子数组进行排序，我们只需要对 quickSort(int[] arr, int first, int last) 的代码进行改进即可。
package sort; /** * @author 狐狸半面添 * @create 2022-11-29 2:32 */ public class QuickSort { public static void main(String[] args) { int[] arr = {4, 7, 6, 5, 3, 2, 8, 1}; //对 arr 数组进行排序，指定了要对索引在 [0,arr.length-1] 内的元素进行一轮排序 quickSort(arr, 0, arr.length - 1); //输出：1 2 3 4 5 6 7 8 for (int i : arr) { System.out.print(i + "\t"); } } /** * 功能：对 数组索引在 [first, last] 范围内的元素进行一轮排序 * * @param arr 待排序的数组 * @param first 待排序数组的第一个元素的索引值，我们规定该索引的元素值也是基准值 * @param last 待排序数组的最后一个元素的索引值 */ public static void quickSort(int[] arr, int first, int last) { /* quickSort方法是对 索引在[first, last]范围内的元素进行排序， - 1.如果 first == last 说明此时只有一个元素了，很明显，一个元素是没有排序的必要的，因此直接退出 quickSort 方法即可，递归终止 - 2.如果 first > last 说明此时是没有元素的，那也不需要排序，递归终止 */ if(first >= last){ return; } //定义一个中间变量 int temp; //定义左指针，初始值为待排序数组的头部 int left = first; //定义右指针，初始值为待排序数组的尾部 int right = last; while (true) { //先判断右指针和基准值，如果右指针指向的元素值 大于等于基准元素值 或者 不与左指针重合 就向前移动，否则停止移动。 while (arr[right] >= arr[first] && left < right) { right--; } //再判断左指针和基准值，如果左指针指向的元素值 小于等于基准元素值 或者 不与右指针重合 就向后移动，否则停止移动。 while (arr[left] <= arr[first] && left < right) { left++; } //判断是否重合 if (left < right) { //1.如果没有重合，就交换左右指针的值，继续下一次循环移动指针 temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } else { //2.如果重合，则将重合指针索引位置的元素值与基准数位置的值进行交换，本轮排序结束 temp = arr[left]; arr[left] = arr[first]; arr[first] = temp; break; } } /* 退出了while循环，说明 left 指针 和 right 指针 已经重合。 对 [first, last]范围内的元素完成一轮排序后， 此时 左子数组即索引在 [first, left - 1] 的元素都是小于等于当前基准元素值的 右子数组即索引在 [left + 1, last] 的元素都是大于等于当前基准元素值的 那么我们只需要分别再对左子数组和右子数组分别进行排序即可 */ quickSort(arr,first,left-1); quickSort(arr,left+1,last); } }
