算法思想
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
（2）快速排序的基本思想
设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
分解：
在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。
求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
组合：
因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
代码实现（Java）
public class QuickSort {
private Double[] source;
private int TYPE;
private Object result;
public QuickSort(Double[] source) { //Double类型构造
this.source = source;
result = source;
TYPE = 0;
}
public QuickSort(double[] source) { //double类型构造
this.source = new Double[source.length];
for (int i = 0; i < source.length; i++) {
this.source[i] = source[i];
}
result = source;
TYPE = 1;
}
public QuickSort(int[] source) { //int类型构造
this.source = new Double[source.length];
for (int i = 0; i < source.length; i++) {
this.source[i] = (double) source[i];
}
result = source;
TYPE = 2;
}
public void sort() {
if (source != null) {
sort(0, source.length - 1);
switch (TYPE) {
case 0:
break;
case 1:
{
for (int i = 0; i < source.length; i++) {
((double[]) result)[i] = source[i].doubleValue();
}
}
break;
case 2:
{
for (int i = 0; i < source.length; i++) {
((int[]) result)[i] = source[i].intValue();
}
}
break;
}
}
}
/**
* @param left : 左指针
* @param right : 右指针
* @category 递归排序
* */
private void sort(int left, int right) {
if (right <= left) return;
int l = left; //左边界
int r = right; //右边界
double base = source[left]; //参照数
boolean done = true; //上一轮是否进行了交换，这里定义，每进行一次定方向的比较查找 就算是一轮
while (left < right) {
//倒序
if (!done) break;
done = false;
for (int i = right; i > left; i--) {
if (source[i] < base) { //这里的base肯定指向 source[left]，不然不会进行到【倒序】
double t = source[left];
source[left] = source[i];
source[i] = t;
right = i;
done = true;
break;
}
}
//正序
if (!done) break;
done = false;
for (int i = left; i < right; i++) {
if (source[i] >= base) { //这里的base肯定指向 source[right]，不然不会进行到【正序】
double t = source[right];
source[right] = source[i];
source[i] = t;
left = i;
done = true;
break;
}
}
}
//递归
if (source[left] == base) {
sort(l, left - 1);
sort(left + 1, r);
} else {
sort(l, right - 1);
sort(right + 1, r);
}
}
}
测试代码
public class Test {
/**
* @author Wfei
*/
public static void main(String[] args) {
int[] source_int = new int[20];
Double[] sourceDou = new Double[20];
double[] source_dou = new double[20];
for (int i = 0; i < source_int.length; i++) {
int t = (int) (Math.random() * 20);
source_int[i] = t;
sourceDou[i] = (double) t;
source_dou[i] = (double) t;
}
long beginTime;
long endTime;
printData(source_int);
QuickSort quickSort = new QuickSort(source_int);
beginTime = new Date().getTime();
quickSort.sort();
endTime = new Date().getTime();
printData(source_int);
System.out.println("耗时 : " + (endTime - beginTime) + " 毫秒");
}
private static void printData(int[] source) {
for (int i = 0; i < source.length; i++) {
if (i % 10000 == 0) {
System.out.println("");
}
System.out.print(source[i] + " , ");
}
System.out.println("");
}
}
声明：以上实现，纯属个人初次学习《快速排序》思想所得，暂未参见其他前辈高明的实现算法思想，持续学习更新中！
引用：快速排序理论思想，请参见：http://www.cnblogs.com/foreverking/articles/2234225.html