思想：
以数据中的一个数为基准P，把数据分成大于这个基准的一份和小于这个基准的一份（分区）。在再分区的数据中重复这个过程，直到分区只剩一个数据就完成了排序。
具体排序过程：
1.1 默认数据中的第一个为基准数据P， 左指针PL指向第一个数据，右指针PR指向最后一个元素
1.2 PL和PR分别和P进行比较，如果RL <= P即左边的数据小于P，将LR右移一位，如果大于P则看RP，如果RP < LP, 则将LR 和RP位置的数据互换。
1.3 PR 和 P进行比较，如果 PR > P 则将PR左移一位，否则不变。如果RP < P < LP , 则将LR 和RP位置的数据互换，类似上一步。
1.4 LP 和 RP 相遇，则将P插入LR和RP中，第一次分区完成。
1.5 重复上面的过程，直到分区只有一个数据。
e.g:
outOfSoted: 4, 10, 9 ,3, 5, 8 , 2, 9, 11, 6
P: 4
PL: 4
PR: 6
outOfSoted: pl:4, 10, 9 ,3, 5, 8 , 2, 9, 11, pr:6
PL <= P, PL右移， PL = 10
PR > P, PR左移， PR = 11
result： 4 l:10 9 3 5 8 2 9 r:11 6
PL > P, PL位置不变， PL = 10
PR > P, PR左移， PR =9
result： 4 l:10 9 3 5 8 2 r:9 11 6
PL > P, PL位置不变， PL = 10
PR > P, PR左移， PR = 2
result： 4 l:10 9 3 5 8 r:2 9 11 6
PL > P, PL位置不变， PL = 10
PR <= P, PR位置不变， PR = 2
PL > P && PR < PL, 互换PL和PR的值，PL = 2, PR = 10
result： 4 l:2 9 3 5 8 r:10 9 11 6
PL <= P, PL右移， PL = 9
PR > P, PR左移， PR = 8
result：4 2 l:9 3 5 r:8 10 9 11 6
PL > P, PL不变， PL = 9
PR > P, PR左移， PR = 5
result：4 2 l:9 3 r:5 8 10 9 11 6
PL > P, PL不变， PL = 9
PR > P, PR左移， PR = 3
result：4 2 l:9 r:3 5 8 10 9 11 6
PL > P, PL不变， PL = 9
PR <= P, PR不变， PR = 3
PL > P && PR < PL, 互换PL和PR的值，PL = 3, PR = 9
result：4 2 l:3 r:9 5 8 10 9 11 6
PL < P, PL 右移， PL = 9
PL = PR，比较PR和P的大小，PR > P, 位置不变，将P插入PR前（PR前的数据都<=p,故将PR-1和P互换位置即可）。
至此，第一次分区完成，3 2 4 9 5 8 10 9 11 6 ,P前面的数据都比P小，后面分区的数据都比P大，对分区重复上面的过程，直到所有分区的数据只剩一个就完成了排序。
2. 优点对冒泡排序中天然有序的部分数据进行了优化，会直接跳过，所以更快，称为快排
3. java代码实现import cn.jiayeli.sorts;
import java.util.Arrays;
import java.util.Random;
public class FastSort {
int realPr = 0;
@Test
public void fastOrder() {
Integer[] outOfOrder = new Integer[10];
System.out.println("OutOfOrder");
for (int i = 0; i < outOfOrder.length; i++) {
Random random = new Random();
outOfOrder[i] = random.nextInt(20);
System.out.print(outOfOrder[i] + "t,");
}
System.out.println(Arrays.asList(outOfOrder) + "n");
// 第一次初始化时以第一个为基准，其等于它自己，直接右移一位
partitionSort(outOfOrder, 1, outOfOrder.length-1);
}
public void partitionSort(Integer[] outOfOrder, int pl, int pr) {
int p = pl;
int temp = 0;
//第二个分区偏移量
realPr = pl == 0 && realPr != 0 ? 0 : realPr;
if (outOfOrder.length > 1) {
//分区只有一个元素时结束该分区的排序
while (pr - pl > 0 ) {
if (outOfOrder[pl] > outOfOrder[p] && outOfOrder[pr] < outOfOrder[pl]) {
temp = outOfOrder[pl];
outOfOrder[pl] = outOfOrder[pr];
outOfOrder[pr] =temp;
}
pl = outOfOrder[pl] <= outOfOrder[p] ? ++pl : pl ;
pr = outOfOrder[pr] > outOfOrder[p] ? --pr : pr;
//右边的数小于基准且左边的数大于基准，交换两个指针位置的数据
if (pl >= pr) {
if (outOfOrder[pr] > outOfOrder[p]) {
temp = outOfOrder[pr-1];
outOfOrder[pr-1] = outOfOrder[p];
outOfOrder[p] = temp;
} else {
temp = outOfOrder[pr];
outOfOrder[pr] = outOfOrder[p];
outOfOrder[p] = temp;
}
// 保证第二个分区计算时偏移量不被覆盖
realPr = realPr == 0 ? pr : realPr;
System.out.println("p:t" + p + "tpr:t" + pr);
System.out.println("p:t" + outOfOrder[p] + "tpr:t" + outOfOrder[pr]);
System.out.println(Arrays.asList(outOfOrder));
//对第二个分区进行计算
partitionSort(outOfOrder, pr+1, outOfOrder.length-1);
//对第一个分区进行计算
partitionSort(outOfOrder, 0, realPr-1);
}
}
}
}
}
