快速排序
快速排序和归并排序有点像，快速排序将一个数组分成两个子数组，将两部分独立排序，，而且通过迭代的方式不断进行切分和排序最终实现有序数组。切分的位置取决于数组内容。
切分排序的具体实现步骤如下：先选定一个元素a(选定第一个元素)，然后从数组从左往右遍历找打一个小于a的元素，和数组从右往左的一个大于a的元素，交换他们的位置，最后两个数组指针相遇时就将元素a移动过去。
public class Quicksort {
public static void sort(int []a) {
sort(a,0,a.length-1);
}
private static void sort(int [] a,int low,int high) {
if(high<=low) return;
int j=partition(a,low,high);
sort(a, low, j-1);
sort(a, j+1, high);
}
private static int partition(int []a,int low ,int high) {
int i=low;
int j=high+1;
int v=a[low];
while(true) {
//从左往右或从右往左遍历找到当前第一个比v小的元素和比v大的元素
while(a[++i]<v) if(i==high) break;
while(v<a[--j]) if(j==low) break;
if(i>=j) { break;} //如果是指针相遇过就退出循环
exchange(a, i, j); //交换比v大和小元素的位置
}
exchange(a, low, j);
return j;
}
private static void exchange(int []a,int i,int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
反正完成一次sort就是要达成a[low...j-1]<=a[j]<=a[j+1...high]
很神奇的它竟然连长度为2的数组特例都包含的，真的很妙。
快速排序的复杂读是不稳定的，最快的复杂度O(nlogn)，最慢O(n^2)，平均复杂度O(nlogn)
而有时候为了避免出现坏情况，而且让运行时间可预计，往往会将数组进行随机性打乱
这个快排其实有几种改进的思路可以参考一下
结合插入排序
对于小数组插入排序比快速排序快
所以我们递归到一定程度 使得子数组长度小到一定程度时可适用插入排序将子数组进行排序
if(high<=low+M) {Insertion.sort(a,low,high); return;}
三取样排序
使用子数列的一小部分的元素的中位数来切分数组。但代价是要计算中位数，人们发现将取样大小设置为3并用大小居中的元素切分数组的效果最好
三向切分排序
三向切分快速排序是对快速排序算法改进，特别适用于有大量重复元素的数组的排序（比归并排序还快），其时间复杂度介于N - NlogN之间，在没有重复元素的情况下有最坏的时间复杂度。
public class Quickthreewaysort {
public static void sort(int []a) {
sort(a,0,a.length-1);
}
private static void sort(int []a,int low,int high) {
if(high<=low) return;
int lt=low,i=low+1,gt=high;
int v=a[low];
while(i<=gt) {
if(a[i]<v) exchange(a, lt++, i++); //将元素丢到It的左侧，所以lt要++
else if(a[i]>v) exchange(a, i, gt--); //将元素丢到gt的右侧，这里i不能增，因为gt位置过来元素不知道它和v的关系
else i++; //发现元素和v相等，直接i++探访下一个元素，让该元素夹在lt和i中间就行
}
sort(a, low, lt-1);
sort(a, gt+1, high);
}
private static void exchange(int []a,int i,int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
我们有请灵魂画手
三向切分示意图.png
其实lt i gt可以说是三个指针，而他们的存在是代表着三个种元素的分界线 小于等于大于v这三种元素。而所谓的三向切分只不过是将元素分成三类而已
lt永远是指着元素值为v的元素
最后 a[low..lt-1]<a[lt..gt]=v<a[gt+1..high]
网友评论