鸡尾酒排序
维基百科，自由的百科全书
雞尾酒排序，也就是定向冒泡排序, 雞尾酒攪拌排序, 攪拌排序 (也可以視作選擇排序的一種變形), 漣漪排序, 來回排序 or 快樂小時排序, 是冒泡排序的一種變形。此演算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。
目录 |
[编辑] 虛擬碼
虛擬碼是以 C 語言撰寫，目的在將一個序列由小到大進行排序：
function cocktail_sort(list, list_length) // the first element of list has index 0 bottom = 0; top = list_length - 1; swapped = true; while(swapped == true) // if no elements have been swapped, then the list is sorted { swapped = false; for(i = bottom; i < top; i = i + 1) { if(list[i] > list[i + 1]) // test whether the two elements are in the correct order { swap(list[i], list[i + 1]); // let the two elements change places swapped = true; } } // decreases top the because the element with the largest value in the unsorted // part of the list is now on the position top top = top - 1; for(i = top; i > bottom; i = i - 1) { if(list[i] < list[i - 1]) { swap(list[i], list[i - 1]); swapped = true; } } // increases bottom because the element with the smallest value in the unsorted // part of the list is now on the position bottom bottom = bottom + 1; } }
[编辑] 與冒泡排序不同的地方
雞尾酒排序等於是冒泡排序的輕微變形。不同的地方在於從低到高然後從高到低，而冒泡排序則僅從低到高去比較序列裡的每個元素。他可以得到比冒泡排序稍微好一點的效能，原因是冒泡排序只從一個方向進行比對(由低到高)，每次循環只移動一個項目。
以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問一次序列就可以完成排序，但如果使用冒泡排序則需要四次。
[编辑] 複雜度
雞尾酒排序最糟或是平均所花費的次數都是O(n2)，但如果序列在一開始已經大部分排序過的話，會接近O(n)。
