快捷導(dǎo)航

C#實現(xiàn)奇偶排序的示例代碼

更新時間：2023年11月27日 14:31:21 作者：神仙別鬧

奇偶排序是一種簡單的排序算法,該算法通過比較并交換相鄰的元素來完成排序,本文主要介紹了C#實現(xiàn)奇偶排序的示例代碼,具有一定的參考價值,感興趣的可以了解一下

這篇就從簡單一點的一個“奇偶排序”說起吧，不過這個排序還是蠻有意思的，嚴格來說復(fù)雜度是 O(N2)，不過在多核的情況下，可以做到 N2 /(m/2)的效率，這里的 m 就是待排序的個數(shù)，當 m=100，復(fù)雜度為 N2 /50，還行把，比冒泡要好點，因為重點是解決問題的奇思妙想。
下面我們看看這個算法是怎么描述的，既然是奇偶，肯定跟位數(shù)有關(guān)了

先將待排序數(shù)組的所有奇數(shù)位與自己身后相鄰的偶數(shù)位相比較，如果前者大于后者，則進行交換，直到這一趟結(jié)束。
然后將偶數(shù)位與自己身后相鄰的奇數(shù)位相比較，如果前者大于后者，則進行交換，直到這一趟結(jié)束。
重復(fù) 1，2 的步驟，直到發(fā)現(xiàn)無“奇偶”，“偶奇” 交換的時候，就認為排序完畢，此時退出循環(huán)。

① 待排序數(shù)組： 9 2 1 6 0 7
② 所有奇數(shù)位與身后的相鄰的偶數(shù)位比較交換 2 9 1 6 0 7
③ 所有偶數(shù)位與身后的相鄰的奇數(shù)位比較交換 2 1 9 0 6 7
④ 所有奇數(shù)位與身后的相鄰的偶數(shù)位比較交換 1 2 0 9 6 7
⑤ 所有偶數(shù)位與身后的相鄰的奇數(shù)位比較交換 1 0 2 6 9 7
⑥ 所有奇數(shù)位與身后的相鄰的偶數(shù)位比較交換 0 1 2 6 7 9

我們可以看到，經(jīng)過 5 趟排序后，我們的數(shù)組就排序完畢了，從圖中 ② 可以看到，如果每個線程分攤一個奇數(shù)位，那交換是不是只要一次就夠了呢，可以看到這個算法在多核處理下面還是很有優(yōu)勢的。
最后的運行代碼：

 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)
         {
             List<int> list = new List<int>() { 9, 2, 1, 6, 0, 7 };
 
             Console.WriteLine("\n排序前 => " + string.Join(",", list));
 
             list = OddEvenSort(list);
 
             Console.WriteLine("\n排序后 => " + string.Join(",", list));
 
             Console.Read();
         }
 
         static List<int> OddEvenSort(List<int> list)
         {
             var isSorted = false;
 
             //如果還沒有排序完，就需要繼續(xù)排序，知道沒有交換為止
             while (!isSorted)
             {
                 //先默認已經(jīng)排序完了
                 isSorted = true;
 
                 //先進行 奇數(shù)位 排序
                 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;
                     }
                 }
 
                 //再進行 奇數(shù)位 排序
                 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;
         }
     }
 }