变量命名及背景
- 数组为 q
- 数组 q 左下标为 l
- 数组 q 右下标为 r
- i,j 分别为数组 q 的左右两个指针,向中间移动
模板默写思路
- 递归返回条件:当只有一个元素:即 l==r,什么都不做直接 return。用 l>=r 也可以,个人习惯问题,此处用 l>=r
- 找到分界值 x ,一般可取的值为:q[l],q[(l+r)/2],q[r],便于解决边界值和方便记忆,x=q[l]
- 初始化 i,j的值,便于解决边界值问题,i=l--,j=r++,定义为数组第一个和最后一个左边的两侧
- i 和 j 向中间走,直到相遇为止,因此,第一个循环限制条件是 while(i<j){...}
- 在第一个while循环的每一次遍历里面,i不断向中间靠近,每走一步,如果元素q[i]小于临界值x则可以继续走,直到不满足这个条件为止。于是可以简写为:while(q[++i]<x)。j同理,只不过从右边往中间,所以简写为:while(q[--j]>x)
当i和j都停下来,则检查是否相交,不相交(i<j)就交换 q[i] 和 q[j];
- 注:这时候如果i和j都停下来,但是不满足 i<j 表示相交了,什么都不要做,因为接下来就是退出循环,进行快排左边和快排右边。也就是此时肯定是相交,同时不满足第一个循环的条件while(i<j){...},退出循环
- 递归执行排序左边和右边
模板
public class QuickSort785 {
public static void main(String[] args) {
int[] arr = new int[]{3, 5, 3, 9, 8};
int num = arr.length;
quickSort(arr, 0, num - 1);
for (int value : arr) {
System.out.print(value + " ");
}
}
private static void quickSort(int[] q, int l, int r) {
if (l >= r) {
return;
}
// 第1步,找x,设定i和j,注意定义i,j为两侧
int x = q[l], i = l - 1, j = r + 1;
while (i < j) { // 每一次循环,代表i与j暂停,交换后!i和j继续左走和右走
// 第2步,以x为标准分隔,走左右两边
while(q[++i] < x){}
while(q[--j] > x){}
// 第3步,两个指针还没有相遇,交换,没有交换,(如果i与j相遇了,就不能交换了,交换就出问题!)
if (i < j) {
swap(q,i,j);
}else {
// 这里代表相遇,相遇则不会有下个循环,本次结束
}
}
// 第4步,递归排左和右
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
public static void swap(int[] q, int a, int b) {
int t = q[a];
q[a] = q[b];
q[b] = t;
}
}
本文由 ONE 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
如有版权疑问交流,请给我留言:oneisall8955@gmail.com
本文永久链接:http://liuzhicong.cn/index.php/study/alg-quick-sort_template_acwing785.html
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
如有版权疑问交流,请给我留言:oneisall8955@gmail.com
本文永久链接:http://liuzhicong.cn/index.php/study/alg-quick-sort_template_acwing785.html