【交换排序】快速排序
前言
平常码砖的时候，对于一个数组进行排序更多的是起泡排序，起泡排序对于一般不是很长的数组进行操作没什么问题，一旦数组过大，很明显效率低。
而快排是对起泡排序的一种改进，效率明显优高。
快排思想
快排的思想是通过每一次排序将待排的数组分成两部分，左边的部分所有值均小于右边部分，然后再对这两部分分别再进行排序以达到整修序列有序。
Example
有如下一个无序的序列 arr[]（长度为10)，现在要对其进行快排
1
| 10 | 9 | 22 | 38 | 47 | 7 | 11 | 2 | 82 | 1 |
1.首先要先任一个记录作为枢轴（也可称为支点），然后将其它的记录与期进行对比，比枢轴小的记录放左边，
比枢轴大的记录放右边通常我们选取序列的第一个记录作为枢轴。
1
2
3
| 10 | 9 | 22 | 38 | 47 | 7 | 11 | 2 | 82 | 1 |
将arr[0]＝10 作为枢轴
2.接下来将各记录与其进行对比，关键是如何将各记录与枢轴进行对比，这里涉及到一个小的技巧，挖坑填坑！
将枢轴赋给一个临时的变量，挖一个坑，寻找一个比枢轴小的值来填此坑：
1
2
3
int tmp = arr[0]
| | 9 | 22 | 38 | 47 | 7 | 11 | 2 | 82 | 1 |
3.寻找比枢轴小的值可以有几种方法，但是否都能行得通？我们来分析下
a. 如果先按从左到右的顺序进行寻找，经过一次排序后，序列如下：
1
2
3
4
5
6
7
8
9
| | 9 | 22 | 38 | 47 | 7 | 11 | 2 | 82 | 1 |
| 9 | | 22 | 38 | 47 | 7 | 11 | 2 | 82 | 1 |
| 9 | 7 | 22 | 38 | 47 | | 11 | 2 | 82 | 1 |
| 9 | 7 | 22 | 38 | 47 | 2 | 11 | | 82 | 1 |
| 9 | 7 | 22 | 38 | 47 | 2 | 11 | 1 | 82 | 10 |
现在的情况是，比枢轴10小的记录确实已经排到了枢轴的左边，但你有办法将比10大的记录都排右边吗？
有吗？ 好像没有吧…
如果，再把末尾的10挖出个坑来，让大的数来填，最后你发现，大的记录确实到了枢轴的右边，但小的记录又分布枢轴两边…
所以无论是一开始从右向左或者是从左向边一口气的排序并不能解决我们的问题… Game Over!
b.作为人人敬仰的聪明小一休会坐下来静下心，迪迪哇哇迪迪哇哇三秒钟，脑洞大开，又有一方法：
我们轮流从头尾拿记录与枢轴进行对比进行交换，情况会如何?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| | 9 | 22 | 38 | 47 | 7 | 11 | 2 | 82 | 1 |
| 1 | 9 | 22 | 38 | 47 | 7 | 11 | 2 | 82 | |
| 1 | 9 | | 38 | 47 | 7 | 11 | 2 | 82 | 22|
| 1 | 9 | 2 | 38 | 47 | 7 | 11 | | 82 | 22|
| 1 | 9 | 2 | | 47 | 7 | 11 | 38| 82 | 22|
| 1 | 9 | 2 | 7 | 47 | | 11 | 38| 82 | 22|
| 1 | 9 | 2 | 7 | | 47| 11 | 38| 82 | 22|
| 1 | 9 | 2 | 7 | 10 | 47| 11 | 38| 82 | 22|
经过轮流头尾记录与枢轴进行对比交换后，达到了我们的预期序列，开不开森呐？
将下来只是递归的问题了，对枢轴左右两部分再次进行以上步骤，即可将此序列有序
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Public class Demo{
public static void quickSort(int arr[], int startPos, int endPos){
if(startPos >= endPos) return;
int tmp = arr[startPos];
int i = startPos;
int j = endPos;
while(i < j){
while(i < j && arr[j] > tmp){
j--;
}
if(i < j){
arr[i++] = arr[j];
}
while(i < j && arr[i] < tmp){
i++;
}
if(i < j){
arr[j--] = arr[i];
}
}
arr[i] = tmp;
quickSort(arr, startPos,i-1);
quickSort(arr, i+1, endPos);
}
}
本篇所属：算法篇