网站设计公司有名乐云seo,室内装修设计师学什么专业,长沙优化排名,响应式网站的宽度这篇就从简单一点的一个“奇偶排序”说起吧#xff0c;不过这个排序还是蛮有意思的#xff0c;严格来说复杂度是 O(N2)#xff0c;不过在多核的情况下#xff0c;可以做到 N2 /(m/2)的效率#xff0c;这里的 m 就是待排序的个数#xff0c;当 m100#xff0c;复杂度为 N…这篇就从简单一点的一个“奇偶排序”说起吧不过这个排序还是蛮有意思的严格来说复杂度是 O(N2)不过在多核的情况下可以做到 N2 /(m/2)的效率这里的 m 就是待排序的个数当 m100复杂度为 N2 /50还行把比冒泡要好点因为重点是解决问题的奇思妙想。 下面我们看看这个算法是怎么描述的既然是奇偶肯定跟位数有关了
先将待排序数组的所有奇数位与自己身后相邻的偶数位相比较如果前者大于后者则进行交换直到这一趟结束。然后将偶数位与自己身后相邻的奇数位相比较如果前者大于后者则进行交换直到这一趟结束。重复 12 的步骤直到发现无“奇偶”“偶奇” 交换的时候就认为排序完毕此时退出循环。
① 待排序数组 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 趟排序后我们的数组就排序完毕了从图中 ② 可以看到如果每个线程分摊一个奇数位那交换是不是只要一次就够了呢可以看到这个算法在多核处理下面还是很有优势的。 最后的运行代码 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Xml.Xsl;namespace ConsoleApplication1{class Program{static void Main(string[] args){Listint list new Listint() { 9, 2, 1, 6, 0, 7 };Console.WriteLine(\n排序前 string.Join(,, list));list OddEvenSort(list);Console.WriteLine(\n排序后 string.Join(,, list));Console.Read();}static Listint OddEvenSort(Listint list){var isSorted false;//如果还没有排序完就需要继续排序知道没有交换为止while (!isSorted){//先默认已经排序完了isSorted true;//先进行 奇数位 排序for (int i 0; i list.Count; i i 2){//如果 前者 大于 后者则需要进行交换操作,也要防止边界if (i 1 list.Count list[i] list[i 1]){var temp list[i];list[i] list[i 1];list[i 1] temp;//说明存在过排序还没有排序完isSorted false;}}//再进行 奇数位 排序for (int i 1; i list.Count; i i 2){//如果 前者 大于 后者则需要进行交换操作也要防止边界if (i 1 list.Count list[i] list[i 1]){var temp list[i];list[i] list[i 1];list[i 1] temp;//说明存在过排序还没有排序完isSorted false;}}}return list;}}}
