1 using System;
 2  using System.Collections.Generic;
 3 
 4 namespace Com.Colobu.Algorithm.Exchange
 5 {
 6     /// <summary>
 7     /// <b>鸡尾酒排序</b>，也就是双向冒泡排序(bidirectional bubble sort), 鸡尾酒搅拌排序, 搅拌排序 
 8     /// (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 
 9     /// 是冒泡排序的一种变形。
10     /// 此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
11     /// 
12     /// 平均时间复杂度:O(n^2)
13     /// Stability:Yes
14     /// </summary>
15     public class CocktailSortAlgorithm
16     {
17         public static void CocktailSort<T>(IList<T> szArray) where T : IComparable
18         {
19             int bottom = 0;
20             int top = szArray.Count - 1;
21             bool swapped = true;
22             while (swapped == true) // if no elements have been swapped, then the list is sorted
23             {
24                 swapped = false;
25                 for (int i = bottom; i < top; i = i + 1)
26                 {
27                     if (szArray[i].CompareTo(szArray[i + 1]) > 0)  // test whether the two elements are in the correct order
28                     {
29                         Swap(szArray,i,i + 1); // let the two elements change places
30                         swapped = true;
31                     }
32                 }
33                 // decreases top the because the element with the largest value in the unsorted
34                 // part of the list is now on the position top 
35                 top = top - 1;
36                 for (int i = top; i > bottom; i = i - 1)
37                 {
38                     if (szArray[i].CompareTo(szArray[i - 1]) < 0)
39                     {
40                         Swap(szArray,i,i - 1);
41                         swapped = true;
42                     }
43                 }
44                 // increases bottom because the element with the smallest value in the unsorted 
45                 // part of the list is now on the position bottom 
46                 bottom = bottom + 1;
47             }
48         }
49 
50         private static void Swap<T>(IList<T> szArray, int i,int j)
51         {
52             T tmp = szArray[i];
53             szArray[i] = szArray[j];
54             szArray[j] = tmp;
55         }
56     }
57 }
58