快捷導(dǎo)航

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

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

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

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

先將待排序數(shù)組的所有奇數(shù)位與自己身后相鄰的偶數(shù)位相比較，如果前者大于后者，則進(jìn)行交換，直到這一趟結(jié)束。
然后將偶數(shù)位與自己身后相鄰的奇數(shù)位相比較，如果前者大于后者，則進(jìn)行交換，直到這一趟結(jié)束。
重復(fù) 1，2 的步驟，直到發(fā)現(xiàn)無(wú)“奇偶”，“偶奇” 交換的時(shí)候，就認(rèn)為排序完畢，此時(shí)退出循環(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)過(guò) 5 趟排序后，我們的數(shù)組就排序完畢了，從圖中 ② 可以看到，如果每個(gè)線程分?jǐn)傄粋€(gè)奇數(shù)位，那交換是不是只要一次就夠了呢，可以看到這個(gè)算法在多核處理下面還是很有優(yōu)勢(shì)的。
最后的運(yùn)行代碼：

 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;
 
             //如果還沒(méi)有排序完，就需要繼續(xù)排序，知道沒(méi)有交換為止
             while (!isSorted)
             {
                 //先默認(rèn)已經(jīng)排序完了
                 isSorted = true;
 
                 //先進(jìn)行 奇數(shù)位 排序
                 for (int i = 0; i < list.Count; i = i + 2)
                 {
                     //如果 前者 大于 后者，則需要進(jìn)行交換操作,也要防止邊界
                     if (i + 1 < list.Count && list[i] > list[i + 1])
                     {
                         var temp = list[i];
                         list[i] = list[i + 1];
                         list[i + 1] = temp;
 
                         //說(shuō)明存在過(guò)排序，還沒(méi)有排序完
                         isSorted = false;
                     }
                 }
 
                 //再進(jìn)行 奇數(shù)位 排序
                 for (int i = 1; i < list.Count; i = i + 2)
                 {
                     //如果 前者 大于 后者，則需要進(jìn)行交換操作，也要防止邊界
                     if (i + 1 < list.Count && list[i] > list[i + 1])
                     {
                         var temp = list[i];
                         list[i] = list[i + 1];
                         list[i + 1] = temp;
 
                         //說(shuō)明存在過(guò)排序，還沒(méi)有排序完
                         isSorted = false;
                     }
                 }
             }
 
             return list;
         }
     }
 }