介绍

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

原理

实现

JavaScript

/**
 * Cocktail Shaker Sort is an algorithm that is a Bidirectional（双向的） Bubble Sort.
 *
 * The algorithm extends bubble sort by operating in two directions.
 * While it improves on bubble sort by more quickly moving items to the beginning of the list, it provides only marginal（微小的）
 * performance improvements.
 *
 * Wikipedia (Cocktail Shaker Sort): https://en.wikipedia.org/wiki/Cocktail_shaker_sort
 * Wikipedia (Bubble Sort): https://en.wikipedia.org/wiki/Bubble_sort
 */
function cocktailShakerSort (items) {
  for (let i = items.length - 1; i > 0; i--) {
    let j

    // Backwards
    for (j = items.length - 1; j > i; j--) {
      if (items[j] < items[j - 1]) {
        [items[j], items[j - 1]] = [items[j - 1], items[j]]
      }
    }

    // Forwards
    for (j = 0; j < i; j++) {
      if (items[j] > items[j + 1]) {
        [items[j], items[j + 1]] = [items[j + 1], items[j]]
      }
    }
  }

  return items
}

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

参考

• 鸡尾酒排序 - 维基百科，自由的百科全书 (opens new window)