排序算法

算法思想

　快速排序是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 }

View Code

测试代码

 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