鸡尾酒排序

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

伪代码

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

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

复杂度

鸡尾酒排序最糟或是平均所花费的次数都是{\displaystyle O(n^{2})}，但如果序列在一开始已经大部分排序过的话，会接近{\displaystyle O(n)}。

原文地址：https://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F

在知识共享 署名-相同方式共享 3.0协议之条款下提供