鸡尾酒排序
| 鸡尾酒排序 | |
|---|---|
 使用鸡尾酒排序為一列数字进行排序的过程 | |
| 概况 | |
| 類別 | 排序算法 |
| 資料結構 | 数组 |
| 复杂度 | |
| 平均時間複雜度 | |
| 最坏时间复杂度 | |
| 最优时间复杂度 | |
| 最佳解 | No |
| 相关变量的定义 | |
鸡尾酒排序（英語：Cocktail shaker sort），亦為定向冒泡排序，雞尾酒攪拌排序，攪拌排序（也可以視作選擇排序的一種變形），漣漪排序，來回排序或快乐小時排序，是冒泡排序的一種变形。此演算法与冒泡排序的不同處在於排序時是以双向在序列中進行排序。
伪代码
将一个序列由小到大进行排序：
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）為例，鸡尾酒排序只需要訪問一次序列就可以完成排序，但如果使用冒泡排序則需要四次。但是在亂數序列的狀態下，鸡尾酒排序與冒泡排序的效率与其他众多排序算法相比均比较低。
實作範例
C语言
void cocktail_sort(int arr[], int len) {
int i, left = 0, right = len - 1;
int temp;
while (left < right) {
for (i = left; i < right; i++)
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
right--;
for (i = right; i > left; i--)
if (arr[i - 1] > arr[i]) {
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
left++;
}
}
C++
template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void cocktail_sort(T arr[], int len) {
int j, left = 0, right = len - 1;
while (left < right) {
for (j = left; j < right; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
right--;
for (j = right; j > left; j--)
if (arr[j - 1] > arr[j])
swap(arr[j - 1], arr[j]);
left++;
}
}
Rust
fn cocktail_sort<T: PartialOrd>(arr: &mut [T]) {
let mut bottom: usize = 0;
let mut top = arr.len() - 1;
let mut swapped = true;
while swapped {
swapped = false;
for i in bottom..top {
if arr[i] > arr[i+1] {
arr.swap(i, i+1);
swapped = true;
}
}
top -= 1;
for j in ((bottom + 1)..=top).rev() {
if arr[j] < arr[j - 1] {
arr.swap(j, j - 1);
swapped = true;
}
}
bottom += 1;
}
}
JAVA
public static void cocktail_sort(int[] arr) {
int i, left = 0, right = arr.length - 1;
int temp;
while (left < right) {
for (i = left; i < right; i++)
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
right--;
for (i = right; i > left; i--)
if (arr[i - 1] > arr[i]) {
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
left++;
}
}
JavaScript
Array.prototype.cocktail_sort = function() {
var i, left = 0, right = this.length - 1;
var temp;
while (left < right) {
for (i = left; i < right; i++)
if (this[i] > this[i + 1]) {
temp = this[i];
this[i] = this[i + 1];
this[i + 1] = temp;
}
right--;
for (i = right; i > left; i--)
if (this[i - 1] > this[i]) {
temp = this[i];
this[i] = this[i - 1];
this[i - 1] = temp;
}
left++;
}
};
PHP
function swap(&$x, &$y) {
$t = $x;
$x = $y;
$y = $t;
}
function cocktail_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參才能修改原陣列
$left = 0;
$right = count($arr) - 1;
while ($left < $right) {
for ($j = $left; $j < $right; $j++)
if ($arr[$j] > $arr[$j + 1])
swap($arr[$j], $arr[$j + 1]);
$right--;
for ($j = $right; $j > $left; $j--)
if ($arr[$j - 1] > $arr[$j])
swap($arr[$j - 1], $arr[$j]);
$left++;
}
}
Python 2.7
def cocktail_sort(l):
l_len = len(l)
for i in range(l_len, 0, -1):
rem_i_l_len = abs(i - l_len)
isNeedContinue = False
obverse_count = len(l[rem_i_l_len : i-1])
reverse_count = len(l[rem_i_l_len + 1 : i-1])
for j in range(obverse_count):
if l[j] > l[j + 1]:
l[j], l[j + 1] = l[j + 1], l[j]
isNeedContinue = True
# you can print this to observe the whole process
# print l
for j in range(reverse_count, 0, -1):
if l[j] < l[j - 1]:
l[j], l[j - 1] = l[j - 1], l[j]
isNeedContinue = True
# you can print this to observe the whole process
# print l
if isNeedContinue:
continue
else:
return
if __name__ == '__main__':
sample_list = [6,5,4,3,2,100]
cocktail_sort(sample_list)
print(sample_list)
Python 3.10
def cocktail_sort(arr: list, bottom: int = None, top: int = None):
if not bottom and not top:
bottom, top = 0, len(arr) - 1
if bottom == top or bottom > top:
return
swapped: bool = False
for i in range(bottom, top):
if arr[i] > arr[i + 1]:
arr[i + 1], arr[i] = arr[i], arr[i + 1]
swapped = True
for i in range(top - 1, bottom, -1):
if arr[i] < arr[i - 1]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
swapped = True
if not swapped:
return
cocktail_sort(arr, bottom + 1, top - 1)
if __name__ == '__main__':
sample_list = [3, 7, 5, 1, 6, 4, 8, 2]
cocktail_sort(sample_list)
print(sample_list)
Golang
func cocktailSort(arr []int) {
left := 0
right := len(arr) - 1
for left < right {
for i := left; i < right; i++ {
if arr[i] > arr[i+1] {
arr[i], arr[i+1] = arr[i+1], arr[i]
}
}
right--
for i := right; i > left; i-- {
if arr[i-1] > arr[i] {
arr[i-1], arr[i] = arr[i], arr[i-1]
}
}
left++
}
}
Julia (程式語言)
# Julia Sample : CocktailSort
function CocktailSort(A)
isordered, lo, hi = false, 1, length(A)
while !isordered && hi > lo
isordered = true
for i=lo+1:hi
if A[i] < A[i-1]
A[i-1], A[i] = A[i], A[i-1]
isordered = false
end
end
hi -= 1
if isordered || hi ≤ lo
break
end
for i in hi:-1:lo+1
if A[i-1] > A[i]
A[i-1], A[i] = A[i], A[i-1]
isordered = false
end
end
lo += 1
end
return A
end
# Main Code
A = [16,586,1,31,354,43,3]
println(A) # Original Array
println(CocktailSort(A)) # Cocktail Sort Array
複雜度
鸡尾酒排序最糟或是平均所花費的次數都是，但如果序列在一開始已經大部分排序過的話，會接近。
外部連結
- Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
- Implementations of cocktail sort in several different programming languages
| |||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
