疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

排序算法 - 快速排序(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 }