1、前言
快速排序是一个经典的排序，而且针对特定的问题，又分为2路快排和3路快排。今天，我们不搞这些复杂的，就搞经典快排。
快速排序.png
如图所示，快速排序如果遇到数组都有序的情况，那么快排将会退化成O(n^2)，所以选择随机快排来更改这个情况。然后变成了一个概率事件，长期期望为O(n*logn)。
快排总体思路：
1.先将数组分开，小于基准的放左边，等于的放中间，大于的放右边，然后依次对左右进行类似的操作。
2.关于partition函数，less相当于左边界，more相当于右边界，像 左） 数组 （右。
快排其实有两种思路，思路一是分成了小于区less区，大于区more区，然后每次将小于基准的放到小于区，小于区扩大一个，表现为less++；每次把大于基准的放到大于区，大于区扩大一个，表现为more--。
partition函数思路二是，选择一个基准，然后从数组的右端向左端扫描直到找到一个小于它的元素，停止，然后从数组的左端到右端扫描，直到找到一个大于它的元素，停止，然后交换两个元素的位置。当两个指针相遇时，交换基准和相遇位置的元素。
2、代码
//思路一
public class QuickSort {
public void quickSort(int[] arr){
if(arr == null || arr.length < 2)
return;
quickSort(arr, 0, arr.length - 1);
}
public void quickSort(int[] arr, int L, int R){
if(L < R){
swap(arr, L + (int)(Math.random() * (R - L + 1)), R); // 随机选一个数与最后一个数交换
int[] p = partition(arr, L, R); //把小的放左边，等于放中间，大的放右边
quickSort(arr, L, p[0] - 1);//排左边
quickSort(arr, p[1] + 1, R);//排右边
}
}
public int[] partition(int[] arr, int L, int R){
int less = L - 1;
int more = R;
while(L < more){
if(arr[L] < arr[R])
swap(arr, ++less, L++);
else if(arr[L] > arr[R])
swap(arr, --more, L);
else
L++;
}
swap(arr, more, R);
return new int[]{less + 1, more};
}
public void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 3, 6, 2, 1, 9};
new QuickSort().quickSort(arr);
for (int e: arr) {
System.out.println(e);
}
}
}
//思路二
public class quickSort2 {
public void quickSort(int[] arr){
if(arr == null || arr.length < 2)
return;
quickSort(arr, 0, arr.length - 1);
}
public void quickSort(int[] arr, int L, int R){
if(L < R){
swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
int i = partition(arr, L, R);
quickSort(arr, L, i - 1);
quickSort(arr, i + 1, R);
}
}
public int partition(int[] arr, int L, int R){
int index = R;
R--;
while(L < R){
while (arr[R] > arr[index])
R--;
while(arr[L] < arr[index])
L++;
swap(arr, arr[R--], arr[L++]);
}
swap(arr, arr[index], arr[L]);
return L;
}
public void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 3, 6, 2, 7, 3, 1, 9};
new QuickSort().quickSort(arr);
for (int e: arr) {
System.out.println(e);
}
}
}
3、扩展
在实际工作做，我们经常会遇到对一个对象排序，而且往往是根据对象的多个条件进行排序。比如有一个对象 Num，它有一个 left、right 属性，我们希望它先按照 left 生序排序，如果有 left 相等的则按照 right 生序排序。
我们可以因此陷入懵逼，因为一个我会，但是两个的话就不知道该怎么操作了。其实我们可以假设一下，快排中只有 left、right 与哨兵都相等我们才算是相等的，在 left 相等的情况下，right 小于哨兵的 left 则认为可以放到小于区域，right 大于哨兵的则认为可以放到大于区域。后面小于区域排序的时候，因为这些数 left 都是最大的，自然会排到哨兵的左边；右边也同理。
到最后的时候，肯定能根据你想要的要求排好序。代码如下：
public class MaxEnvelopes {
class Num {
int left;
int right;
public Num(int left, int right) {
this.left = left;
this.right = right;
}
}
public static void main(String[] args) {
int[][] envelopes = {{4, 5},{4, 6},{6,7},{2,3}, {1, 1}, {9,1}, {2, 6}, {4, 5}};
Num[] list = new MaxEnvelopes().quickSort(envelopes);
for (Num num : list) {
System.out.println(num.left + ":" + num.right);
}
}
public Num[] quickSort(int[][] envelopes){
Num[] list = new Num[envelopes.length];
for (int i = 0; i < envelopes.length; i++) {
list[i] = new Num(envelopes[i][0], envelopes[i][1]);
}
quickSort(list, 0, list.length - 1);
return list;
}
public void quickSort(Num[] arr, int L, int R){
if(L < R){
swap(arr, L + (int)(Math.random() * (R - L + 1)), R); // 随机选一个数与最后一个数交换
int[] p = partition(arr, L, R); //把小的放左边，等于放中间，大的放右边
quickSort(arr, L, p[0] - 1);//排左边
quickSort(arr, p[1] + 1, R);//排右边
}
}
public int[] partition(Num[] arr, int L, int R){
int less = L - 1;
int more = R;
while(L < more){
if(arr[L].left < arr[R].left)
swap(arr, ++less, L++);
else if(arr[L].left > arr[R].left)
swap(arr, --more, L);
else{
// 关于那种多条件排序，肯定是遇到有一个条件相等的情况下，
// 后面再比较另一个条件，看放到大于区、小于区、还是等于区
if(arr[L].right < arr[R].right)
swap(arr, ++less, L++);
else if(arr[L].right > arr[R].right)
swap(arr, --more, L);
else
L++;
}
}
swap(arr, more, R);
return new int[]{less + 1, more};
}
public void swap(Num[] arr, int i, int j){
Num temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
