看漫畫學java：什麼是雞尾酒排序？

在上一篇漫畫中，小灰介紹了冒泡排序的思路和幾種變化：

漫畫：什麼是冒泡排序？

那麼，雞尾酒排序又是何方神聖呢？我們這一期將會詳細講述。

讓我們首先來回顧一下冒泡排序的思想：

冒泡排序的每一個元素都可以像小氣泡一樣，根據自身大小，一點一點向著數組的一側移動。算法的每一輪從都是從左到右比較元素，進行單向的位置交換。

那麼雞尾酒排序做了怎樣的優化呢？

雞尾酒排序的元素比較和交換過程是雙向的。

讓我們來舉一個栗子：

有8個數組成一個無序數列：2，3，4，5，6，7，8，1，希望從小到大排序。

如果按照冒泡排序的思想，排序的過程是什麼樣呢？

第一輪結果（8和1交換）

第二輪結果（7和1交換）

第三輪結果（6和1交換）

第四輪結果（5和1交換）

第五輪結果（4和1交換）

第六輪結果（3和1交換）

第七輪結果（2和1交換）

雞尾酒排序是什麼樣子呢？讓我們來看一看詳細過程：

第一輪（和冒泡排序一樣，8和1交換）

第二輪

此時開始不一樣了，我們反過來從右往左

比較和交換：

8已經處於有序區，我們忽略掉8，讓1和7比較。元素1小於7，所以1和7交換位置：

接下來1和6比較，元素1小於6，所以1和6交換位置：

接下來1和5比較，元素1小於5，所以1和5交換位置：

接下來1和4交換，1和3交換，1和2交換，最終成為了下面的結果：

第三輪（雖然已經有序，但是流程並沒有結束）

雞尾酒排序的第三輪，需要重新從左向右比較和交換：

1和2比較，位置不變；2和3比較，位置不變；3和4比較，位置不變......6和7比較，位置不變。

沒有元素位置交換，證明已經有序，排序結束。

這就是雞尾酒排序的思路。排序過程就像鐘擺一樣，第一輪從左到右，第二輪從右到左，第三輪再從左到右......

public class CockTailSort {

1. private
3. static
5. void
6. sort(
7. int
8. array[])
9. {
10. int tmp = 0;
12. for
13. (
14. int
15. i=
16. 0
17. ; i
18. 2
19. -1; i++)
20. {
22. //有序標記，每一輪的初始是true
24. boolean
25. isSorted =
26. true
27. ;
29. //奇數輪，從左向右比較和交換
31. for
32. (
33. int
34. j=i; j
36. ; j++)
37. {
39. if
40. (array[j] > array[j+
41. 1
42. ])
43. {
44. tmp = array[j];
45. array[j] = array[j+
46. 1
47. ];
48. array[j+
49. 1
50. ] = tmp;
52. //有元素交換，所以不是有序，標記變為false
53. isSorted =
54. false
55. ;
56. }
57. }
59. if
60. (isSorted){
62. break
63. ;
64. }
66. //偶數輪，從右向左比較和交換
68. for
69. (
70. int
71. j=array.length-i-
72. 1
73. ; j>i; j--)
74. {
76. if
77. (array[j] < array[j-
78. 1
79. ])
80. {
81. tmp = array[j];
82. array[j] = array[j-
83. 1
84. ];
85. array[j-
86. 1
87. ] = tmp;
89. //有元素交換，所以不是有序，標記變為false
90. isSorted =
91. false
92. ;
93. }
94. }
96. if
97. (isSorted){
99. break
100. ;
101. }
102. }
103. }
104. public
106. static
108. void
109. main(
110. String
111. [] args){
113. int
114. [] array =
115. new
117. int
118. []{
119. 2
120. ,
121. 3
122. ,
123. 4
124. ,
125. 5
126. ,
127. 6
128. ,
129. 7
130. ,
131. 8
132. ,
133. 1
134. };
135. sort(array);
137. System
138. .
139. out
140. .println(
141. Arrays
142. .toString(array));
143. }

}

這段代碼是雞尾酒排序的原始實現。代碼外層的大循環控制著所有排序回合，大循環內包含兩個小循環，第一個循環從左向右比較並交換元素，第二個循環從右向左比較並交換元素。

讓我們來回顧一下冒牌排序針對有序區的優化思路：

原始的冒泡排序，有序區的長度和排序的輪數是相等的。比如第一輪排序過後的有序區長度是1，第二輪排序過後的有序區長度是2 ......

