1，经典快排
经典快排就是将序列中比尾元素小的移动到序列左边，比尾元素大的移动到序列右边，对以该元素为界的左右两个子序列（均不包括该元素）重复此操作
首先我们要考虑的是对给定的一个数，如何将序列中比该数小的移动到左边，比该数大的移动到右边。
准备一个less 指针 代表小于尾元素的区域 less指向arr[-1]
准备一个cur指针 代表当前元素
循环数组 如何当前元素比尾元素小，那么arr[++less]和arr[cur]交换 cur++寻找下一个元素
当前元素大于等于尾元素则cur++
经典排序的时间复杂度与数据状况有关，如果每一次partition时，尾元素都是序列中最大或最小的，那么去除该元素序列并未如我们划分为样本量相同的左右两个子序列，而是只安排好了一个元素（就是去掉的那个元素），这样的话时间复杂度就是O(n-1+n-2+……+1)=O(n^2)；但如果每一次partition时，都将序列分成了两个样本量相差无几的左右两个子序列，那么时间复杂度就是O(nlogn)（使用Master公式求解）。
package mySort;
public class QuickSort {
public static void quickSort(int[] arr){
if(arr==null||arr.length<2){
return ;
}
quickSort(arr,0,arr.length-1);
}
private static void quickSort(int[] arr, int l, int r) {
if(l<r){
// swap(arr, l + (int) (Math.random() * (r - l + 1)), r); //随机性
int[] p= partition(arr,l,r);
quickSort(arr,l,p[0]-1);
quickSort(arr,p[1]+1,r);
}
}
public static int[] partition(int arr[],int l,int r){
//由荷兰国旗问题改进过的快排问题
// int less=l-1;
// int more=r;
// int cur=l;
// while(cur<more){
//
// if(arr[cur]<arr[r]){
// swap(arr,++less,cur++);
// }
// else if(arr[cur]==arr[r]){
//
// cur++;
// }
// else{
//
// swap(arr,--more,cur);
// }
//
// }
// swap(arr,r,more);
//
// return new int[]{less+1,more};
//未改进的经典快排
int less=l-1;
int cur=l;
while(cur<arr.length-1){
if(arr[cur]<arr[r]){
swap(arr,++less,cur++);
}
cur++;
}
swap(arr,less+1,r);
return new int[]{less+1,less+1};
}
public static void swap(int[]arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[]generateArray(){
int[] arr=new int[10];
for(int i=0;i<arr.length;i++){
arr[i]=(int)(Math.random()*20);
}
return arr;
}
public static void printArray(int[] arr){
if(arr==null){
return ;
}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String args[]){
int[] test = generateArray();
printArray(test);
quickSort(test);
printArray(test);
}
}
2，由荷兰国旗问题引发对经典快排的改进
比较一下经典排序和使用荷兰国旗问题改进后的经典排序，不难发现，后者一次partition能去除一个以上的元素（等于arr[r]的区域），而前者每次partition只能去除一个元素，这里的去除相当于安排（排序）好了对应元素的位置。因此后者比经典排序更优，但是优化不大，只是常数时间内的优化，实质上的效率还是要看数据状况
代码
public class QuickSort {
public static void quickSort(int[] arr){
if(arr==null||arr.length<2){
return ;
}
quickSort(arr,0,arr.length-1);
}
private static void quickSort(int[] arr, int l, int r) {
if(l<r){
// swap(arr, l + (int) (Math.random() * (r - l + 1)), r); //随机性
int[] p= partition(arr,l,r);
quickSort(arr,l,p[0]-1);
quickSort(arr,p[1]+1,r);
}
}
public static int[] partition(int arr[],int l,int r){
int less=l-1;
int more=r;
int cur=l;
while(cur<more){
if(arr[cur]<arr[r]){
swap(arr,++less,cur++);
}
else if(arr[cur]==arr[r]){
cur++;
}
else{
swap(arr,--more,cur);
}
}
swap(arr,r,more);
return new int[]{less+1,more};
}
public static void swap(int[]arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[]generateArray(){
int[] arr=new int[10];
for(int i=0;i<arr.length;i++){
arr[i]=(int)(Math.random()*20);
}
return arr;
}
public static void printArray(int[] arr){
if(arr==null){
return ;
}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String args[]){
int[] test = generateArray();
printArray(test);
quickSort(test);
printArray(test);
}
}
网友评论