快速排序（QuickSort）
1、思想
快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
说明：最核心的思想是将小的部分放在左边，大的部分放到右边，实现分割。
2、算法复杂度
最好的情况下：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN)
最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较N*N次，故为O(N*N)
3、稳定性
由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！
4、实现
Java实现方式。
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] data = { 49, 38, 65, 97, 76, 13, 27, 9 };
quickSort(data, 0, data.length - 1); // 第一种实现方式
printData(data);
}
public static void quickSort(int[] data, int low, int high) {
int i = low;
int j = high;
// 参数检查
if (low >= high) {
return;
}
int comparableKey = data[low]; // 一般选取第一个数为基数
if (i < j) {
while (i < j) {
while (i < high && comparableKey > data[i]) { // 从左边开始查找找到一个比基数大的数。
i++;
}
while (low < j && comparableKey < data[j]) { // 从右边开始查找找到一个比基数小的数。
j--;
}
if (i < j) {
swap(data, i, j);
}
}
quickSort(data, low, i - 1);
quickSort(data, j + 1, high);
}
}
public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void printData(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
}