快速排序是使用的最广得排序算法.优点:简单,适用于不同的输入数据,在一般应用中比排序算法快.
是一种原地排序(只需要一个很小的辅助栈),排序时间与N 数组成NLgN成正比.而且内循环比大多数算法都要少.
快速排序是一种分治的排序算法.把数组一分为二,然后分别对两半进行排序.只有一分为二,时间复杂度才有可能 达到lgN→log2N.
具体算法过程:
- 1.查找一个拆分点K,使得把整个数组分成两块.左边都小于K,右边值都大于等于K
- 2.对左边,右边分别排序.
问题:
如何找中轴?
通常把第一个数作为中轴,目的是要把第一个数排序到中间位置,使得 左边的数都小于它,右边的数都大于它.
2018-04-07 20-01-49 的屏幕截图.png
2018-04-07 20-02-25
的屏幕截图.png
拆分中轴的算法如下:
public class QuikSort{
public void sort(int [] arr,int low,int high){
if(arr==null||arr.length==0){
return;
}
int mid=partion(arr,0,arr.length-1);
sort(arr,0,mid-1);
sort(arr,mid+1,high);
}
private int partition(int[] arr,int low,int high){
while(low<high){
while(low<high&&arr[high]>arr[low]){
high--;
}
if(low<high){
swap(arr,low,high);
low++;
}
while(low<high&&arr[low]<arr[high]){
low++;
}
if(low<high){
swap(arr,low,high);
high--;
}
}
}
private void swap(int [] a,int left,int right){
a[left]^=a[right];
a[right]^=a[left];
a[left]^=a[right];
}
}
性能分析
命题K:
将长度为N的无重复数组排序,快速排序的平均需要 2NlnN次比较,(1/6的交换).在实际数组中元素重复,精确的分析会十分复杂,但是在重复的元素,其平均比较次数不会大于CN.
尽管快速排序有众多优点,但是有些潜在的缺点:
-
1.切分不平衡是效率会极低
命题:
快速排序最多需要N2/2次比较,但是随机打乱数组能预防这种情况.
经过测试,
对于5000000个整数的排序 时间平均在 800~900毫秒之内..速度惊人.
几十万级别排序在几十毫秒级别
-
2.对于小数组,改用插入排序.
因为递归,小数组在快速排序中也会递归调用自己.对于设置这个常数 一般在5-15 之间.
-
3.对于元素重复率高的时候,三取样切分/熵最优的排序
例如一个全部是重复元素的子数组不需要排序,但我们的普通算法还是会将他继续切分成更小的数组排序,这里面就有改进的空间.
