快速排序
基本思想
快速排序的基本思想就是类似于分书。我记得我学快速排序听到的故事就是分书的故事。
有一堆书他们有相应的序号,现在图书管理员希望你帮他把这些书按序号从小到大分好给他。我们采取的方案是把第一本书作为基准,把序号比他大的丢到右边,序号比他小的丢到左边。从而我们一直分直到所有的书都按顺序排好为止。
只要左右分的方法我们就称为快速排序。
代码实现
public class Main {
public void quickSort(int[] arr, int l, int r) {
if(l < r) {
int pivot = partition(arr, l, r);
quickSort(arr, l, pivot);
quickSort(arr, pivot+1, r);
}
}
public int partition(int[] arr, int l, int r) {
int pivot = arr[l];
while(l < r) {
while(l < r && arr[r] >= pivot) r--;
arr[l] = arr[r];
while(l < r && arr[l] <= pivot) l++;
arr[r] = arr[l];
}
arr[l] = pivot;
return l;
}
}