简介
快速排序是使用分治思想进行排序的一种方法,其平均效率较高,故被经常使用。一般来说,快速排序的平均算法复杂度是,最差情况下的算法复杂度为
。
基本思想
1.先从数列里取出一个数作为基准,一般取列表中的第一个数字
2.从数列首尾遍历,将比基准数大的数字放到其右边,将比基准数字小的数字放到左边
3.基准数字位置确定,在其左边区域和右边区域递归2中的操作,直到各区间只有一个数
基本代码
package quick.sort;
import edu.princeton.cs.algs4.StdRandom;
public class Quick {
private static int partition(Comparable[] a, int lo, int hi){
int i = lo, j = hi + 1;
while (true){
while (less(a[++i], a[lo]))
if (i == hi) break;
while(less(a[lo], a[--j]))
if(j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private static void sort(Comparable[] a, int lo, int hi){
if (lo >= hi) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
public static void sort(Comparable[] a){
// shuffle函数将数列中的数字顺序打乱,防止数列有序,增加算法复杂度
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
}
网友评论