上手难度：★★★★
算法复杂度：O(nlogn)
排序思想：
预先设定三个空间
l为最左边的索引
初始值lt=l, gt=r+1, i = l + 1
arr[l+1~lt) 存放的是小于v的值
arr[l+1 ~ i)存放的是等于v的值
arr[gt~r]存放的是大于v的值
初始的时候这三个区间都为空
进入while(i < gt)的循环
当arr[i]<v时，将i和lt+1的值交换位置，同时i和lt向右移动，i移动是为了比较下一个值，lt移动是因为左边的区间多了一个值
当arr[i]>v时，将i和gt-1的值交换位置，gt向左移动，i不变，因为交换来的值还未判断，所以i不动
当arr[i]=v时，不做交换操作，i继续向右移动
循环完成后，lt到gt之间的值就不需要再排序了，然后将继续切分小于v的区间和大于v的区间即可
代码实现：
public class QuickSort3 {
private static Random random = new Random();
private static int rand(int l, int r){
return random.nextInt(r - l + 1);
}
/**
* 交换数组中两个元素的位置
*/
private static void swap(int[] arr, int x, int y){
if(x < 0 || y < 0 || x > arr.length || y > arr.length){
return;
}
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
/**
* 对ar[l...r]部分进行快速排序
*/
public static void quickSort(int[] arr, int l, int r){
if(l >= r){
return;
}
swap(arr, l, l + rand(l, r));
int v = arr[l];
int lt = l;
// 索引对应arr[l+1...lt) < v
int gt = r + 1;
// 索引对应arr[gt...r] > v
int i = l + 1;
// 索引对应arr[lt+1...i) = v 在初始情况下，这些区间都是空的，符合逻辑，首先假设有这样的数组空间了，
//随着lt、gt、i的变动以及交换位置，就可以把这三个区间确定下来
//当i移动到从右往左数 最后一个大于v的值的位置时，就不用循环了
while(i < gt){
if(arr[i] < v){
//当i索引的值小于v，就将其与lt+1的值调换位置，同时i继续往右移动，lt因为多了一个值，也要往右移动
//lt+1的值之前已经判断过了，因此不需要再处理，直接将i移动
swap(arr, i, lt + 1);
i++;
lt++;
}else if(arr[i] > v){
//当i索引的值大于v，就将其与gt-1的值调换位置，将大于v的值放到gt区间
//然后继续判断调换过来的值，因此i不用移动，gt因为多了一个值，所以要往左移动
swap(arr, i, gt - 1);
gt--;
}else{
i++;
}
}
//l对应的值就是v，lt对应的是最后一个小于v的值，交换后，v就放在了合适的位置，即v的左边小于v，右边大于等于v
swap(arr, l, lt);
//注意：这里返回p，之后，只是说满足arr[l+1...j] < v; arr[j+1...i) > v
//并不是说p的左边一定有数组，或者p的右边一定有数组，也可能是空
quickSort(arr, l, lt - 1);
//以p为中间点，再进行快速排序
quickSort(arr, gt, r);
}
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
quickSort(arr, 0, arr.length - 1);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}
优点：
不需要对大量等于v的元素重复操作，在包含大量相同元素时，三路排序最有效率
另外快速排序在 取出数组中第n大的元素这类问题效率很高，算法复杂度为O(n)，因为快速排序的过程每一次都是找到一个标定点，然后将标定点挪到数组中合适的位置，这个合适的位置就是数组排好序后最终所处的位置，所以第n大元素，就是第n个位置的元素
网友评论