快速排序讓我看了很久，也折磨了我很長時間，因為大體上的思路我是有了，但是寫代碼時總是出現各種問題，要想把它調試出來對我個人來說還是有一定難度的，而且因為工作和偷懶的原因，導致之前調試不出來的錯誤放了很久，今天終于出來啦，還是有些小激動的哦，下面來分享一下我的代碼并做一點點說明。
要學會快速排序，就必須先要學會分治法，分治的思想是給一串亂序的數字（數字是假設，也可以是其他的對象，當然方法的參數可以自己定義哦，我在這里假設有一個整型的數組吧）然后給他一個中間數，分治法會把這些數字以給他的那個是中間數為分界分為兩部分，一部分在中間數的左邊，另一部分在右邊，以這個數為分界點，兩邊的數現在還是亂序的，我給他定義的方法如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
//left是數組的想分治部分的左端點，right是數組分治部分的總端點，如長度為10的數組，我想對前5個整數進行分治，則傳0，4即可 public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right>n-1){ return -1; } int temp = test[left]; int j=right; int i=left; while(i<j){ while(test[j]>=test[left]&&i<j){ j--; } while(test[i]<=test[left]&&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; } } if(i==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } for(int m=0;m<n;m++){ System.out.print(test[m]+" "); } return i; } |
當然，也可以把那個中間數當參數傳進來，現在我只是單純的以數組的傳進來的第left數做為分界數，這只是為了說明。
明白了分治，那么快速排序也就簡單了，那就是對已經分為兩部分的數再進行分治，依次類推，直到全部的數字都有序為止，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public void quickSort(int left,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhi(left, right); System.out.println(point); //if(point!=left&&point!=right){ quickSort(left,point-1); quickSort(point+1,right); //} } } |
快速排序的效率在眾多的排序算法中是很優秀的，時間復雜度為O(N*log2n),但是如果分治的分界點選的不好的話，時間復雜度將會降到（n的平方）,因為如果正好這個數組是有序的，然后我們每次都取傳過來的最左端的數，那么效率就會很低，所以要避免發生這種情況，如果檢測所有的選項，那么將會很花時間，所以一個折中的辦法 ，就是把最左端的數和最右端的數加上一個中間的數，找到他們三個中間的數，以這個為分界值就會變的好一點，在上面方法的基礎上，修改以后的代碼如下，但是我做完了以后這樣的做法不是很好，應該把分界值也當做傳給分治的方法會好些，細心的朋友可以自己試一下，我在這里就不試了哈，大體上是一樣的哦！
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
package com.jll;public class FenZhi { int[] test; int n=10; public FenZhi(){ test = new int[10]; for(int i=0;i<n;i++){ test[i]=(int)(Math.random()*100)+1; System.out.print(test[i]+" "); } System.out.println(); } public FenZhi(int n){ if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){ test[i]=(int)(Math.random()*100)+1; } } } public int signalFenZhiMajorizationFirst(int left,int right){ if(left<0||left>n-1||right<0||right>n-1||left>=right){ return -1; } if(right-left>=2){ int middle = (right+left)/2; if(test[left]>test[middle]){ int temp = test[middle]; test[middle] = test[left]; test[left] = temp; } if(test[left]>test[right]){ int temp = test[left]; test[left] = test[right]; test[right] = temp; } if(test[middle]>test[right]){ int temp = test[middle]; test[middle] = test[right]; test[right] = temp; } int temp = test[middle]; test[middle] = test[left]; test[left] = temp; int j=right-1; int i=left+1; while(i<j){ while(test[j]>=test[left]&&i<j){ j--; } while(test[i]<=test[left]&&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; } } if(i==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } /*if(i==j){ temp = test[middle]; test[middle]=test[i]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" "); }*/ return i; }else { if(test[right]<test[left]){ int temp = test[right]; test[right] = test[left]; test[left] = temp; } return right; } } public void quickSortMajorizationFirst(int left,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhiMajorizationFirst(left, right); System.out.println("the point is:"+point); quickSortMajorizationFirst(left,point-1); quickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out.println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,f.n-1); //f.quickSort(0,f.test.length-1); for(int i:f.test){ System.out.print(i+" "); } }} |
代碼運行如下：
|
1
2
3
4
5
6
7
8
9
10
|
95 40 64 18 78 23 73 84 40 the point is:4the point is:1the point is:3the point is:7the point is:6the point is:918 23 40 40 64 73 78 84 95 |
以上就是我學習到的東西，記錄一下，以備后面查閱。
