查看“︁鸡尾酒排序”︁的源代码

{{NoteTA
|G1 = IT
}}
{{算法信息框
|class=[[排序算法]]
|image=[[File:Sorting shaker sort anim.gif]]
|caption=使用鸡尾酒排序為一列数字进行排序的过程
|data=[[数组]]
|time=<math> O(n^2) </math>
|best-time=<math>O(n)</math>
|average-time= <math>  O(n^2) </math>
|space=
|optimal=No
}}

'''鸡尾酒排序'''（{{lang-en|Cocktail shaker sort}}），亦為'''定向冒泡排序'''，'''雞尾酒攪拌排序'''，'''攪拌排序'''（也可以視作[[選擇排序]]的一種變形），'''漣漪排序'''，'''來回排序'''或'''快乐小時排序'''，是[[冒泡排序]]的一種变形。此演算法与[[冒泡排序]]的不同處在於排序時是以双向在序列中進行排序。

== 伪代码 ==
将一个序列由小到大进行排序：
 '''function''' cocktail_sort(list, list_length){ <span style="color:green">// the first element of list has index 0</span>
     bottom = 0;
     top = list_length - 1;
     swapped = true; 
     '''while'''(swapped == true) <span style="color:green">// if no elements have been swapped, then the list is sorted</span>
     {
         swapped = false; 
         '''for'''(i = bottom; i < top; i = i + 1)
         {
             '''if'''(list[i] > list[i + 1])  <span style="color:green">// test whether the two elements are in the correct order</span>
             {
                 swap(list[i], list[i + 1]); <span style="color:green">// let the two elements change places</span>
                 swapped = true;
             }
         }
         <span style="color:green">// decreases top the because the element with the largest value in the unsorted
         // part of the list is now on the position top </span>
         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;
             }
         }
         <span style="color:green">// increases bottom because the element with the smallest value in the unsorted 
         // part of the list is now on the position bottom </span>
         bottom = bottom + 1;  
     }
 }

== 与冒泡排序不同的地方 ==
鸡尾酒排序等於是[[冒泡排序]]的輕微變形。不同的地方在於從低到高然後從高到低，而[[冒泡排序]]則僅從低到高去比較序列裡的每個元素。他可以得到比[[冒泡排序]]稍微好一點的效能，原因是[[冒泡排序]]只從一個方向進行比對（由低到高），每次循環只移動一個項目。

以序列（2,3,4,5,1）為例，鸡尾酒排序只需要訪問一次序列就可以完成排序，但如果使用[[冒泡排序]]則需要四次。但是在亂數序列的狀態下，鸡尾酒排序與冒泡排序的效率与其他众多排序算法相比均比较低。

==實作範例==

===C语言===
<syntaxhighlight lang="c" line="1">
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++;
	}
}
</syntaxhighlight>

===C++===
<syntaxhighlight lang = "cpp">
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++;
	}
}
</syntaxhighlight>

===Rust===
<syntaxhighlight lang = "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;
    }
}
</syntaxhighlight>

===JAVA===
<syntaxhighlight lang="java" line="1">
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++;
	}
}
</syntaxhighlight>

===JavaScript===
<syntaxhighlight lang="javascript" line="1">
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++;
	}
};
</syntaxhighlight>
===PHP===
<syntaxhighlight lang="php" line="1">
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++;
	}
}
</syntaxhighlight>
===Python 2.7===
<syntaxhighlight lang="python3" line="1">
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)
</syntaxhighlight>
===Python 3.10===
<syntaxhighlight lang="python3" line="1">
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)
</syntaxhighlight>

=== Golang ===
<syntaxhighlight lang="go" line="1">
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++
	}
}

</syntaxhighlight>



===[[Julia (程式語言)]]===
<syntaxhighlight lang="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
</syntaxhighlight>

== 複雜度 ==
鸡尾酒排序最糟或是平均所花費的次數都是<math>O(n^2)</math>，但如果序列在一開始已經大部分排序過的話，會接近<math>O(n)</math>。

== 外部連結 ==
*[https://web.archive.org/web/20061008105719/http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms]
*[[:wikisource:Cocktail Sort|Implementations of cocktail sort in several different programming languages]]

{{排序算法表}}
{{算法}}

[[Category:排序算法]]
[[Category:带有伪代码示例的条目]]
[[Category:带有代码示例的条目]]