快速排序
逻辑实现
以下列数组为例：
int[] list = new int[]{5,2,8,3,7,6,4,0,1,9};
①：随意指定数组中一个值（一般取数组中第一个元素），称为枢轴（pivot），拿数组中每个数据和枢轴对比，比枢轴大的放枢轴右边，比枢轴小的放枢轴左边
蓝色：往前移动
红色：往后移动
第一次比较：
第二次比较：
第三次比较：
第四次比较
。。。。。。以此类推，最后得到下面的数组
②：以枢轴为切分点切分成两个数组
③：对切分后的数组分别再调用步骤①、②进行排序，切分，最终完成排序
—————————————————————————————————————
但是，实际上这边存在一个问题！！！！！
问题描述：
仔细查看步骤①的第三次比较，发现当3前移时，需要移动5和8共2个元素，如果此时5和3之间夹带的不止一个8，可能有100，1000个元素呢？岂不是要全部后移一位？那样就非常浪费时间！
解决方案：
快速排序的逻辑虽然是拿数组中每个数据和枢轴对比，比枢轴大的放枢轴右边，比枢轴小的放枢轴左边，但算法其实是这样的
- 前置条件：
- Ⅰ仍然指定数组中第一个元素为枢轴（pivot）
- Ⅱ每次比较一定是枢轴和其他元素的比较
- Ⅲ对比元素选取规则：
- 1.当前对比元素如果在枢轴左边，则下一个对比元素即当前对比元素的下标+1
- 2.当前对比元素如果在枢轴右边，则下一个对比元素即当前对比元素的下标-1
第一次比较：
第二次比较：
第三次比较
第四次比较
第五次比较
第六次比较
第七次比较
第八次比较
最终比较
可以看到，每次调换都只移动了2个元素的位置，节约了大部分时间。
步骤①完成改进后，其他步骤②③没有改变
—————————————————————————————————————
代码实现
定义快速排序方法
void quickSort(int[] list) {
//调用快速排序真实方法，主要是为了调用方法时传参方便，只需要传入一个数组
sort(list, 0, list.length-1);
}定义快速排序真实方法
void sort(int[] list, int low, int high) {
//定义枢轴
int pivot;
//low<higt，保证遍历时，左元素和右元素对比到下标一致时就结束
if (low < high) {
//此处代码代表的就是步骤①（1）
pivot = compare(list, low, high);
//对切分后的左边的数组调用递归排序
sort(list, low, pivot - 1);
//对切分后的右边的数组调用递归排序
sort(list, pivot + 1, high);
}
}定义核心代码，元素比较与转换模块
int compare(int[] list, int low, int high) {
//记录枢轴的大小
int pivotKey;
//默认定义枢轴元素为左起第一个元素
pivotKey = list[low];
//low<higt，保证遍历时，左元素和右元素对比到下标一致时就结束
while (low < high) {
//上诉提到的元素对比规则Ⅲ中的第2条：
//当前对比元素如果在枢轴右边，则下一个对比元素即当前对比元素的下标-1
while (low < high && list[high] >= pivotKey)
high--;
//直到找到比枢轴小的元素，枢轴与对比元素进行交换
swap(list, low, high);
//上诉提到的元素对比规则Ⅲ中的第1条：
//当前对比元素如果在枢轴左边，则下一个对比元素即当前对比元素的下标+1
while (low < high && list[low] <= pivotKey)
low++;
//直到找到比枢轴大的元素，枢轴与对比元素进行交换
swap(list, low, high);
}
}定义对调位置的函数
void swap(int[] list,int low,int high){
int middle = list[low];
list[low]=list[high];
list[high]=middle;
}好了，快速排序的逻辑实现和代码实现都已经完成。以上就是对快速排序的介绍
逻辑实现的内容是自己编写，图片也是自己用PPT做出来的截图的
代码实现参考了程杰老师的《大话数据结构》
如果需要转载，请注明出处
https://blog.csdn.net/weixin_42152023/article/details/82689894