1.借鉴
2. 开始
图解
- 我们以数组{49, 38, 65, 97, 23, 22, 76}为例,升序排序,则流程如下:
实现
public static void main(String[] args) {
int[] ints = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
quickSort(ints, 0, ints.length - 1);
System.out.println(Arrays.toString(ints));
}
static void quickSort(int[] a, int l, int r) {
// 1. 判断终止条件,如果左>=右,则停止
if (l >= r) return;
// 2. 要干什么?
// 将tmp放到正确的位置,将小于tmp的放左边,大于等于tmp的放右边
int i = l, j = r, tmp = a[l];
while(i < j) {
while(i < j && tmp < a[j]) j--;
if(i < j) a[i++] = a[j];
while(i < j && tmp > a[i]) i++;
if(i < j) a[j--] = a[i];
}
a[i] = tmp;
// 递归,此时i在l和r之间,分别处理左边和右边
quickSort(a, l, i - 1);
quickSort(a, i + 1, r);
}
3. 大功告成
自己画一遍,就会很清楚了,思路有了,还怕没法实现吗?
网友评论