算法思想

　快速排序是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.survivalescaperooms.com/foreverking/articles/2234225.html