排序算法——归并/计数/基数/桶排序

 internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 5, 7, 3, 8, 6, 9, 4, 2 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        merge_sort(arr, 1, 8);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }
     
     // 分割数组
     private static void merge_sort(int[] arr,int start,int end)
     {
         if(arr == null || start >= end)
         {
             return;
         }
         int mid = (start + end) / 2; // 取得数组中间值下标
         // 继续分割
         merge_sort(arr,start,mid);
         merge_sort(arr,mid + 1,end);
         merge(arr,start,mid,end);
     }
     
     privatr static void merge(int[] arr,int start,int mid,int end)// 1 1 2
     {
         int left = mid - start + 1; // 获得左边数组元素个数 
         int right = end - mid; // 获得右边数组元素个数 
         int leftArr = new int[left + 1]; 
         int rightArr = new int[right + 1]; 
         int i;
         for(i = 0; i < left; i++)
         {
             leftArr[i] = arr[start - 1 + i]; 
         }
         leftArr[i] = 2147483647; // 把数组最后一个元素设置为最大值
         for(i = 0; i < right; i++)
         {
             rightArr[i] = arr[mid + i];
         }
         leftArr[i] = 2147483647; // 把数组最后一个元素设置为最大值
         int j = 0;
         i = 0;
         for(int k = start; k < end; k++)
         {
             if(leftArr[i] <= rightArr[j])
             {
                 arr[k - 1] = leftArr[i];
                 i++;
             }
             else
             {
                 arr[k - 1] = rightArr[j];
                 j++;
             }
         }
     }
 }

internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 2, 4, 1, 2, 5, 3, 4, 8, 7 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        countingSort(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    private static int get_max(int[] arr)
    {
        int max = arr[0];
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
            }
        }
        return max;
    }

    private static void countingSort(int[] arr)
    {
        int length = arr.Length;
        // 找出数组中的最大值
        int max = get_max(arr);
        int[] array = new int[max + 1]; // 创建一个统计元素出现次数的数组
        int[] output = new int[length]; // 排序数组
        // 统计元素出现个数，存储在对应的位置上
        for (int i = 0; i < length; i++)
        {
            array[arr[i]]++;
        }
        // 累加出现的次数
        for (int i = 1; i < max + 1; i++)
        {
            array[i] += array[i - 1];
        }
        // 根据次数进行排序
        for (int i = 0; i < length; i++)
        {
            output[array[arr[i]] - 1] = arr[i];
            array[arr[i]]--;
        }
        // 复制到arr数组中 2, 4, 1, 2, 5, 3, 4, 8, 7
        for (int i = 0; i < length; i++)
        {
            arr[i] = output[i];
        }
    }
}

internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 121, 432, 564, 23, 1, 45, 788 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        radixSort(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    private static int getMax(int[] arr)
    {
        int max = arr[0];
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
            }
        }
        return max;
    }

    private static void countingSort(int[] arr, int place)
    {
        int length = arr.Length;
        int[] output = new int[length];

        int max = (arr[0] / place) % 10;
        for (int i = 1; i < length; i++)
        {
            if (((arr[i] / place) % 10) > max)
            {
                max = (arr[i] / place) % 10;
            }
        }

        int[] count = new int[max + 1];
        for (int i = 0; i < length; i++)
        {
            count[(arr[i] / place) % 10]++;
        }

        for (int i = 1; i < max + 1; i++)
        {
            count[i] += count[i - 1];
        }

        // 一定要从后往前排
        for (int i = length - 1; i >= 0; i--)
        {
            output[count[(arr[i] / place) % 10] - 1] = arr[i];
            count[(arr[i] / place) % 10]--;
        }

        for (int i = 0; i < length; i++)
        {
            arr[i] = output[i];
        }
    }

    private static void radixSort(int[] arr)
    {
        int max = getMax(arr);
        // 根据最高位数，从低位依次进行计数排序
        for (int i = 1; max / i > 0; i *= 10)
        {
            countingSort(arr, i);
        }
    }
}