快速排序
快速排序的思想
- 从待排序区间选择一个数，作为基准值（pivot）；
- Partition：遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
- 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 ==1，代表已经有序，或者小区间的长度 ==0，代表没有数据。
快速排序时间复杂度为O(nlogn)，是一个不稳定的排序算法。
图解如下：
基准值的选择
- 选择边上（左或者右）：在接近有序的数组上，快排会退化为O(n^2)，左右两个子区间严重不平衡，二叉树退化为链表。
- 随机选择：随机在当前数组中选取一个树作为基准值。
- 几树取中，一般都是三数取中。
第二种和第三种都能避免在递归过程中，在接近有序的数组上，快速排序的分区严重不平衡的问题。
代码
public static void quickSort(int[] arr){
quickSortInternal(arr,0,arr.length-1);
}
private static void quickSortInternal(int[] arr, int l, int r) {
//优化1：小区间上使用插入排序，减少递归的次数
if (r-l<=15){
insertionSort(arr, l, r);
return;
}
//先获取分区点，分区点左侧全是小于该元素的区间，分区点右侧全是大于该元素的区间
int p=partition(arr,l,r);
quickSortInternal(arr, l, p-1);
quickSortInternal(arr, p+1, r);
}
private static int partition(int[] arr, int l, int r) {
//优化2：随机在当前数组中选一个数
//能避免递归过程中，在接近有序的数组上，快速排序的分区严重不平衡的问题
int randomIndex=random.nextInt(l,r);
swap(arr,l,randomIndex);
int v=arr[l];
//1.先选一个基准点
//int v=arr[l];
//分区点：
//arr[l+1...j] < v
//arr[j+1...i) >= v
//i表示当前正在扫描的元素
int j=l;
for (int i = l+1; i <=r ; i++) {
//如果arr[i]小于v，就将大于v的第一个元素和正在扫描的元素进行交换
if (arr[i]<v){
swap(arr,i,j+1);
j++;
}
}
//将基准值和最后一个小于v的元素进行交换，基准值就到了最终位置
swap(arr,j,l);
return j;
}
二路快排
为什么引入二路快排？
当待排序的集合中出现大量重复元素时，就会导致某个分区的元素过多（相等的元素全在一个区间中），造成递归过程中，递归树严重不平衡，快排退化为O(n^2)。二路快排就是将相等的元素均分到左右两个子区间，解决了递归树严重不平衡的问题。
图解如下：
代码如下：
private static final ThreadLocalRandom random=ThreadLocalRandom.current();
public static void quickSort(int[] arr){
quickSortInternal(arr,0,arr.length-1);
}
private static void quickSortInternal(int[] arr, int l, int r) {
//优化1：小区间上使用插入排序，减少递归次数
if (r-l<=15){
insertionSort(arr,l,r);
return;
}
//获取分区点
int p=partition(arr,l,r);
quickSortInternal(arr,l,p-1);
quickSortInternal(arr,p+1,r);
}
private static int partition(int[] arr,int l,int r){
//优化2：随机选取基准值
int randomIndex=random.nextInt(l,r);
swap(arr,l,randomIndex);
int v=arr[l];
int i=l+1; //[l+1..i)<=v
int j=r; //(j..r]>=v
while (i<=j){
//i从前向后扫描，碰到第一个大于等于v的元素停止
while (i<=j && arr[i]<v){
i++;
}
//j从后向前扫描，碰到第一个小于等于v的元素停止
while (i<=j && arr[j]>v){
j--;
}
if (i>=j){
break;
}
//如果此时i<j，交换i和j的元素
swap(arr,i,j);
i++;
j--;
}
//此时j指向小于等于v的区间的最后一个元素
swap(arr,l,j);
return j;
}
private static void insertionSort(int[] arr,int l,int r){
for (int i = l+1; i <=r ; i++) {
for (int j = i; j >0 ; j--) {
if (arr[j]>=arr[j-1]){
break;
}else{
swap(arr,j,j-1);
}
}
}
}
private static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
三路快排
三路快排思想：在一次分区函数的操作中，将所有相等的元素都放在最终位置，只需要在小于v和大于v的子区间上进行快排，所有相等的元素就不再处理了。
图解如下：
代码如下：
private static final ThreadLocalRandom random=ThreadLocalRandom.current();
public static void quickSort(int[] arr){
quickSortInternal(arr,0,arr.length-1);
}
private static void quickSortInternal(int[] arr, int l, int r) {
//小区间使用插入排序
if (r-l<=15){
insertionSort(arr,l,r);
return;
}
//随机选取基准值
int randomIndex=random.nextInt(l,r);
swap(arr,l,randomIndex);
int v=arr[l];
int lt=l; //arr[l+1..lt]<v lt代表小于v的最后一个元素
int i=lt+1; //arr[lt+1..i)==v i代表正在扫描的元素
int gt=r+1; //arr[gt..r]>v gt指向第一个大于v的元素
//i表示当前扫描元素
while (i<gt){
if (arr[i]<v){
swap(arr,lt+1,i);
lt++;
i++;
}else if (arr[i]==v){
i++;
}else{
//当前扫描元素大于v时，将gt-1与i交换，i不加加，因为换过来的gt-1还没处理
swap(arr,i,gt-1);
gt--;
}
}
swap(arr,l,lt);
quickSortInternal(arr, l, lt-1);
quickSortInternal(arr, gt, r);
}
public static void insertionSort(int[] arr,int l,int r){
for (int i = l+1; i <=r ; i++) {
for (int j = i; j >0 ; j--) {
if (arr[j]>=arr[j-1]){
break;
}else{
swap(arr,j,j-1);
}
}
}
}
public static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
总结
- 当待排序的集合重复元素并不多时，随机化快排已经可以解决问题，甚至性能比二路快排和三路快排还要好；
- 当待排序集合中有大量重复元素时，使用二路快排或三路快排优化重复元素的处理；
- 当待排序集合是一个接近有序的集合，分区点的选择就不能单纯选择最左侧或最右侧，可以使用随机化选择或三数取中。