首页 > 代码库 > 经典算法题每日演练——第二十三题 鸡尾酒排序
经典算法题每日演练——第二十三题 鸡尾酒排序
原文:经典算法题每日演练——第二十三题 鸡尾酒排序
这篇我们继续扯淡一下鸡尾酒排序，为了知道为啥取名为鸡尾酒，特意看了下百科，见框框的话，也只能勉强这么说了。
要是文艺点的话，可以说是搅拌排序，通俗易懂点的话，就叫“双向冒泡排序”，我想作为码农的话，不可能不知道冒泡排序，
冒泡是一个单向的从小到大或者从大到小的交换排序，而鸡尾酒排序是双向的，从一端进行从小到大排序，从另一端进行从大
到小排序。
从图中可以看到，第一次正向比较，我们找到了最大值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 Program10 {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 }
经典算法题每日演练——第二十三题 鸡尾酒排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。