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

　　由于种种原因，这个话题已经很久没有继续了，MM。。。你知道，嘿嘿，但你必须继续写下去。如果你很长时间不写，有些事情有点陌生，

这篇文章从一个简单的“奇偶排名”开始，但是这个排名挺有意思的。严格来说，复杂度是O(N2)，但是在多核的情况下，可以做到。

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

让我们来看看这个算法是如何描述的。既然是奇偶，肯定和位数有关。

1：首先，将待排序数组的所有奇数数与身后相邻的偶数数进行比较。如果前者大于后者，则交换，直到旅程结束。

2：然后将偶数数与身后相邻的奇数数进行比较。如果前者大于后者，则交换，直到旅程结束。

3：重复1、2的步骤，直到发现没有“奇偶”和“奇偶” 交换时，认为排名已经完成，此时退出循环。

　　由于网速问题，下载几次frehand都失败了，我就手写一个例子。

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

② 所有奇数位与身后相邻的偶数位进行比较交换 2 916 0 7

③ 所有偶数位与身后相邻的奇数位比较交换2 1906 7

④12096年，所有奇数位与身后相邻的偶数位进行比较交换 7

⑤10269年，所有偶数与身后相邻的奇数进行比较交换 7

⑥01267与身后相邻的偶数进行比较交换 9

我们可以看到，经过五次排序，我们的数组已经完成了排序，从图中②可以看出，如果每个线程共享一个奇数位，交换是否只需要

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

最终操作代码：

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Xml.Xsl; 6  7 namespace consoleaplication 8 { 9     class Program10     {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 }