# 鸡尾酒排序

（重定向自雞尾酒排序

## 伪代码

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

## 實作範例

### 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 range(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 range(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 range(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 	left := 0
3 	right := len(arr) - 1
4
5 	for left < right {
6 		for i := left; i < right; i++ {
7 			if arr[i] > arr[i+1] {
8 				arr[i], arr[i+1] = arr[i+1], arr[i]
9 			}
10 		}
11 		right--
12
13 		for i := right; i > left; i-- {
14 			if arr[i-1] > arr[i] {
15 				arr[i-1], arr[i] = arr[i], arr[i-1]
16 			}
17 		}
18 		left++
19 	}
20 }
```