1、基本思想
快速排序是对冒泡排序的改进。通过一趟排序，将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个序列可以递归进行，以此达到整个数据变得有序序列。
2、图解
首先，随便从数组选一个值（比如选最中间的值），然后把比这个值小的元素放在这个值的左边，比这个值大的元素放在这个值的右边。
然后，把这个值的左右两边序列看成独立序列，分别再次进行上面操作。直到分成的独立序列只剩下一个元素位置。
3、代码实现
package cn.klb.datastructures.sort;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 实现数组的快速排序
* @Date: Create in 2023/4/4 19:42
* @Modified By:
*/
public class Quick {
public static void sort(int[] arr) {
int left = 0; // 初始left是最左边
int right = arr.length - 1; // 初始right是最右边
doSort(arr, left, right);
}
private static void doSort(int[] arr, int left, int right) {
int l = left;
int r = right;
// 这里定义一个中间值
// 注意：
// 这里所谓的中间值不一定就得是数组最中间的那个值
// 它可以是数组中任意的一个值，这里为了方便，才取了数组最中间的值
// 核心思想就是使得数组整体上小的在前面，大的在后面
int mediumValue = arr[(left + right) / 2];
int temp = 0;
// 把左边大于mediumValue的元素和右边小于mediumValue的元素进行交换
while (l < r) {
// 遍历左边元素，如果元素小于mediumValue，则索引往右走继续找
while (arr[l] < mediumValue) {
l++;
}
// 遍历右边元素，如果元素大于mediumValue，则索引继续往左走
while (mediumValue < arr[r]) {
r--;
}
// 检查一下l和r是不是超出边界了
if (l >= r) {
break;
}
// 如果没有退出当前while，则进行交换元素
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换完后，发现这个arr[l] == mediumValue 相等 r--， 左移
if (arr[l] == mediumValue) {
r--;
}
//如果交换完后，发现这个arr[r] == mediumValue 相等 l++， 右移
if (arr[r] == mediumValue) {
l++;
}
}
// 跳出最外层while后，要么 l > r,要么 l == r，不会出现 l < r 的情况
// 什么时候会出现 l < r呢
// 比如有个数组：{3，3，3，3，4，4，4}
// 我们取了最中间的3作为中间值
// l指针会跑到下标4的地方才跳出while
// r指针会跑到下标3的地方才跳出while
// 然后触发 l >= r 条件而跳出最外层的while循环。
if (r == l) {
r--;
l++;
}
// 左边递归
if (left < r) {
doSort(arr, left, r);
}
// 右边递归
if (right > l) {
doSort(arr, l, right);
}
}
}
4、时间复杂度
其实，在执行小的放前边，大的放后边之前，选取哪个值哪来当枢纽元（就是拿来比较的那个值）会影响算法的性能。最不好的就是每轮都选取第一个元素，因为当一个序列是预排序或者反序的，会导致所有的元素都划分在小值那边或者大值那边。比较安全的做法是随机选取，但会明显减慢快速排序的速度。一般做法是使用三数中值分割法，即先拿出最左边、最右边和最中间三个值，以这三个值的中值作为枢纽元，数学证明这样做能减少14%的比较次数。
假设比较次数为C，交换次数为S。
快速排序的时间复杂度受枢纽元选取策略影响，最差情况下的时间复杂度为O(n²)。
5、稳定性
通过原理可以判断：在左右两步进行交换的时候，是不会考虑左指针和右指针中间的重复值，因此快速排序是不稳定的。
6、测试
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.sort.*;
import org.junit.Test;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 排序测试
* @Date: Create in 2023/4/3 21:32
* @Modified By:
*/
public class SotrTest {
@Test
public void testQuick(){
int[] arr = new int[80000000];
for (int i = 0; i < 80000000; i++) {
arr[i] = (int) (Math.random() * 80000000);
}
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date date1 = new Date();
System.out.println("-----" + sdf.format(date1) + "-----");
System.out.println(Arrays.toString(arr));
Quick.sort(arr);
Date date2 = new Date();
System.out.println("-----" + sdf.format(date2) + "-----");
System.out.println(Arrays.toString(arr));
// 8000万的随机数据进行快速排序，我的电脑花了大约13秒(更质的飞跃)
}
}