从大二开始，就没写过任何算法相关的东西了，数据结构也只是知道一个大概而已。最近在看《Thinking in Java》，看到集合一章的时候，书中使用到了快速排序。我一直在自嘲不会手写快排，不会翻转二叉树，今天就顺便看了下快排的思想。
初步
对于一个数组（简化为整数数组）：
- 任选其中一个作为轴点（简化选择最后一个值）。
- 然后从两端用两个指针（L，R）进行遍历：
- L指针从左侧开始遍历，如果指向的数值不小于轴点，则停止。
- R指针开始从右侧遍历，如果指向的数值不大于轴点，则停止。
- 交换LR指针所指向的值,LR指针继续移动。
- 直至LR指针相遇
- LR指针指向同一点，交换此值与轴点。此时，此点左侧（L遍历过的）所有的值均小于此点，右侧（R遍历过的）所有的值均大于此点。
- 把此点左右分别进行递归快排。
实现
private static void quickSort(int[] arrays, int start, int end) {
//先判断是否已经不需要排序
if (end > start) {
//找到轴点
int pivot = arrays[end];
int l = start;
int r = end - 1;
while (l < r) {
//从左边开始遍历，直到左边某个数不小于轴点
while (arrays[l] < pivot && l < r) {
l++;
}
//从右边开始遍历，直到右边某个数不大于轴点
while (arrays[r] > pivot && r > l) {
r--;
}
//此时l指向的值不小于轴点，r指向的值不大于轴点
swap(arrays, l, r);
}
swap(arrays, l, end);
quickSort(arrays, start, l - 1);
quickSort(arrays, l + 1, end);
}
}
换种方式
再次把思路简化一下：
- 任选其中一个作为轴点。
- 搞个大动作，把轴点移动（交换到中间），使这个轴点左边的值均小于此点，右边的值都大于此点。
- 把此点左右分别进行递归快排。
伪实现
private static void quickSort2(int[] arrays, int start, int end) {
if (end > start) {
//确定轴点
int pivot = doBigThing(arrays, start, end);
quickSort2(arrays, start, pivot - 1);
quickSort2(arrays, pivot + 1, end);
}
}
具体细节
依旧可以像上面那样两个指针LR，分别从左和从右开始遍历，直至相遇。 也可以这样：
- 用两个指针，一前一后进行遍历。
- 保证其中一个指针L左侧所有的值都小于等于轴点，所在点大于轴点。
- 另外一个指针P则由L向右移动，当P指向的值小于轴点时，交换LP所指向的值。
- L向前移动，P也继续向前移动。
- 直至P移动到最后一位。
- 此时L点左侧都小于轴点，右侧都大于轴点（因为P遍历过，如果存在小于轴点的点，早就交换位置了）。
具体实现
static int partition(int[] arrays, int start, int end) {
int l = start;
int pivot = arrays[end];
for (int p = start; p < end; p++) {
if (arrays[p] < pivot) {
swap(arrays, p, l);
l++;
}
}
swap(arrays, l, end);
return l;
}