本页使用了标题或全文手工转换

鸡尾酒排序

维基百科,自由的百科全书
跳到导航 跳到搜索
鸡尾酒排序
Sorting shaker sort anim.gif
使用鸡尾酒排序為一列数字进行排序的过程
分类 排序算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度

鸡尾酒排序,也就是定向冒泡排序雞尾酒攪拌排序攪拌排序(也可以視作選擇排序的一種變形),漣漪排序來回排序快乐小時排序,是冒泡排序的一種变形。此演算法与冒泡排序的不同處在於排序時是以双向在序列中進行排序。

伪代码[编辑]

将一个序列由小到大进行排序:

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语言[编辑]

 1 void cocktail_sort(int arr[], int len) {
 2 	int i, left = 0, right = len - 1;
 3 	int temp;
 4 	while (left < right) {
 5 		for (i = left; i < right; i++)
 6 			if (arr[i] > arr[i + 1]) {
 7 				temp = arr[i];
 8 				arr[i] = arr[i + 1];
 9 				arr[i + 1] = temp;
10 			}
11 		right--;
12 		for (i = right; i > left; i--)
13 			if (arr[i - 1] > arr[i]) {
14 				temp = arr[i];
15 				arr[i] = arr[i - 1];
16 				arr[i - 1] = temp;
17 			}
18 		left++;
19 	}
20 }

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++;
	}
}

JAVA[编辑]

 1 public static void cocktail_sort(int[] arr) {	
 2 	int i, left = 0, right = arr.length - 1;
 3 	int temp;
 4 	while (left < right) {
 5 		for (i = left; i < right; i++)
 6 			if (arr[i] > arr[i + 1]) {
 7 				temp = arr[i];
 8 				arr[i] = arr[i + 1];
 9 				arr[i + 1] = temp;
10 			}
11 		right--;
12 		for (i = right; i > left; i--)
13 			if (arr[i - 1] > arr[i]) {
14 				temp = arr[i];
15 				arr[i] = arr[i - 1];
16 				arr[i - 1] = temp;
17 			}
18 		left++;
19 	}
20 }

JavaScript[编辑]

 1 Array.prototype.cocktail_sort = function() {
 2 	var i, left = 0, right = this.length - 1;
 3 	var temp;
 4 	while (left < right) {
 5 		for (i = left; i < right; i++)
 6 			if (this[i] > this[i + 1]) {
 7 				temp = this[i];
 8 				this[i] = this[i + 1];
 9 				this[i + 1] = temp;
10 			}
11 		right--;
12 		for (i = right; i > left; i--)
13 			if (this[i - 1] > this[i]) {
14 				temp = this[i];
15 				this[i] = this[i - 1];
16 				this[i - 1] = temp;
17 			}
18 		left++;
19 	}
20 };

PHP[编辑]

 1 function swap(&$x, &$y) {
 2 	$t = $x;
 3 	$x = $y;
 4 	$y = $t;
 5 }
 6 function cocktail_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參才能修改原陣列
 7 	$left = 0;
 8 	$right = count($arr) - 1;
 9 	while ($left < $right) {
10 		for ($j = $left; $j < $right; $j++)
11 			if ($arr[$j] > $arr[$j + 1])
12 				swap($arr[$j], $arr[$j + 1]);
13 		$right--;
14 		for ($j = $right; $j > $left; $j--)
15 			if ($arr[$j - 1] > $arr[$j])
16 				swap($arr[$j - 1], $arr[$j]);
17 		$left++;
18 	}
19 }

Python 2.7[编辑]

 1 def cocktail_sort(l):
 2     l_len = len(l)
 3     for i in xrange(l_len, 0, -1):
 4         rem_i_l_len = abs(i - l_len)
 5         isNeedContinue = False
 6         obverse_count = len(l[rem_i_l_len : i-1])
 7         reverse_count = len(l[rem_i_l_len + 1 : i-1])
 8         
 9         for j in xrange(obverse_count):
10             if l[j] > l[j + 1]:
11                 l[j], l[j + 1] = l[j + 1], l[j]
12                 isNeedContinue = True
13         # you can print this to observe the whole process
14         # print l
15         
16         for j in xrange(reverse_count, 0, -1):
17             if l[j] < l[j - 1]:
18                 l[j], l[j - 1] = l[j - 1], l[j]
19                 isNeedContinue = True
20         # you can print this to observe the whole process
21         # print l
22         
23         if isNeedContinue:
24             continue
25         else:
26             return
27   
28         
29 if __name__ == '__main__':
30     sample_list = [6,5,4,3,2,100]
31     cocktail_sort(sample_list)
32     print sample_list

Golang[编辑]

 1 func cocktailSort(arr []int) {
 2 	i, left := 0, 0
 3 	right := len(arr) - 1
 4 	var temp int
 5 	for left < right {
 6 		for i = left; i < right; i++ {
 7 			if arr[i] > arr[i+1] {
 8 				temp = arr[i]
 9 				arr[i] = arr[i+1]
10 				arr[i+1] = temp
11 			}
12 		}
13 		right--
14 
15 		for i = right; i > left; i-- {
16 			if arr[i-1] > arr[i] {
17 				temp = arr[i]
18 				arr[i] = arr[i-1]
19 				arr[i-1] = temp
20 			}
21 		}
22 		left++
23 	}
24 }

複雜度[编辑]

鸡尾酒排序最糟或是平均所花費的次數都是,但如果序列在一開始已經大部分排序過的話,會接近

額外連結[编辑]