同冒泡排序一样，快速排序（Quicksort）也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。但快速排序是对冒泡排序的一种改进。
2.基本思想关于基本思想，我们在这里先不考虑是如何具体实现的，先明白最终能达到什么样的效果。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端。
基准元素 pivot📝 例如，我们规定 基准元素为待排序数组的第一个元素，使用快速排序后的数组结果为：
左子数组右子数组📚 分而治之：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解。
基准值 pivot3.1 双边循环法
3.1.1 步骤一：如何完成一轮排序
3.1.1.1 思路分析
左指针 left右指针 right基准值 pivot3.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 思路分析
递归：一个含直接或间接调用本函数语句的函数称之为递归函数，它必须满足以下两个条件：
- 在每一次调用自己时，必须是（在某种意义上）更接近于解
- 必须有一个终止处理或计算的准则
📝 我们以具体示例分析一下，调用步骤一的方法对数组可以完成第一轮排序：
左子数组 [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);
}
}
3.2 单边循环法
双边循环法从数组的两边交替遍历原数组，虽然更加直观，但是代码实现相对繁琐。而单边循环法则简单得多，只从数组的一边对元素进行遍历和交换。
当然，两种方法的目的是相同的，即：每轮排序后 基准值的左边都是小于或等于基准值的元素，基准值的右边是大于或等于基准值的元素。
3.2.1 思路分析
3.2.1.1 对于每轮排序的操作
基准值 pivotmark指针travel指针3.2.1.2 递归完成对子数组的排序
我们需要明白，双边循环法和单边循环法不同的只是每一轮排序的方式，但最终的效果都会是一样的，即每轮排序后 基准值的左边都是小于或等于基准值的元素，基准值的右边是大于或等于基准值的元素。
因此，我们在之前双边循环法里的步骤二的代码实现并不需要改变，只需要改变双边循环法的步骤一的代码实现即可！！！
3.2.2 图解每轮排序操作
对于每轮排序的操作，如果只是文字描述你可能比较难理解，我们对第一次排序的过程进行图解分析，你再结合上面的思路分析，来看看是怎样一个原理与过程：
💬 特别注意观察 索引从头部位置的下一个位置到mark位置 的元素值与基准元素值的大小关系
3.2.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);
//输出：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;
//定义mark指针，初始值为待排序数组的头部
int mark = first;
//定义travel指针，初始值为待排序数组的头部位置 + 1，作用是对数组进行遍历
int travel = first + 1;
// 遍历当前数组
while (true) {
//travel指针向后移动，找到第一个小于基准元素值的元素 或 指针超出数组最大索引，就停止移动
while (travel <= last && arr[travel] >= arr[first]) {
travel++;
}
/*
判断 travel 是否超出当前数组最大索引
- 如果未超出：mark指针向后移动一位，travel 和 mark 指针指向的值进行交换，travel向后移动，再回到第二步继续循环操作
- 如果超出：将 mark 指针指向的值 与 头部元素值（基准元素值）进行交换，本次排序完成。
*/
if(travel <= last){
//未超出
mark++;
temp = arr[travel];
arr[travel] = arr[mark];
arr[mark] = temp;
//发生交换后,travel需要向后移动一位
//这个必须写，是针对于 mark == travel的情况下，arr[travel]<arr[first]
//否则下一次 travel <= last && arr[travel] >= arr[first] 仍然为false导致mark超过了travel
//最终会导致栈溢出，因此必须写 travel++
travel++;
}else{
//超出了
temp = arr[mark];
arr[mark] = arr[first];
arr[first] = temp;
break;
}
}
/*
退出了while循环，说明本轮排序已完成
对 [first, last]范围内的元素完成一轮排序后，
此时 左子数组即索引在 [first, mark - 1] 的元素都是小于当前基准元素值的（注意与双边循环法不同，不存在等于基准元素值的，等于的都在右子数组）
右子数组即索引在 [mark + 1, last] 的元素都是大于等于当前基准元素值的
那么我们只需要分别再对左子数组和右子数组分别进行排序即可
*/
quickSort(arr, first, mark - 1);
quickSort(arr, mark + 1, last);
}
}
3.2.4 另一种代码实现
根本的思路与第一种是一样的，但是会更为清晰，如果你明白了上面的，那下面的也不会很难理解：
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;
//定义mark指针，初始值为待排序数组的头部
int mark = first;
//定义travel指针，初始值为待排序数组的头部位置 + 1，作用是对数组进行遍历
int travel = first + 1;
// 遍历当前数组
for(;travel<=last;travel++){
if(arr[travel]<arr[first]){
//找到了比基准元素值小的数，就交换
mark++;
temp = arr[travel];
arr[travel] = arr[mark];
arr[mark] = temp;
}
}
//遍历完毕，将 mark指向的值 与 头部元素值（基准元素值）进行交换
temp = arr[mark];
arr[mark] = arr[first];
arr[first] = temp;
/*
对 [first, last]范围内的元素完成一轮排序后，
此时 左子数组即索引在 [first, mark - 1] 的元素都是小于当前基准元素值的（注意与双边循环法不同，不存在等于基准元素值的，等于的都在右子数组）
右子数组即索引在 [mark + 1, last] 的元素都是大于等于当前基准元素值的
那么我们只需要分别再对左子数组和右子数组分别进行排序即可
*/
quickSort(arr, first, mark - 1);
quickSort(arr, mark + 1, last);
}
}
我们已经给出了三种递归方式的代码实现，由于递归的代码操作都是一样的，因此在这里我们就只将双边循环法的代码改造为非递归的方式，其他两种也是同理操作即可。
4.1 说明
绝大多数的递归逻辑，都可以使用栈的方式来代替。
代码中一层一层的方法调用，本身就是用来一个方法调用栈。每次进入一个新方法，就相当于入栈；每次有方法返回，就相当于出栈。所以，可以把原来的递归实现转化成一个栈的实现，在栈中存储每一次方法调用的参数。
4.2 代码实现
package sort;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* @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] 内的元素进行一轮排序
quickSortByStack(arr, 0, arr.length - 1);
//输出：1 2 3 4 5 6 7 8
for (int i : arr) {
System.out.print(i + "\t");
}
}
public static void quickSortByStack(int[] arr, int first, int last) {
//用一个集合栈来代替递归的函数栈
Stack<Map<String, Integer>> quickSortStack = new Stack<>();
//整个数列的起止下标，以 哈希的形式入栈
Map<String, Integer> rootParam = new HashMap<>(2);
rootParam.put("firstIndex", first);
rootParam.put("lastIndex", last);
quickSortStack.push(rootParam);
//基准位置索引
int pivot;
//循环结束的条件为栈空
while (!quickSortStack.isEmpty()) {
Map<String, Integer> param = quickSortStack.pop();
int firstIndex = param.get("firstIndex");
int lastIndex = param.get("lastIndex");
pivot = quickSort(arr, firstIndex, lastIndex);
if (pivot != -1) {
//将左子数组和右子数组加入到栈中
Map<String, Integer> leftArrParam = new HashMap<>(2);
leftArrParam.put("firstIndex", firstIndex);
leftArrParam.put("lastIndex", pivot - 1);
quickSortStack.push(leftArrParam);
Map<String, Integer> rightArrParam = new HashMap<>(2);
rightArrParam.put("firstIndex", pivot + 1);
rightArrParam.put("lastIndex", lastIndex);
quickSortStack.push(rightArrParam);
}
}
}
/**
* 功能：对 数组索引在 [first, last] 范围内的元素进行一轮排序
*
* @param arr 待排序的数组
* @param first 待排序数组的第一个元素的索引值，我们规定该索引的元素值也是基准值
* @param last 待排序数组的最后一个元素的索引值
* @return 最终的基准位置索引
*/
public static int quickSort(int[] arr, int first, int last) {
/*
quickSort方法是对 索引在[first, last]范围内的元素进行排序，
- 1.如果 first == last 说明此时只有一个元素了，很明显，一个元素是没有排序的必要的，因此直接退出 quickSort 方法即可
- 2.如果 first > last 说明此时是没有元素的，那也不需要排序
*/
if (first >= last) {
return -1;
}
//定义一个中间变量
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;
}
}
return left;
}
}
在我们之前写的规则与代码中，都是将数组的第一个元素作为基准。这种选择在绝大多数情况下是没有问题的。但是，如果有一个原本是逆序的队列，期望使用快速排序形成顺序队列，会发生什么呢？
可以看到，整个数组并没有被很好的分成两半，基准元素的最终位置总是在最左边或者最右边，而不在中间，无法发挥分治法的优势。因此在这种极端情况下，快速排序需要进行 n 轮，时间复杂度退化为 O ( n 2 ) O(n^2) O(n2)
应该怎样避免呢？我们可以随机选择一个元素作为基准元素，并让该基准元素和数组首元素交换位置。这样首元素就成了基准元素。
这样一来，即使在数列完全逆序的情况下，也能有效地将数列分成两部分。
当然，即使是随机选择基准元素，也会有极小的可能宣导数列的最小值或最大值，同样会影响分治的效果。
6.快速排序的时间复杂度通过上述的分析，我们就可以知道快速排序的平均时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) ，但最坏情况下的时间复杂度是 O ( n 2 ) O(n^2) O(n2)