🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，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. 将这些有序子序列合并成一个大的有序序列，即不断将两个有序子序列进行合并，直到所有的子序列都被合并成一个有序序列。

在进行合并时，可以使用两个指针分别指向两个有序子序列的首元素，比较两个指针所指元素的大小，将较小的元素插入到合并后的序列中，同时移动指向这个元素的指针。重复这个过程直到两个子序列都被遍历完，然后将剩余的元素直接插入到合并后的序列的末尾即可。

时间复杂度为 O(nlogn)，是一种稳定的排序算法。

🔎2.复杂度分析

归并排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。

归并排序的主要步骤是将待排序数组不断地分成两个子数组，直到每个子数组只有一个元素，然后再将相邻的子数组合并成一个有序的数组。这个过程可以看成是一棵二叉树的结构，每一层的时间复杂度都是O(n)，而树的高度是logn，因此总的时间复杂度为O(nlogn)。

归并排序的空间复杂度也为O(n)，因为需要开辟一个与原数组长度相同的额外空间用于存储归并后的有序数组。

🔎3.应用场景

归并排序的应用场景包括但不限于以下几种:

1. 数组排序：归并排序是一种高效且稳定的排序算法，常用于对数组进行排序。
2. 大数据排序：归并排序对于大数据的排序能力优秀，可以高效地对大量数据进行排序。
3. 多路归并：将多个有序序列合并成一个有序序列时，常使用归并排序实现。
4. 外排序：归并排序适用于外部排序，即数据无法一次性全部读入内存而需要拆分成多个小文件进行排序，然后将这些有序文件进行归并。
5. 逆序对计算：使用归并排序算法可以高效地计算一个序列中逆序对的数量。

归并排序是一种高效且灵活的排序算法，在多种应用场景中均有广泛的应用。

🔎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 };

        MergeSort(array, 0, array.Length - 1);
        ShowSord(array);

        Console.ReadKey();
    }

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

    public static void MergeSort(int[] array, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            MergeSort(array, low, mid);
            MergeSort(array, mid + 1, high);
            Merge(array, low, mid, high);
        }
    }

    private static void Merge(int[] array, int low, int mid, int high) {
        int[] mergeArr = new int[high - low + 1];
        int left = low;
        int right = mid + 1;
        int merge = 0;
        while (left <= mid && right <= high) {
            if (array[left] <= array[right]) {
                mergeArr[merge++] = array[left++];
            }
            else {
                mergeArr[merge++] = array[right++];
            }
        }
        while (left <= mid) {
            mergeArr[merge++] = array[left++];
        }
        while (right <= high) {
            mergeArr[merge++] = array[right++];
        }
        merge = 0;
        while (low <= high) {
            array[low++] = mergeArr[merge++];
        }
    }

}

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