# 鸡尾酒排序

分類 使用鸡尾酒排序為一列数字进行排序的过程 排序算法 数组 $O(n^2)$ $O(n)$ $O(n^2)$

## 伪代码

```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语言实现

```void cocktail_sort(int arr[], int len) {
int j, left = 0, right = len - 1;
int temp;
while (left < right) {
for (j = left; j < right; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
right--;
for (j = right; j > left; j--)
if (arr[j - 1] > arr[j]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
left++;
}
}
```

### C++实现

```template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void cocktail_sort(T arr[], int len) {
int j, left = 0, right = len - 1;
T temp;
while (left < right) {
for (j = left; j < right; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
right--;
for (j = right; j > left; j--)
if (arr[j - 1] > arr[j]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
left++;
}
}
```

### JAVA实现

```	/**
* 鸡尾酒排序法
*
* @param a
*            指定整型数组
*/
public void sort(int[] a) {
//需要来回a,length/2趟
for (int i = 0; i < a.length / 2; i++) {
//类冒泡，交换最大值至右端
for (int j = i; 1 + j < a.length - i; j++)
if (a[j] > a[1 + j])
Arr.swap(a, j, 1 + j);
//类冒泡，交换最小值至左端
for (int j = a.length - i - 1; j > i; j--)
if (a[j - 1] > a[j])
Arr.swap(a, j - 1, j);
}
}
```