C# 實作雞尾酒排序演算法

演算法簡介

雞尾酒排序，又稱雙向氣泡排序、攪拌排序 或漣漪排序，是氣泡排序的改良版。標準氣泡排序單向掃描（由小到大），每輪只能將最大值移至末端；雞尾酒排序則雙向交替掃描：先由左往右將最大值「冒泡」到右端，再由右往左將最小值「下沉」到左端。如此可減少約一半的掃描輪數，效能略優於單向氣泡排序（但仍屬 O(n²)，僅適合小規模資料教學用途）。

完整實作代碼

using System;

namespace SortingAlgorithms
{
    public static class CocktailSorter
    {
        public static int[] Sort(int[] array)
        {
            if (array == null || array.Length < 2) return array;
            CocktailSort(array);
            return array;
        }

        private static void CocktailSort(int[] arr)
        {
            int low = 0;
            int up = arr.Length - 1;
            int lastSwap = low;

            while (up > low)
            {
                // 正向掃描：將最大值移到 up
                for (int i = low; i < up; i++)
                {
                    if (arr[i] > arr[i + 1])
                    {
                        Swap(ref arr[i], ref arr[i + 1]);
                        lastSwap = i;
                    }
                }
                up = lastSwap; // 縮小右邊界

                // 反向掃描：將最小值移到 low
                for (int i = up; i > low; i--)
                {
                    if (arr[i] < arr[i - 1])
                    {
                        Swap(ref arr[i], ref arr[i - 1]);
                        lastSwap = i;
                    }
                }
                low = lastSwap; // 縮小左邊界
            }
        }

        private static void Swap(ref int a, ref int b)
        {
            int tmp = a; a = b; b = tmp;
        }
    }
}

運作流程圖解

假設陣列 [5, 1, 4, 2, 8, 3]：

1. 第 1 輪正向： 5↔1, 5↔4, 5↔2, 8↔3 → [1, 4, 2, 5, 3, 8]，up=4
2. 第 1 輪反向： 3↔5, 2↔4 → [1, 2, 4, 3, 5, 8]，low=1
3. 第 2 輪正向： 4↔3 → [1, 2, 3, 4, 5, 8]，up=2
4. 第 2 輪反向： 無交換 → low=2，結束