算法實例-C#邮箱排序-PigeonHoleSort

# 算法实例 #

排序算法Sort

信箱排序PigeonHoleSort

https://en.wikipedia.org/wiki/Pigeonhole_sort

算法說明

1.信箱算法使用一個完整的序列來存放排序後的數據2.我們常用的序列是不連續的,{2,3,5,2}中間缺少了元素{4},而信箱算法的存放序列是連續的我們如果以最小的元素{2}來定位,每個位置只是表示其有多少個相同的元素那麼{2,3,5,2}可以表示成{2,1,0,1}[即連續空間中有兩個2,壹個3,零個4,壹個5]3.該算法的問題在於,先要知道最大數和最小數.4.如果不知道最大數和最小數,使用該算法將會有額外的開銷用於尋找最大和最小數.5.由於是需要連續空間的存放,所以算法只支持int類型,不然創造的連續空間長度不可控.

算法步驟

1.找到序列中的最大和最小數2.確定完整空間大小size=max-min+13.計算每個信箱格的元素個數4.去掉完整序列的零個數元素,生成排序后的非完整序列.

代碼示例
https://github.com/aalhour/C-Sharp-Algorithms/blob/master/Algorithms/Sorting/PigeonHoleSorter.cs

/// <summary>/// Only support IList<int> Sort/// Also called CountSort (not CountingSort)/// </summary>public static class PigeonHoleSorter{    public static void PigeonHoleSort(this IList<int> collection)    {        collection.PigeonHoleSortAscending();    }    public static void PigeonHoleSortAscending(this IList<int> collection)    {        int min = collection.Min();        int max = collection.Max();        int size = max - min + 1;        int[] holes = new int[size];        foreach (int x in collection)        {            holes[x - min]++;        }                int i = 0;        for (int count = 0; count < size; count++)        {            while (holes[count]-- > 0)            {                collection[i] = count + min;                i++;            }        }        }    public static void PigeonHoleSortDescending(this IList<int> collection)    {        int min = collection.Min();        int max = collection.Max();        int size = max - min + 1;        int[] holes = new int[size];        foreach (int x in collection)        {            holes[x - min]++;        }        int i = 0;        for (int count = size-1; count >= 0; count--)        {            while (holes[count]-- >0)            {                collection[i] = count + min;                i++;            }        }    }}

測試用例

    [TestMethod]    public void TestMethod2()    {        List<int> list = new List<int>() { 23, 42, 4, 16, 8, 23, 15, 3, 9, 55, 0, 23, 34, 12, 2, 46, 25, 25 };        list.PigeonHoleSort();    }

算法構造的完整序列