首页 > 代码库 > 排序算法 - 快速排序(Quick Sort)
排序算法 - 快速排序(Quick Sort)
算法思想
快速排序是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）
1 public class QuickSort { 2 3 private Double[] source; 4 private int TYPE; 5 private Object result; 6 7 public QuickSort(Double[] source) { //Double类型构造 8 this.source = source; 9 result = source; 10 TYPE = 0; 11 } 12 public QuickSort(double[] source) { //double类型构造 13 this.source = new Double[source.length]; 14 for (int i = 0; i < source.length; i++) { 15 this.source[i] = source[i]; 16 } 17 result = source; 18 TYPE = 1; 19 } 20 public QuickSort(int[] source) { //int类型构造 21 this.source = new Double[source.length]; 22 for (int i = 0; i < source.length; i++) { 23 this.source[i] = (double) source[i]; 24 } 25 result = source; 26 TYPE = 2; 27 } 28 29 public void sort() { 30 if (source != null) { 31 sort(0, source.length - 1); 32 switch (TYPE) { 33 case 0: 34 break; 35 case 1: 36 { 37 for (int i = 0; i < source.length; i++) { 38 ((double[]) result)[i] = source[i].doubleValue(); 39 } 40 } 41 break; 42 case 2: 43 { 44 for (int i = 0; i < source.length; i++) { 45 ((int[]) result)[i] = source[i].intValue(); 46 } 47 } 48 break; 49 } 50 } 51 } 52 53 /** 54 * @param left : 左指针 55 * @param right : 右指针 56 * @category 递归排序 57 * */ 58 private void sort(int left, int right) { 59 if (right <= left) return; 60 int l = left; //左边界 61 int r = right; //右边界 62 double base = source[left]; //参照数 63 boolean done = true; //上一轮是否进行了交换，这里定义，每进行一次定方向的比较查找 就算是一轮 64 while (left < right) { 65 //倒序 66 if (!done) break; 67 done = false; 68 for (int i = right; i > left; i--) { 69 if (source[i] < base) { //这里的base肯定指向 source[left]，不然不会进行到【倒序】 70 double t = source[left]; 71 source[left] = source[i]; 72 source[i] = t; 73 right = i; 74 done = true; 75 break; 76 } 77 } 78 //正序 79 if (!done) break; 80 done = false; 81 for (int i = left; i < right; i++) { 82 if (source[i] >= base) { //这里的base肯定指向 source[right]，不然不会进行到【正序】 83 double t = source[right]; 84 source[right] = source[i]; 85 source[i] = t; 86 left = i; 87 done = true; 88 break; 89 } 90 } 91 } 92 //递归 93 if (source[left] == base) { 94 sort(l, left - 1); 95 sort(left + 1, r); 96 } else { 97 sort(l, right - 1); 98 sort(right + 1, r); 99 }100 }101 }
测试代码
1 public class Test { 2 3 /** 4 * @author Wfei 5 */ 6 public static void main(String[] args) { 7 int[] source_int = new int[20]; 8 Double[] sourceDou = new Double[20]; 9 double[] source_dou = new double[20];10 for (int i = 0; i < source_int.length; i++) {11 int t = (int) (Math.random() * 20);12 source_int[i] = t;13 sourceDou[i] = (double) t;14 source_dou[i] = (double) t;15 }16 long beginTime;17 long endTime;18 19 printData(source_int);20 QuickSort quickSort = new QuickSort(source_int);21 22 beginTime = new Date().getTime();23 quickSort.sort();24 endTime = new Date().getTime();25 26 printData(source_int);27 System.out.println("耗时 : " + (endTime - beginTime) + " 毫秒");28 }29 30 private static void printData(int[] source) {31 for (int i = 0; i < source.length; i++) {32 if (i % 10000 == 0) {33 System.out.println("");34 }35 System.out.print(source[i] + " , ");36 }37 System.out.println("");38 }39 }
声明：以上实现，纯属个人初次学习《快速排序》思想所得，暂未参见其他前辈高明的实现算法思想，持续学习更新中！
引用：快速排序理论思想，请参见：http://www.cnblogs.com/foreverking/articles/2234225.html
排序算法 - 快速排序(Quick Sort)