Posted on 2010-01-17 16:14
创意恒动力 阅读(338)
评论(0) 编辑 收藏
快速排序介绍：
快速排序（Quicksort）是对冒泡法的一种改进。由C. A. R. Hoare在1962年提出。
基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1 package my.sort;
2
3 public class QuickSort {
4
5 static int a[] = { 10, 11, 13, 1, 64, 32, 54, 5, 6 };
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