快速排序
快速排序简介
快速排序是一种基于交换的排序方式（另一种基于交换的排序方式是冒泡排序），它的时间复杂度是nlog_2n。它的思路如下
先在元素序列中选择一个元素作为基准（一般选第一个元素），然后进行一次划分操作，划分操作简单说来就是将小于该基准的元素放在基准的左边，将大于该基准的元素放在基准的右边（不需要考虑左边元素是不是有序的，即只要把小于基准的放在左边就行了，不需要考虑到底放在左边的哪个位置。右边元素也是这个道理)。然后递归处理基准左边的序列和基准右边的序列，递归出口是序列中的元素数小于两个时。
划分操作概述
- 首先设置两个指针，分别指向序列的首尾，令首指针为tmpL, 尾指针为tmpR。
- 将首元素作为基准保存在变量pivotal中。
- 当首指针小于尾指针时进行循环
- 先从尾指针出发，往前遍历元素序列，直到找到一个小于pivotal的元素，将这个元素放到首指针的位置（此时首指针指向元素已经存放在另一个位置中了：第一次while循环时存在pivotal变量中，以后就存在上一次循环的尾指针中，所以不用担心首指针指向的元素被覆盖）
- 再从首指针出发，往后遍历元素序列，直到找到一个大于pivotal的元素，将这个元素放到尾指针的位置
- 退出循环时首指针等于尾指针，且它们就指向了基准元素应该放在的位置，所以将pivotal放进这个位置
Java实现
public class Quick{
public static void main(String[] args){
Integer[] integers = {1, 3, 2, 4, 1, 5, 4};
Quick.sort(integers);
System.out.println(integers);
}
public static void sort(Comparable[] array){
sort(array, 0, array.length - 1);
}
// 划分操作
@SuppressWarnings("unchecked")
private static void sort(Comparable[] array, int left, int right){
Comparable pivotal = array[left];
int tmpL = left, tmpR = right;
while (tmpL < tmpR){
while (tmpR > tmpL && array[tmpR].compareTo(pivotal) >= 0)
tmpR--;
array[tmpL] = array[tmpR];
while (tmpR > tmpL && array[tmpL].compareTo(pivotal) <= 0)
tmpL++;
array[tmpR] = array[tmpL];
}
array[tmpL] = pivotal;
if (tmpR - 1 > left)
sort(array, left, tmpR-1);
if (tmpR + 1 < right)
sort(array, tmpR+1, right);
}
}
