日期：2023年 02月 27日

標籤： Algorithm Sort Paractical Algorithm C# Asp.NET Core

摘要：演算法-排序

第一部分：桶子排序 - 介紹

Step 1：原理

給定一組可比較陣列，遍歷
1. 將一組可比較數列輸入
2. 求出該數列最大值與最小值
3. 決定桶子數量，決定每個桶子的區間 => (最大值-最小值) / 桶子數 = 每個桶子區間
4. 遍歷輸入的所有元素，放進對應的桶子
5. 所有桶子各自排序 (Quick sort O(nlong) 可參考Quick Sort 排序演算法)
6. 最後合併的桶子將會由小至大的排序結果

Step 2：演算法流程圖

第二部分：圖解範例說明

Step 1：以整數陣列為例

初始內有6個值

第三部分：代碼

Step 1：桶子排序代碼 - 呼叫進入點

輸入一組數列 inputItem 求出 result

public void Execute()
{
    List<int> inputItem = new() { 92, 17, 38, 59, 26, 39 };
    var execute = new BucketSort<int>();
    execute.BuckAscendingSorting(inputItem);
}

Step 2：桶子排序代碼 - 主程式

主要三個流程
1. 決定每個桶子放的區間
2. 將所有值放進對應的桶子內
3. 所有桶子內排序 + 組成所有桶子排序後的結果

public class BucketSort<T> where T : IComparable, IConvertible
{
    private readonly static int _bucketCount = 10;
    public List<T> BuckAscendingSorting(List<T> items)
    {
        //1. 決定每個桶子放的區間
        var min = (dynamic)items.Min();
        var bucketSize = GetRegionSize(ref items);
        var buckets = new List<List<T>>();
        for (int index = 0; index < _bucketCount; index++)
            buckets.Add(new List<T>());
        //2. 將所有值放進對應的桶子內
        for (int index = 0; index < items.Count; index++)
        {
            var value = Convert.ToInt32(items[index]) - min;
            var putIndex = (value / bucketSize - 1) < 0 ? 0 : (value / bucketSize - 1);
            buckets[putIndex].Add(items[index]);
        }          
        //3. 所有桶子內排序 + 組成所有桶子排序後的結果
        items.Clear();
        foreach (var bucketItem in buckets)
        {
            //Quick sort 排序每個桶子 耗費 O( k * nlogn)
            bucketItem.Sort();
            items.AddRange(bucketItem);
        }
        return items;
    }
    private int GetRegionSize(ref List<T> items)
    {
        try
        {
            var max = items.Max();
            var min = items.Min();
            return ((dynamic)max - (dynamic)min) / _bucketCount;
        }
        catch (Exception ex)
        {
            return 0;
        }
    }
}