要想優化，我們可以在每一輪排序的最後，記錄下最後一次元素交換的位置，那個位置也就是無序數列的邊界，再往後就是有序區了。

對於單向的冒泡排序，我們需要設置一個邊界值，對於雙向的雞尾酒排序，我們需要設置兩個邊界值。請看代碼：

public class CockTailSort {

1. private
3. static
5. void
6. sort
7. (
8. int
9. array
10. [])
11. {
13. int
14. tmp
15. =
17. 0
18. ;
20. //記錄右側最後一次交換的位置
22. int
23. lastRightExchangeIndex
24. =
26. 0
27. ;
29. //記錄左側最後一次交換的位置
31. int
32. lastLeftExchangeIndex
33. =
35. 0
36. ;
38. //無序數列的右邊界，每次比較只需要比到這裡為止
40. int
41. rightSortBorder
42. =
43. array
44. .
45. length
46. -
48. 1
49. ;
51. //無序數列的左邊界，每次比較只需要比到這裡為止
53. int
54. leftSortBorder
55. =
57. 0
58. ;
60. for
61. (
62. int
63. i
64. =
65. 0
66. ;
67. i
68. <
69. array
70. .
71. length
72. /
73. 2
74. ;
75. i
76. ++)
78. {
80. //有序標記，每一輪的初始是true
82. boolean
83. isSorted
84. =
86. true
87. ;
89. //奇數輪，從左向右比較和交換
91. for
92. (
93. int
94. j
95. =
96. leftSortBorder
97. ;
98. j
99. <
100. rightSortBorder
101. ;
102. j
103. ++)
105. {
107. if
108. (
109. array
110. [
111. j
112. ]
114. >
115. array
116. [
117. j
118. +
119. 1
120. ])
122. {
123. tmp
124. =
125. array
126. [
127. j
128. ];
129. array
130. [
131. j
132. ]
134. =
135. array
136. [
137. j
138. +
139. 1
140. ];
141. array
142. [
143. j
144. +
145. 1
146. ]
148. =
149. tmp
150. ;
152. //有元素交換，所以不是有序，標記變為false
153. isSorted
154. =
156. false
157. ;
158. lastRightExchangeIndex
159. =
160. j
161. ;
163. }
165. }
166. rightSortBorder
167. =
168. lastRightExchangeIndex
169. ;
171. if
172. (
173. isSorted
174. ){
176. break
177. ;
179. }
181. //偶數輪，從右向左比較和交換
183. for
184. (
185. int
186. j
187. =
188. rightSortBorder
189. ;
190. j
191. >
192. leftSortBorder
193. ;
194. j
195. --)
197. {
199. if
200. (
201. array
202. [
203. j
204. ]
206. <
207. array
208. [
209. j
210. -
211. 1
212. ])
214. {
215. tmp
216. =
217. array
218. [
219. j
220. ];
221. array
222. [
223. j
224. ]
226. =
227. array
228. [
229. j
230. -
231. 1
232. ];
233. array
234. [
235. j
236. -
237. 1
238. ]
240. =
241. tmp
242. ;
244. //有元素交換，所以不是有序，標記變為false
245. isSorted
246. =
248. false
249. ;
250. lastLeftExchangeIndex
251. =
252. j
253. ;
255. }
257. }
258. leftSortBorder
259. =
260. lastLeftExchangeIndex
261. ;
263. if
264. (
265. isSorted
266. ){
268. break
269. ;
271. }
273. }
274. }
275. public
277. static
279. void
280. main
281. (
282. String
283. []
284. args
285. ){
287. int
288. []
289. array
290. =
292. new
294. int
295. []{
296. 2
297. ,
298. 3
299. ,
300. 4
301. ,
302. 5
303. ,
304. 6
305. ,
306. 7
307. ,
308. 8
309. ,
310. 1
311. };
312. sort
313. (
314. array
315. );
317. System
318. .
319. out
320. .
321. println
322. (
323. Arrays
324. .
325. toString
326. (
327. array
328. ));
329. }

}

代碼中使用了左右兩個邊界值，rightSortBorder 代表右邊界，leftSortBorder代表左邊界。

在比較和交換元素時，奇數輪從 leftSortBorder 遍歷到 rightSortBorder 位置，偶數輪從 rightSortBorder 遍歷到 leftSortBorder 位置。

—————END—————

---

分享到:

---

閱讀更多 java進階架構師 的文章

關鍵字: 雞尾酒 排序 漫畫

---