浅谈快速排序
2021-04-08 10:26
标签：排序 -- quic 数据 索引 == 一个 完成后 中间 快速排序的核心是先找到一个比较的基数,然后从左往右寻找比基数大的值,从右往左找到比基数小的值,最后交换数据 浅谈快速排序 标签：排序 -- quic 数据 索引 == 一个 完成后 中间 原文地址：https://www.cnblogs.com/zhijm/p/13378938.htmlpublic static void quickSort(int left,int right,int[]arr){
// 获取最左边的索引和最右边的索引
int l=left;
int r=right;
// 以中间的索引为比较的基数
int middlePoint=arr[(left+right)/2];
// 开始遍历比较
while(lr){
// 先往左遍历,找到比中间值大的
while (arr[l]middlePoint){
l++;
}
// 往右遍历,找一个比中间值小的
while (arr[r]>middlePoint){
r--;
}
// 如果l>=r的时候就没有必要比较了,因为已经满足了以中间值为界限左边小,右边大
if(l>=r){
break;
}
// 开始交换
int tenp=arr[l];
arr[l]=arr[r];
arr[r]=tenp;
// 如果交换完成后 两值都等于中间值,那就跳过 这一步可有可无,有的话就优化一些
if(arr[l]==middlePoint){
r--;
}
if(arr[r]==middlePoint){
l++;
}
}
// 如果最后两个索引相等 ,那就各自一个往右移动一位,一个往左移动一位
if(l==r){
r--;
l++;
}
if(lright){
quickSort(l,right,arr);
}
if(r>left){
quickSort(left,r,arr);
}
}
上一篇：后缀数组模板题总结