经典算法题每日演练——第二十三题 鸡尾酒排序

原文:经典算法题每日演练——第二十三题 鸡尾酒排序

 

　　这篇我们继续扯淡一下鸡尾酒排序，为了知道为啥取名为鸡尾酒，特意看了下百科，见框框的话，也只能勉强这么说了。

要是文艺点的话，可以说是搅拌排序，通俗易懂点的话，就叫“双向冒泡排序”，我想作为码农的话，不可能不知道冒泡排序，

冒泡是一个单向的从小到大或者从大到小的交换排序，而鸡尾酒排序是双向的，从一端进行从小到大排序，从另一端进行从大

到小排序。

从图中可以看到，第一次正向比较，我们找到了最大值9. 

                      第一次反向比较，我们找到了最小值1.

                      第二次正向比较，我们找到了次大值8.

                      第二次反向比较，我们找到了次小值2

                      。。。

                     最后就大功告成了。

下面我们看看代码：

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Xml.Xsl;
 6
 7 namespace ConsoleApplication1
 8 {
 9     class Program
10     {
11         static void Main(string[] args)
12         {
13             List<int> list = new List<int>() { 8, 1, 4, 2, 9, 5, 3 };
14
15             Console.WriteLine("\n排序前 => {0}\n", string.Join(",", list));
16
17             list = CockTailSort(list);
18
19             Console.WriteLine("\n排序后 => {0}\n", string.Join(",", list));
20
21             Console.Read();
22         }
23
24         /// <summary>
25         /// 鸡尾酒排序
26         /// </summary>
27         /// <param name="list"></param>
28         /// <returns></returns>
29         static List<int> CockTailSort(List<int> list)
30         {
31             //因为是双向比较，所以比较次数为原来数组的1/2次即可。
32             for (int i = 1; i <= list.Count / 2; i++)
33             {
34                 //从前到后的排序 (升序)
35                 for (int m = i - 1; m <= list.Count - i; m++)
36                 {
37                     //如果前面大于后面，则进行交换
38                     if (m + 1 < list.Count && list[m] > list[m + 1])
39                     {
40                         var temp = list[m];
41
42                         list[m] = list[m + 1];
43
44                         list[m + 1] = temp;
45                     }
46                 }
47
48                 Console.WriteLine("正向排序 => {0}", string.Join(",", list));
49
50                 //从后到前的排序（降序）
51                 for (int n = list.Count - i - 1; n >= i; n--)
52                 {
53                     //如果前面大于后面，则进行交换
54                     if (n > 0 && list[n - 1] > list[n])
55                     {
56                         var temp = list[n];
57
58                         list[n] = list[n - 1];
59
60                         list[n - 1] = temp;
61                     }
62                 }
63
64                 Console.WriteLine("反向排序 => {0}", string.Join(",", list));
65             }
66
67             return list;
68         }
69     }
70 }

从结果上面看，我们会发现，当数组有序的时候，我们还会继续往下排，知道完成length/2次，这个就跟没优化之前的冒泡排序一样，

此时我们可以加上一个标志位IsSorted来判断是否已经没有交换了，如果没有，提前退出循环。。。

 1         /// <summary>
 2         /// 鸡尾酒排序
 3         /// </summary>
 4         /// <param name="list"></param>
 5         /// <returns></returns>
 6         static List<int> CockTailSort(List<int> list)
 7         {
 8             //判断是否已经排序了
 9             var isSorted = false;
10
11             //因为是双向比较，所以比较次数为原来数组的1/2次即可。
12             for (int i = 1; i <= list.Count / 2; i++)
13             {
14                 //从前到后的排序 (升序)
15                 for (int m = i - 1; m <= list.Count - i; m++)
16                 {
17                     //如果前面大于后面，则进行交换
18                     if (m + 1 < list.Count && list[m] > list[m + 1])
19                     {
20                         var temp = list[m];
21
22                         list[m] = list[m + 1];
23
24                         list[m + 1] = temp;
25
26                         isSorted = true;
27                     }
28                 }
29
30                 Console.WriteLine("正向排序 => {0}", string.Join(",", list));
31
32                 //从后到前的排序（降序）
33                 for (int n = list.Count - i - 1; n >= i; n--)
34                 {
35                     //如果前面大于后面，则进行交换
36                     if (n > 0 && list[n - 1] > list[n])
37                     {
38                         var temp = list[n];
39
40                         list[n] = list[n - 1];
41
42                         list[n - 1] = temp;
43
44                         isSorted = true;
45                     }
46                 }
47
48                 //当不再有排序，提前退出
49                 if (!isSorted)
50                     break;
51
52                 Console.WriteLine("反向排序 => {0}", string.Join(",", list));
53             }
54
55             return list;
56         }