经典算法题每日演练——第二十二题 奇偶排序-阿里云开发者社区

开发者社区> 人工智能> 正文

经典算法题每日演练——第二十二题 奇偶排序

简介: 原文:经典算法题每日演练——第二十二题 奇偶排序     这个专题因为各种原因好久没有继续下去了,MM吧。。。你懂的,嘿嘿,不过还得继续写下去,好长时间不写,有些东西有点生疏了, 这篇就从简单一点的一个“奇偶排序”说起吧,不过这个排序还是蛮有意思的,严格来说复杂度是O(N2),不过在多核的情况下,可以做到 N2 /(m/2)的效率,这里的m就是待排序的个数,当m=100,复杂度为N2 /50,还行把,比冒泡要好点,因为重点是解决问题的奇思妙想。
原文:经典算法题每日演练——第二十二题 奇偶排序

 

  这个专题因为各种原因好久没有继续下去了,MM吧。。。你懂的,嘿嘿,不过还得继续写下去,好长时间不写,有些东西有点生疏了,

这篇就从简单一点的一个“奇偶排序”说起吧,不过这个排序还是蛮有意思的,严格来说复杂度是O(N2),不过在多核的情况下,可以做到

N2 /(m/2)的效率,这里的m就是待排序的个数,当m=100,复杂度为N2 /50,还行把,比冒泡要好点,因为重点是解决问题的奇思妙想。

    下面我们看看这个算法是怎么描述的,既然是奇偶,肯定跟位数有关了

1:先将待排序数组的所有奇数位与自己身后相邻的偶数位相比较,如果前者大于后者,则进行交换,直到这一趟结束。

2:然后将偶数位与自己身后相邻的奇数位相比较,如果前者大于后者,则进行交换,直到这一趟结束。

3:重复1,2的步骤,直到发现无“奇偶”,“偶奇” 交换的时候,就认为排序完毕,此时退出循环。

 

  由于网速问题,下载几次freehand都失败了,我就手写个例子吧。

 

① 待排序数组:                                            9  2  1  6  0  7

② 所有奇数位与身后的相邻的偶数位比较交换       2  9  1  6  0  7

③ 所有偶数位与身后的相邻的奇数位比较交换       2  1  9  0  6  7

④ 所有奇数位与身后的相邻的偶数位比较交换       1  2  0  9  6  7

⑤ 所有偶数位与身后的相邻的奇数位比较交换       1  0  2  6  9  7

⑥ 所有奇数位与身后的相邻的偶数位比较交换       0  1  2  6  7  9

 

我们可以看到,经过5趟排序后,我们的数组就排序完毕了,从图中②可以看到,如果每个线程分摊一个奇数位,那交换是不是只要

一次就够了呢,可以看到这个算法在多核处理下面还是很有优势的。

最后的运行代码:

 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>() { 9, 2, 1, 6, 0, 7 };
14 
15             Console.WriteLine("\n排序前 => " + string.Join(",", list));
16 
17             list = OddEvenSort(list);
18 
19             Console.WriteLine("\n排序后 => " + string.Join(",", list));
20 
21             Console.Read();
22         }
23 
24         static List<int> OddEvenSort(List<int> list)
25         {
26             var isSorted = false;
27 
28             //如果还没有排序完,就需要继续排序,知道没有交换为止
29             while (!isSorted)
30             {
31                 //先默认已经排序完了
32                 isSorted = true;
33 
34                 //先进行 奇数位 排序
35                 for (int i = 0; i < list.Count; i = i + 2)
36                 {
37                     //如果 前者 大于 后者,则需要进行交换操作,也要防止边界
38                     if (i + 1 < list.Count && list[i] > list[i + 1])
39                     {
40                         var temp = list[i];
41                         list[i] = list[i + 1];
42                         list[i + 1] = temp;
43 
44                         //说明存在过排序,还没有排序完
45                         isSorted = false;
46                     }
47                 }
48 
49                 //再进行 奇数位 排序
50                 for (int i = 1; i < list.Count; i = i + 2)
51                 {
52                     //如果 前者 大于 后者,则需要进行交换操作,也要防止边界
53                     if (i + 1 < list.Count && list[i] > list[i + 1])
54                     {
55                         var temp = list[i];
56                         list[i] = list[i + 1];
57                         list[i + 1] = temp;
58 
59                         //说明存在过排序,还没有排序完
60                         isSorted = false;
61                     }
62                 }
63             }
64 
65             return list;
66         }
67     }
68 }

 

 

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章