Posted on 2010-01-17 16:14
創(chuàng)意恒動力 閱讀(348)
評論(0) 編輯 收藏
快速排序介紹：
快速排序（Quicksort）是對冒泡法的一種改進(jìn)。由C. A. R. Hoare在1962年提出。
基本思想是：
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
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開始，從前往后掃描，如果發(fā)現(xiàn)大于a[R](數(shù)組最后一個(gè)值)，與之對換
14 while (j > 0) {
15 if (j <= i) {// 如果i == j結(jié)束跳出循環(huán)
16 break;
17 }
18 if (a[--j] < a[R]) {// 從J開始，從后往前掃描，如果發(fā)現(xiàn)小于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 + " ");//打印沒一趟排序結(jié)果
32 }
33 System.out.println();
34
35 //把數(shù)組分成兩段排序
36 sort(L, i-1);//基準(zhǔn)數(shù)前面的數(shù)據(jù)進(jìn)行排列
37 sort(i, R);//基準(zhǔn)數(shù)后面的數(shù)據(jù)排列
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