经典算法题每日演练——第二十三题 鸡尾酒排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了经典算法题每日演练——第二十三题 鸡尾酒排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2975字,纯文字阅读大概需要5分钟。
内容图文
这篇我们继续扯淡一下鸡尾酒排序,为了知道为啥取名为鸡尾酒,特意看了下百科,见框框的话,也只能勉强这么说了。
要是文艺点的话,可以说是搅拌排序,通俗易懂点的话,就叫“双向冒泡排序”,我想作为码农的话,不可能不知道冒泡排序,
冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大
到小排序。
从图中可以看到,第一次正向比较,我们找到了最大值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 }; 1415 Console.WriteLine("\n排序前 => {0}\n", string.Join(",", list)); 1617 list = CockTailSort(list); 1819 Console.WriteLine("\n排序后 => {0}\n", string.Join(",", list)); 2021 Console.Read(); 22 } 2324///<summary>25/// 鸡尾酒排序 26///</summary>27///<param name="list"></param>28///<returns></returns>29static List<int> CockTailSort(List<int> list) 30 { 31//因为是双向比较,所以比较次数为原来数组的1/2次即可。32for (int i = 1; i <= list.Count / 2; i++) 33 { 34//从前到后的排序 (升序)35for (int m = i - 1; m <= list.Count - i; m++) 36 { 37//如果前面大于后面,则进行交换38if (m + 1 < list.Count && list[m] > list[m + 1]) 39 { 40var temp = list[m]; 4142 list[m] = list[m + 1]; 4344 list[m + 1] = temp; 45 } 46 } 4748 Console.WriteLine("正向排序 => {0}", string.Join(",", list)); 4950//从后到前的排序(降序)51for (int n = list.Count - i - 1; n >= i; n--) 52 { 53//如果前面大于后面,则进行交换54if (n > 0 && list[n - 1] > list[n]) 55 { 56var temp = list[n]; 5758 list[n] = list[n - 1]; 5960 list[n - 1] = temp; 61 } 62 } 6364 Console.WriteLine("反向排序 => {0}", string.Join(",", list)); 65 } 6667return 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; 1011//因为是双向比较,所以比较次数为原来数组的1/2次即可。12for (int i = 1; i <= list.Count / 2; i++) 13 { 14//从前到后的排序 (升序)15for (int m = i - 1; m <= list.Count - i; m++) 16 { 17//如果前面大于后面,则进行交换18if (m + 1 < list.Count && list[m] > list[m + 1]) 19 { 20var temp = list[m]; 2122 list[m] = list[m + 1]; 2324 list[m + 1] = temp; 2526 isSorted = true; 27 } 28 } 2930 Console.WriteLine("正向排序 => {0}", string.Join(",", list)); 3132//从后到前的排序(降序)33for (int n = list.Count - i - 1; n >= i; n--) 34 { 35//如果前面大于后面,则进行交换36if (n > 0 && list[n - 1] > list[n]) 37 { 38var temp = list[n]; 3940 list[n] = list[n - 1]; 4142 list[n - 1] = temp; 4344 isSorted = true; 45 } 46 } 4748//当不再有排序,提前退出49if (!isSorted) 50break; 5152 Console.WriteLine("反向排序 => {0}", string.Join(",", list)); 53 } 5455return list; 56 }
原文:http://www.cnblogs.com/huangxincheng/p/3576492.html
内容总结
以上是互联网集市为您收集整理的经典算法题每日演练——第二十三题 鸡尾酒排序全部内容,希望文章能够帮你解决经典算法题每日演练——第二十三题 鸡尾酒排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。