日期：2023年 02月 18日

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

摘要：演算法-排序

第一部分：計數排序 - 介紹

Step 1：原理

不需要排序的一種排序，先找出陣列中最大值，然後得到一組空間Space。
遍歷該陣列，將值放入對應的Space[Index] 中累進+1
最後再遍歷Space全部，由小到大有多少計數就添加該索引到結果中。
應用：適用於輸入數組小的情境，否則會浪費大量記憶體空間

Step 2：演算法流程圖

第二部分：圖解範例說明

Step 1：以整數陣列為例

初始內有3個值，找出最大值，配置O(k)的空間
遍歷輸入陣列O(n) 添加到額外空間 k 陣列中
最後再遍歷額外空間O(k)，將大於0的索引位置取出，組成排序結果

第三部分：代碼

Step 1：計數排序代碼 - 呼叫進入點

串入一組數列 inputItem 求出 result

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

Step 2：計數排序代碼 - 主程式

主要三個流程
1. 配置空間
2. 計數
3. 組成

public class CountingSort
{
    public List<int> CountingAsedingSort(List<int> items)
    {
        //1. 配置元素最大值的空間 O(k)
        int maxValue = (dynamic)items.Max() + 1;
        var extraSpace = new List<int>();
        for (int index = 0; index < maxValue; index++)
        {
            extraSpace.Add(0);
        }
        //2. 遍歷找出空間 O(n)
        for (int index = 0; index < items.Count; index++)
        {
            extraSpace[items[index]] += 1;
        }
        //3. 將值組成最後的結果由小到大
        items.Clear();
        for (int index = 0; index < extraSpace.Count; index++)
        {
            while (extraSpace[index] > 0)
            {
                items.Add(index);
                extraSpace[index]--;
            }
        }
        return items;
    }
}