Posted on 2010-01-17 16:14
創意恒動力 閱讀(348)
評論(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