posts - 12, comments - 3, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2010年1月17日

快速排序介绍:
快速排序(Quicksort)是对冒泡法的一种改进。由C. A. R. Hoare在1962年提出。

基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

 1 package my.sort;
 2 
 3 public class QuickSort {
 4 
 5     static int a[] = { 101113164325456 };
 6 
 7     public static void sort(int L, int R) {
 8         int i = L - 1;
 9         int j = R;
10         int tmp;
11         if (L < R) {
12             for (; i < R;) {
13                 while (a[++i] > a[R]) {// 从i开始,从前往后扫描,如果发现大于a[R](数组最后一个值),与之对换
14                     while (j > 0) {
15                         if (j <= i) {// 如果i == j结束跳出循环
16                             break;
17                         }
18                         if (a[--j] < a[R]) {// 从J开始,从后往前扫描,如果发现小于a[i],与之对换
19                             tmp = a[j];
20                             a[j] = a[i];
21                             a[i] = tmp;
22                         }
23                         
24                     }
25                     
26                     tmp = a[i];
27                     a[i] = a[R];
28                     a[R] = tmp;
29                     
30                     for(int b : a) {
31                         System.out.print(b + " ");//打印没一趟排序结果
32                     }
33                     System.out.println();
34                     
35                     //把数组分成两段排序
36                     sort(L, i-1);//基准数前面的数据进行排列
37                     sort(i, R);//基准数后面的数据排列
38                 }
39             }
40         }
41 
42     }
43 
44     public static void main(String[] args) {
45         System.out.println("排序前:");
46         for (int b : a) {
47             System.out.print(b + " ");
48         }
49         System.out.println("\n排序过程:");
50         sort(0, a.length - 1);
51         System.out.println("排序后:");
52         for (int b : a) {
53             System.out.print(b + " ");
54         }
55         System.out.println();
56     }
57 }
58 

posted @ 2010-01-17 16:14 创意恒动力 阅读(330) | 评论 (0)编辑 收藏