看漫画学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進階架構師 的文章

關鍵字: Java 技术 编程语言

---