(1) 分治法的基本思想
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题,然后递归地解这些子问题,最后将这些子问题的解组合为原问题的解。
(2)快速排序的基本思想
设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
1)分解:
在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
注意,划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high
2)求解:
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
3)组合:
因为当“求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,“组合”步骤无须做什么,可看作是空操作。
public class Test { private static int[] R; public void quickSort(int low, int high) { int middle; if(low < high){ //对R[low..high]做划分,得到基准记录的位置 middle = partion(low, high); //对左区间递归排序 quickSort(low, middle - 1); //对右区间递归排序 quickSort(middle + 1, high); } } private int partion(int low, int high){ int pivot = R[low]; int i = low; int j = high + 1; while(true){ //从左向右扫描,查找第1个关键字大于pivot.key的记录R[i] while(i < high && R[--j] > pivot); //从右向左扫描,查找第1个关键字小于pivot.key的记录R[j] while(j > low && R[++i] < pivot); //如果左边记录大于右边的,则结束 if(i >= j) break; //交换左右记录 swap(i, j); } //将j与low的记录交换 swap(low, j); return j; } //交换数据 private void swap(int i, int j){ int temp; temp = R[i]; R[i] = R[j]; R[j] = temp; } public static void main(String[] args) { R = new int[]{8, 32, 11, 3, 22, 4, 87, 99}; Test t = new Test(); t.quickSort(0, 7); for(int x : R){ System.out.print(x+" "); } } }
在JDK7 中新增了java.util.DualPivotQuicksort这个类,里面实现于2009年发表的Dual-Pivot Quicksort 算法。其主要的设计是改进了Quicksort算法,使之效率大幅提高。Collections.sort()、Arrays.sort()等的实现部分使用了这个类。