🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，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.基本思想

桶排序是一种线性排序算法，其基本思想是将数据按照一定的规则（如数值大小、字符编码等）分配到不同的桶中，再对每个桶内的数据进行排序。通常情况下，桶内的数据可以通过其他排序算法（如插入排序、快速排序）进行排序。

具体步骤如下：

1. 按照一定的规则将待排序数据分配到不同的桶中。
2. 对每个桶内的数据进行排序，可以使用其他排序算法如插入排序、快速排序。
3. 将所有桶中的数据按照顺序依次输出，形成有序序列。

桶排序的实现依赖于桶的数据结构，通常使用数组或链表来实现桶，以存储桶内的数据。桶的数量需要根据数据分布的情况来确定，通常需要通过一定的算法来估算桶的数量，以达到最优的排序效果。

🔎2.复杂度分析

桶排序是一种线性时间复杂度的排序算法，它的时间复杂度与输入数据的分布是有关系的。假设要排序的数据有 n 个，数据在桶中均匀分布，桶的数量为 k，则桶排序的时间复杂度为：

• 最好情况：所有数据落在同一个桶中，此时桶排序的时间复杂度为 O(n)。
• 最坏情况：每个桶中只有一个数据，此时桶排序的时间复杂度为 O(nlogn)，因为需要对每个桶进行一次排序。
• 平均情况：假设数据在桶中均匀分布，数据经过桶的划分后，每个桶中的数据量为 n/k。每个桶内部使用快速排序等排序算法，时间复杂度为 O((n/k)log(n/k))。因此，桶排序的平均时间复杂度为 O(n+k*(n/k)log(n/k))，即 O(n+nlog(n/k))，当 k 接近 n 时，桶排序的时间复杂度趋近于 O(n)。

桶排序的时间复杂度为 O(n)，它的空间复杂度为 O(n+k)。但是，桶排序对于数据的分布有一定的要求，如果数据的分布不均匀，桶排序的效率就会降低。

🔎3.应用场景

桶排序适用于以下场景：

1. 数据分布均匀，且取值范围已知的情况下，桶排序的效率最高；
2. 数据的取值范围比较小，可以使用桶排序来对数据进行排序；
3. 数据的取值范围较大，但数据分布比较集中，可以使用桶排序进行排序；
4. 数据量较大，但内存比较充足，可以使用桶排序来进行排序。

常见的应用场景有计数排序，求解海量数据，诸如排名（排序）、前K小/大的数据等。例如，对于年龄在0~100岁之间，且人数较多的人群进行排序时，可以采用桶排序，将数据分别放入对应的桶中，再对每个桶中的数据进行排序，最后将所有桶的数据合并起来即可得到排序结果。

🔎4.示例

/// <summary>
/// 桶排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        double[] array = { 0.43, 0.69, 0.11, 0.72, 0.28, 0.21, 0.56, 0.80, 0.48, 0.94, 0.32, 0.08 };

        BucketSort(array, 10);
        ShowSord(array);

        Console.ReadKey();
    }

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

    public static void BucketSort(double[] array, int bucketNum) {
        //创建bucket时，在二维中增加一组标识位，其中bucket[x, 0]表示这一维所包含的数字的个数
        //通过这样的技巧可以少写很多代码
        double[,] bucket = new double[bucketNum, array.Length + 1];
        foreach (var num in array) {
            int bit = (int)(10 * num);
            bucket[bit, (int)++bucket[bit, 0]] = num;
        }
        //为桶里的每一行使用插入排序
        for (int j = 0; j < bucketNum; j++) {
            //为桶里的行创建新的数组后使用插入排序
            double[] insertion = new double[(int)bucket[j, 0]];
            for (int k = 0; k < insertion.Length; k++) {
                insertion[k] = bucket[j, k + 1];
            }
            //插入排序
            StraightInsertionSort(insertion);
            //把排好序的结果回写到桶里
            for (int k = 0; k < insertion.Length; k++) {
                bucket[j, k + 1] = insertion[k];
            }
        }
        //将所有桶里的数据回写到原数组中
        for (int count = 0, j = 0; j < bucketNum; j++) {
            for (int k = 1; k <= bucket[j, 0]; k++) {
                array[count++] = bucket[j, k];
            }
        }
    }

    public static void StraightInsertionSort(double[] array) {
        //插入排序
        for (int i = 1; i < array.Length; i++) {
            double sentinel = array[i];
            int j = i - 1;
            while (j >= 0 && sentinel < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = sentinel;
        }
    }

}

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