什么是雞尾酒排序？
在上(shang)一篇漫畫中，小灰介紹(shao)了冒泡排序的思路和幾種變化：
漫畫：什(shen)么是冒泡排序？
那么，雞尾(wei)酒排序(xu)又是何(he)方神圣呢？我(wo)們這一期將會詳細講述。
讓我們首(shou)先(xian)來回(hui)顧一下冒泡排序的思想：
冒泡排序的每一個元素都可以像小氣泡一樣，根據自身大小，一點一點向著數組的一側移動。算法的每一輪從都是從左到右比較元素，進行單向的位置交換。
那么雞尾酒排序做(zuo)了怎樣(yang)的優化(hua)呢？
雞尾酒排序的元素比較和交換過程是雙向的。
讓(rang)我們來舉(ju)一(yi)個栗子(zi)：
有8個(ge)(ge)數組成一個(ge)(ge)無序(xu)(xu)數列：2，3，4，5，6，7，8，1，希望(wang)從小到大排(pai)序(xu)(xu)。
如果(guo)按照冒泡排序的思想，排序的過程是什么樣(yang)呢(ni)？
第一輪結果（8和1交換）
第二輪結果（7和1交換）
第三輪結果（6和1交換）
第四輪結果（5和1交換）
第五輪結果（4和1交換）
第六輪結果（3和1交換）
第七輪結果（2和1交換）
雞尾酒排(pai)序是什么樣子呢？讓我們來看一(yi)看詳細(xi)過程：
第一輪（和冒泡排序一樣，8和1交換）
第二輪
此時開始不一樣了，我們反過來從右往左比較和交換：
8已經處于(yu)有序區，我(wo)們忽略(lve)掉8，讓1和(he)7比較。元(yuan)素1小(xiao)于(yu)7，所以1和(he)7交換(huan)位置：
接下(xia)來1和(he)(he)6比較(jiao)，元素1小于6，所以1和(he)(he)6交換(huan)位(wei)置：
接下來1和5比較，元素(su)1小于5，所以1和5交換位置：
接下(xia)來1和4交(jiao)換，1和3交(jiao)換，1和2交(jiao)換，最(zui)終成(cheng)為(wei)了下(xia)面的結(jie)果：
第三輪（雖然已經有序，但是流程并沒有結束）
雞(ji)尾(wei)酒排序的(de)第三輪，需要(yao)重新(xin)從左向右(you)比較和交換：
1和(he)2比較(jiao)，位(wei)置(zhi)不(bu)變(bian)；2和(he)3比較(jiao)，位(wei)置(zhi)不(bu)變(bian)；3和(he)4比較(jiao)，位(wei)置(zhi)不(bu)變(bian)......6和(he)7比較(jiao)，位(wei)置(zhi)不(bu)變(bian)。
沒有元素位置交換，證明已(yi)經(jing)有序，排(pai)序結(jie)束(shu)。
這(zhe)就是雞尾酒排(pai)序的(de)思(si)路。排(pai)序過程就像鐘擺一樣，第一輪(lun)從左到右(you)(you)，第二(er)輪(lun)從右(you)(you)到左，第三輪(lun)再從左到右(you)(you)......
1 /// <summary> 2 /// 雞(ji)尾酒排序1 3 /// </summary> 4 /// <param name="list"></param> 5 /// <returns></returns> 6 private static List<int> CockTailSort1(List<int> array) 7 { 8 int tmp = 0; 9 for (int i = 0; i <= array.Count / 2-1; i++) 10 { 11 //有序標(biao)記，每(mei)一輪的初始是true 12 bool isSorted = true; 13 //從前到后的排序(xu)(xu) (升序(xu)(xu)) 14 for (int j = i; j < array.Count - i; j++) 15 { 16 if (j + 1 < array.Count && array[j] > array[j + 1]) 17 { 18 tmp = array[j]; 19 array[j] = array[j + 1]; 20 array[j + 1] = tmp; 21 //有元素交換，所以不是有序，標記變為false 22 isSorted = false; 23 } 24 } 25 if (isSorted) 26 { 27 break; 28 } 29 //從(cong)后到前(qian)的排序（降序） 30 for (int j = array.Count - i - 1; j >= i; j--) 31 { 32 if (j > 0 && array[j] < array[j - 1]) 33 { 34 tmp = array[j]; 35 array[j] = array[j - 1]; 36 array[j - 1] = tmp; 37 //有元素交(jiao)換，所(suo)以不是有序，標記(ji)變(bian)為(wei)false 38 isSorted = false; 39 } 40 } 41 if (isSorted) 42 { 43 break; 44 } 45 } 46 return array; 47 }
這段(duan)代碼(ma)(ma)是雞尾酒排序(xu)的原始實(shi)現。代碼(ma)(ma)外層的大循(xun)(xun)(xun)環(huan)控(kong)制(zhi)著(zhu)所有(you)排序(xu)回(hui)合，大循(xun)(xun)(xun)環(huan)內包含兩(liang)個(ge)小(xiao)循(xun)(xun)(xun)環(huan)，第一個(ge)循(xun)(xun)(xun)環(huan)從左(zuo)向(xiang)右(you)比較并(bing)交(jiao)換元素(su)，第二(er)個(ge)循(xun)(xun)(xun)環(huan)從右(you)向(xiang)左(zuo)比較并(bing)交(jiao)換元素(su)。
讓我們來回顧一下冒(mao)牌排序針對有序區(qu)的優化思(si)路(lu)：
原始(shi)的(de)冒泡排(pai)序(xu)，有(you)序(xu)區(qu)的(de)長(chang)度和排(pai)序(xu)的(de)輪(lun)數(shu)是(shi)相等的(de)。比如(ru)第一輪(lun)排(pai)序(xu)過(guo)后的(de)有(you)序(xu)區(qu)長(chang)度是(shi)1，第二(er)輪(lun)排(pai)序(xu)過(guo)后的(de)有(you)序(xu)區(qu)長(chang)度是(shi)2 ......
要想(xiang)優(you)化，我們可以在每(mei)一輪排序(xu)的(de)最(zui)后(hou)，記錄下最(zui)后(hou)一次元素交換的(de)位置(zhi)，那(nei)個位置(zhi)也(ye)就是無序(xu)數列的(de)邊界，再往(wang)后(hou)就是有(you)序(xu)區了。
對于單向的冒(mao)泡(pao)排(pai)序，我們(men)需要(yao)設(she)置一個(ge)邊界值，對于雙向的雞(ji)尾酒排(pai)序，我們(men)需要(yao)設(she)置兩個(ge)邊界值。請看代碼：
1 /// <summary> 2 /// 雞尾酒排序2 3 /// </summary> 4 /// <param name="list"></param> 5 /// <returns></returns> 6 private static List<int> CockTailSort2(List<int> array) 7 { 8 int tmp = 0; 9 //記(ji)錄右側最(zui)后一次交(jiao)換的(de)位(wei)置 10 int lastRightExchangeIndex = 0; 11 //記錄左側最后一次(ci)交換(huan)的位置 12 int lastLeftExchangeIndex = 0; 13 //無(wu)序(xu)數(shu)列的右邊界，每次比較只需要比到這里為止 14 int rightSortBorder = array.Count - 1; 15 //無序數列的左邊(bian)界，每次比較只需要(yao)比到這里為(wei)止 16 int leftSortBorder = 0; 17 for (int i = 0; i <= array.Count / 2 - 1; i++) 18 { 19 //有(you)序(xu)標(biao)記，每一輪(lun)的初始是(shi)true 20 bool isSorted = true; 21 //奇(qi)數輪，從左向右比較和交換 22 for (int j = leftSortBorder; j < rightSortBorder; j++) 23 { 24 if (array[j] > array[j + 1]) 25 { 26 tmp = array[j]; 27 array[j] = array[j + 1]; 28 array[j + 1] = tmp; 29 //有元素交換，所以不是有序，標記變為false 30 isSorted = false; 31 lastRightExchangeIndex = j; 32 } 33 } 34 rightSortBorder = lastRightExchangeIndex; 35 if (isSorted) 36 { 37 break; 38 } 39 //偶數(shu)輪，從右向左(zuo)比較和交換 40 for (int j = rightSortBorder; j > leftSortBorder; j--) 41 { 42 if (array[j] < array[j - 1]) 43 { 44 tmp = array[j]; 45 array[j] = array[j - 1]; 46 array[j - 1] = tmp; 47 //有元素交換(huan)，所以不是有序，標記變為(wei)false 48 isSorted = false; 49 lastLeftExchangeIndex = j; 50 } 51 } 52 leftSortBorder = lastLeftExchangeIndex; 53 if (isSorted) 54 { 55 break; 56 } 57 } 58 return array; 59 }
代碼中使用了左右兩個(ge)邊界(jie)值(zhi)，rightSortBorder 代表右邊界(jie)，leftSortBorder代表左邊界(jie)。
在比較(jiao)和交換元素時，奇數(shu)輪(lun)從 leftSortBorder遍歷(li)到 rightSortBorder 位(wei)置，偶數(shu)輪(lun)從 rightSortBorder 遍歷(li)到 leftSortBorder 位(wei)置。
—————END—————