快速排序原理:
循环一趟,将待排序的数组分为两部分,其中一部分的值小于另一部分;然后继续对这两部分进行排序,以达到整个序列有序的目的;
class QuickSort {
public static void main(String[] argv){
int[] arr = {50,10,90,30,70,40,80,60,20};
System.out.println("排序前...");
for(int i=0;i<arr.length;i++) {
System.out.println(arr[i]);
}
sort(arr,0,arr.length-1);
System.out.println("排序后...");
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
//分割数组
public static int position(int[] arr, int low, int high){
//哨兵值(此值很关键,决定整个排序的复杂度)
int targetValue = arr[low];
while(low < high){
// 从右向左比较
while(low<high&&arr[high]>=targetValue){
high--;
}
//将low与high对应的值交换
if(arr[high]<targetValue)
int tmp = arr[high];
arr[high]=arr[low];
arr[low] = tmp;
}
// 从左向右比较
while(low<high&&arr[low]<=targetValue){
low++;
}
//交换low与high对应的值
if(arr[low]>targetValue){
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
}
}
//返回low=4
return low;
}
//递归比较各部分
public static void sort(int[] arr, int low, int high){
if (low < high) {
int p = position(arr,low,high);
sort(arr, low, p-1);
sort(arr, p+1, high);
}
}
}
分析:(只进行了一次循环的分析,其他类似)
第一轮:(50,10,90,30,70,40,80,60,20)
low=0,high=8, low
targetValue = 50
arr[high]=20<50
20<50,while循环不走,high=8,low=0
arr[high]=20 < 50
执行if内容
交换low与high的值
至此数组变更为:20,10,90,30,70,40,80,60,50
low=0,high=8,low<high
arr[low]=20<50
进入while循环low++
low=1,high=8,low
arr[low]=10<50
进入while循环low++
low=2,high=8,low
arr[low]=90>50
跳出循环,low=2,high=8
arr[low]=90 > 50
执行if块
至此数组变更为:20,10,50,30,70,40,80,60,90
第二轮:
low=2,high=8, low<high
arr[high]=90>50
进入到while循环high--
low=2,high=7, low
arr[high]=60>50
进入while循环high--
low=2,high=6,low
arr[high]=80>50
进行while循环high--
low=2,high=5,low
arr[high]=40 < 50
跳出while循环,high= 5,low = 2
arr[high]=40<50
进入到if块
交换low与high的值
至此数组变更为:20,10,40,30,70,50,80,60,90
low=2,high=5,low<high
arr[low]=40<50
进入到while循环low++
low=3,high=5,low
arr[low]=30<50
进入到while循环low++
low=4,high=5,low
arr[low]=70>50
跳出循环,low=4,high=5
arr[low]=70 > 50
执行if块
至此数组变更为:20,10,40,30,50,70,80,60,90
第三轮:(20,10,40,30,50,70,80,60,90)
low=4,high=5,low
arr[high]= 70>50
进入while循环,high--
low=4,high=4,low==high不执行while继续向下
由于low==high所以整个外出while会跳出,返回4(一轮比较后)
下标为4的全部小与50,下标大与40的全部大于50
然后再用同样的方法对分割的两个数组进行排序...以此类推
说明:
在最优的情况下,快排的时间复杂度为O(nlogn)
在最坏的情况下,快排的时间复杂度为O(n²)
平均数量级为O(nlogn)
快排最重要的是哨兵值的位置,若正好在中间,则平衡,性能最好,若哨兵值要么最大,要么最小,那么其会出现偏树,导致性能差;通常的优化方法是哨兵值通过三数取中来实现,一般取最左端、右端和中间三个数;将哨兵值设置为三个数的中间值
网友评论