快速排序
思路：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
复杂度分析：
其平均时间复杂度与归并排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。
所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。
下面是三种快排实现，其中针对特殊的情况
（1）对已排序的序列进行快排
（2）对数字全部相同的一个序列进行快排
上面两种情况都会导致快排的时间复杂度达到O(n^2)，所以有了双轴快排和随机化快排
一、经典快排
public class QuickSort {
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int middle = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, middle - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, middle + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public static int partition(int[] list, int left, int right) {
// 用数组的最后一个元素作为基准数
int less = -1; // less区，小于基准的元素都放在其左边
while (left < right){
if(list[left] < list[right]){
less++;
swap(list, less, left);
}
left++;
}
swap(list, less+1, right);// 将基准值放序列中间，完成partition过程
return less+1;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
}
二、双轴快排
双轴快排避免了由于待排序列是有序的，而导致时间复杂度达到O(n^2)的情况
public class QuickSort {
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int middle = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, middle - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, middle + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public static int partition(int[] list, int left, int right) {
// 选取第一个元素为基准
int flag = list[left];
while (left < right) {
while (left < right && list[right] >= flag) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= flag) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
}
三、随机化快排
随机数快排避免了由于待排序列是相同的数，而导致时间复杂度达到O(n^2)的情况
public class QuickSort {
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int middle = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, middle - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, middle + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public static int partition(int[] list, int left, int right) {
// 随机选取一个基准
int length = right-left+1;
int index = new Random(47).nextInt()%(length+left);
// 将随机基准放到序列首部，之后以首部为基准进行快排
swap(list, left, index);
int flag = list[left];
while (left < right) {
while (left < right && list[right] >= flag) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= flag) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
}
以上是我在学习过程中对于快排的总结，若有不足之处，欢迎评论。
