经典算法题每日演练——第二十三题 鸡尾酒排序
2023-02-18 16:44:07 时间
这篇我们继续扯淡一下鸡尾酒排序,为了知道为啥取名为鸡尾酒,特意看了下百科,见框框的话,也只能勉强这么说了。
要是文艺点的话,可以说是搅拌排序,通俗易懂点的话,就叫“双向冒泡排序”,我想作为码农的话,不可能不知道冒泡排序,
冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大
到小排序。
从图中可以看到,第一次正向比较,我们找到了最大值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 }
相关文章
- 还重构?就你那代码只能铲了重写!
- 工作3年,看啥资料能月薪30K?
- 组内分享,画架构图的一些知识整理
- 给你一台服务器,你能把你写的代码部署到线上吗?
- 刚火了的中台转头就拆,一大波公司放不下又拿不起来!
- 工作两年简历写成这样,谁要你呀!
- 讲道理,只要你是一个爱折腾的程序员,毕业找工作真的不需要再花钱培训!
- 刚毕业不久,接私活赚了2万块!
- 北漂码农的我,把在大城市过成了屯子一样舒服,哈哈哈哈哈!
- 码农会锁,synchronized 对象头结构(mark-word、Klass Pointer)、指针压缩、锁竞争,源码解毒、深度分析!
- 都说搭博客简单,鬼知道后端程序员要经历什么!
- 炸!1024我的故事,一个写了两年博客的大厂码农!
- 几百行代码写个Mybatis,原理搞的透透的!
- 每个程序员都该有个自己的博客,分享我的四种博客搭建教程!
- 一次代码评审,差点过不了试用期!
- 数学,离一个程序员有多近?
- 程序员为什么热衷于造轮子,升职加薪吗?
- 牛掰,在IDEA中,你可以安装小傅哥写的插件了!
- 得物(毒)APP,8位抽奖码需求,这不就是产品给我留的数学作业!
- 90%的程序员,都没用过多线程和锁,怎么成为架构师?