快速排序应用广泛。长度为N的数组和运行时间成正比NlogN
快速排序思想
快速排序是一种分治排序的思想。它讲一个数组分成两个子数组，将两部分独立排序
package com.snail.basic;
public class Quick
{
public static void sort(Comparable[] a){
// 将数组打乱 StdRandom.shuffle(a)
sort(a,0,a.length-1);
}
public static void sort(Comparable[] a, int low, int high){
if(high<=low) return;
int j = partnation(a,low,high);
sort(a,low,j-1);
sort(a,j+1,high);
}
public static int partnation(Comparable[] a,int low,int high){
int i = low;
int j = high;
Comparable v = a[low];
while (true){
// 找出比他小的
while (less(a[++i],v)){
if(i == high) break;
}
// 找出比他大的
while (less(v,a[--j])){
if(j == low) break;
}
if(i>=j) break;
exch(a,i,j);
}
// 请注意这个步骤
exch(a,low,j);
return j;
}
public static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
public static void exch(Comparable[] a,int i,int j){
Comparable t = a[i];
a[j]=a[i];
a[i]=t;
}
}
partition 让数组具备三个条件
- 对于某个j，a[j]是已经排定的
- a[0]~a[j] 之间的元素小于a[j],
- a[j]~a[a.length-1]之间的元素都大于a[j]
