雞尾酒排序其實(shí)就是冒泡排序的變形，它的時(shí)間復(fù)雜度和冒泡排序一樣，都是O(n^2)，比快速排序要慢不少。

file

雞尾酒排序的思想有點(diǎn)像擺鐘一樣，從左到右，又從右到左。而冒泡排序只是單向執(zhí)行。

雞尾酒排序也是交換排序，假設(shè)做一個(gè)升序排序，先從左到右，交換一趟把最大的數(shù)放置右邊，然后從右到左，把最小的數(shù)放置左邊。

視頻動(dòng)畫

算法動(dòng)畫視頻 地址

Code

file

Result

初始狀態(tài) [5, 1, 9, 3, 7, 4, 8, 6, 2]
從左到右發(fā)生交換 [1, 5, 9, 3, 7, 4, 8, 6, 2]
從左到右發(fā)生交換 [1, 5, 3, 9, 7, 4, 8, 6, 2]
從左到右發(fā)生交換 [1, 5, 3, 7, 9, 4, 8, 6, 2]
從左到右發(fā)生交換 [1, 5, 3, 7, 4, 9, 8, 6, 2]
從左到右發(fā)生交換 [1, 5, 3, 7, 4, 8, 9, 6, 2]
從左到右發(fā)生交換 [1, 5, 3, 7, 4, 8, 6, 9, 2]
從左到右發(fā)生交換 [1, 5, 3, 7, 4, 8, 6, 2, 9]
從右到左發(fā)生交換 [1, 5, 3, 7, 4, 8, 2, 6, 9]
從右到左發(fā)生交換 [1, 5, 3, 7, 4, 2, 8, 6, 9]
從右到左發(fā)生交換 [1, 5, 3, 7, 2, 4, 8, 6, 9]
從右到左發(fā)生交換 [1, 5, 3, 2, 7, 4, 8, 6, 9]
從右到左發(fā)生交換 [1, 5, 2, 3, 7, 4, 8, 6, 9]
從右到左發(fā)生交換 [1, 2, 5, 3, 7, 4, 8, 6, 9]
從左到右發(fā)生交換 [1, 2, 3, 5, 7, 4, 8, 6, 9]
從左到右發(fā)生交換 [1, 2, 3, 5, 4, 7, 8, 6, 9]
從左到右發(fā)生交換 [1, 2, 3, 5, 4, 7, 6, 8, 9]
從右到左發(fā)生交換 [1, 2, 3, 5, 4, 6, 7, 8, 9]
從右到左發(fā)生交換 [1, 2, 3, 4, 5, 6, 7, 8, 9]

優(yōu)化 減少不必要的交換

看了前面冒泡排序和快速排序，我相信優(yōu)化是一項(xiàng)學(xué)習(xí)的重點(diǎn)，以后面試中可以把這項(xiàng)說說來，展示出你的實(shí)力。

這次我們就優(yōu)化不必要的交換次數(shù)，come on！

我么通過移除swap函數(shù)的調(diào)用，從而讓程序運(yùn)行的更快一點(diǎn)。每次進(jìn)行符合條件判斷時(shí)，不做交換，讓最大或者最小的數(shù)據(jù)做一個(gè)標(biāo)記，待全部比較完之后，才進(jìn)行做交換。

視頻動(dòng)畫

算法動(dòng)畫視頻 地址

Code

file

Result

初始狀態(tài) [5, 1, 9, 3, 7, 4, 8, 6, 2]
從左到右發(fā)生交換 [5, 1, 2, 3, 7, 4, 8, 6, 9]
從右到左發(fā)生交換 [1, 5, 2, 3, 7, 4, 8, 6, 9]
從左到右發(fā)生交換 [1, 5, 2, 3, 7, 4, 6, 8, 9]
從右到左發(fā)生交換 [1, 2, 5, 3, 7, 4, 6, 8, 9]
從左到右發(fā)生交換 [1, 2, 5, 3, 6, 4, 7, 8, 9]
從右到左發(fā)生交換 [1, 2, 3, 5, 6, 4, 7, 8, 9]
從左到右發(fā)生交換 [1, 2, 3, 5, 4, 6, 7, 8, 9]
從右到左發(fā)生交換 [1, 2, 3, 4, 5, 6, 7, 8, 9]

長按下圖二維碼關(guān)注公眾號，「算法無遺策」持續(xù)更新算法

file