🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。

🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。

🏆🎉欢迎 👍点赞✍评论⭐收藏

🚀前言

排序算法是一种将一组数据按照特定的规则进行排列的方法。排序算法通常用于对数据的处理，使得数据能够更容易地被查找、比较和分析。

下面是常见的11种排序算法：

1. 冒泡排序（Bubble Sort）：比较相邻的元素，如果前面的元素大于后面的元素，就交换这两个元素的位置。时间复杂度为O(n^2)。
2. 选择排序（Selection Sort）：在未排序的数据中找到最小（大）的元素，放置在已排序的数据末尾。时间复杂度为O(n^2)。
3. 插入排序（Insertion Sort）：将未排序的元素插入到已排序的序列中，时间复杂度为O(n^2)。
4. 希尔排序（Shell Sort）：希尔排序是插入排序的一种改进，它将原序列分割成若干个子序列，对每个子序列进行插入排序，最后对整个序列进行插入排序。时间复杂度为O(nlogn)。
5. 二路归并排序（Merge Sort）：二路归并排序是指将一个序列分成两个子序列，分别对两个子序列进行归并排序，然后将排序好的两个子序列合并成一个有序序列的过程。这种排序思想采用了分治算法的思想，排序效率较高，时间复杂度为 O(nlogn)。
6. 快速排序（Quick Sort）：选择一个基准元素，将大于基准元素的数放在一边，小于基准元素的数放在另一边，递归执行该过程，最后得到有序序列。时间复杂度为O(nlogn)。
7. 堆排序（Heap Sort）：将序列转换为一个大根堆，每次将堆顶元素与堆底元素交换，然后将剩余元素重新构建堆，重复执行该过程，最后得到有序序列。时间复杂度为O(nlogn)。
8. 计数排序（Counting Sort）：统计小于等于每个元素的个数，再依次计算出每个元素在有序序列中的位置。时间复杂度为O(n+k)，其中k为最大元素值。
9. 桶排序（Bucket Sort）：将元素分到多个桶中，对每个桶进行排序，最后将所有桶中的元素按顺序合并起来。时间复杂度为O(n)。
10. 基数排序（Radix Sort）：按照低位到高位的顺序对元素进行排序，依次排序后得到有序序列。时间复杂度为O(dn)，其中d为元素的位数。
11. 多路归并排序：多路归并排序是指将一个序列分成多个子序列，然后对每个子序列进行排序，最后将排好序的子序列合并成一个有序序列的过程。多路归并排序的时间复杂度不仅取决于序列长度，还取决于子序列个数。多路归并排序的优点是可以对比二路归并排序更加高效地利用计算机的多核心处理能力，因此在大规模数据处理中有广泛的应用。

🚀一、桶排序

🔎1.基本思想

基数排序（radix sort）是一种非比较排序算法，它的基本思想是按照每个数位上的数字进行排序。具体来说，在所有待排序数中，先按照个位数进行排序，然后按照十位数进行排序，再按照百位数进行排序，直到按照最高位排序完成为止。每一轮排序都会将待排序数按照某一位上的数字分配到不同的桶中，然后根据桶的顺序重新排列待排序数。最终完成所有数位的排序后，待排序数将被有序地排列。由于基数排序的时间复杂度与待排序数的位数有关，因此适用于位数较少的情况。

🔎2.复杂度分析

基数排序是一种非比较排序算法，它利用数值的位数来对数据进行排序。基数排序的时间复杂度是O(d*(n+k))，其中d是最大数的位数，n是待排序元素个数，k是基数（对于十进制数k=10）。

在基数排序中，需要进行d次排序，每次排序都要使用计数排序等线性时间复杂度的排序算法。每次排序需要遍历n个数，且每次排序中的计数排序需要开辟k个桶来存储数据，因此基数排序的时间复杂度是O(d*(n+k))。

在空间复杂度方面，基数排序需要开辟k个桶来存储数据，因此空间复杂度是O(n+k)。

基数排序的时间复杂度非常优秀，且不受数据分布的影响，但是它也有一些缺点，比如对于大数值范围和位数较多的数据，排序时间会非常长，同时需要大量的额外存储空间来存储桶。

🔎3.应用场景

基数排序常用于对数字或字符串进行排序，其应用场景包括：

1. 大数据量的排序：基数排序可以处理大量数据的排序，因为它不需要将整个数据集加载到内存中，而只需要逐位比较排序。
2. 数字排序：基数排序对于数字排序特别有效，可以在线性时间内完成排序，而非像快速排序和归并排序那样在最坏情况下需要 O(nlogn) 的时间复杂度。
3. 字符串排序：由于字符串也可以被看作数字序列，因此基数排序在字符串排序中也很有效。例如，可以使用基数排序对英文单词进行排序。
4. 计数排序的优化：可以对计数排序进行优化，通过使用基数排序来解决计数排序中的内存问题和性能问题。在对计数排序的计数过程中，如果数组非常大，会导致内存问题。对于这种情况，可以使用基数排序将大型数组分成小块，然后在每个块上运行计数排序。

🔎4.示例

/// <summary>
/// 基数排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };

        RadixSort(array, 10);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(int[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    public static void RadixSort(int[] array, int bucketNum) {
        int maxLength = MaxLength(array);
        //创建bucket时，在二维中增加一组标识位，其中bucket[x, 0]表示这一维所包含的数字的个数
        //通过这样的技巧可以少写很多代码
        int[,] bucket = new int[bucketNum, array.Length + 1];
        for (int i = 0; i < maxLength; i++) {
            foreach (var num in array) {
                int bit = (int)(num / Math.Pow(10, i) % 10);
                bucket[bit, ++bucket[bit, 0]] = num;
            }
            for (int count = 0, j = 0; j < bucketNum; j++) {
                for (int k = 1; k <= bucket[j, 0]; k++) {
                    array[count++] = bucket[j, k];
                }
            }
            //最后要重置这个标识
            for (int j = 0; j < bucketNum; j++) {
                bucket[j, 0] = 0;
            }
        }
    }

    private static int MaxLength(int[] array) {
        if (array.Length == 0) return 0;
        int max = array[0];
        for (int i = 1; i < array.Length; i++) {
            if (array[i] > max) max = array[i];
        }
        int count = 0;
        while (max != 0) {
            max /= 10;
            count++;
        }
        return count;
        //return (int)Math.Log10(max) + 1;
    }

}

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！