深入解析：C语言中的八大经典排序算法全揭秘

排序的概念及运用

排序概念

排序运用

常见排序算法

八大排序详解

直接插入排序

基本思想

代码实现

希尔排序

基本思想

代码实现

选择排序

基本思想

代码实现

堆排序

堆的向下调整算法（前提）

基本思想

代码实现

冒泡排序

基本思想

代码实现

快速排序

基本思想

1. Hoare版本

2. 挖坑法

3. 前后指针法

代码实现

递归实现

非递归实现

归并排序

基本思想

代码实现

递归实现

非递归实现

计数排序

基本思想

代码实现

排序的概念及运用

排序概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序运用

给你一串数据，我们可以按照一些条件将数据按照递增或者递减的方式进行排列，比如计算机里面的文件：

排序算法是计算机科学的基础工具，广泛应用于数据管理、信息检索、数据分析等领域，通过高效排列数据，提升系统性能和用户体验。

常见排序算法

八大排序算法通常指的是以下这些经典的排序方法：

直接插入排序：逐步将元素插入到已排序序列中的适当位置。
希尔排序：基于插入排序，通过增量分组策略改进，先使数据部分有序，再进行插入排序。
选择排序：每轮找出剩余元素中的最小（或最大）元素，放到已排序序列的末尾。
堆排序：利用完全二叉树的特性，将数据构造成一个大顶堆或小顶堆，然后交换堆顶元素与末尾元素，调整堆结构，达到排序目的。
冒泡排序：重复遍历数组，比较相邻元素并在必要时交换，使得较大的元素逐渐移向数组末端。
快速排序：采用分治法，选取一个基准元素，将数组分成两部分，一部分都比基准小，另一部分都比基准大，然后递归地对这两部分继续排序。
归并排序：递归地将数组分成两半分别排序，然后将两个有序数组合并成一个有序数组。
计数排序：是一种非比较排序算法，适用于一定范围内的整数排序，特别是当输入数据的范围不是很大时非常有效。

这些算法各有特点，适用于不同的应用场景，选择合适的排序算法可以提高程序的效率。以上所有排序都属于内部排序。

八大排序详解

直接插入排序

动图演示：

基本思想

核心在于将一个未排序的序列看作是两部分：已排序的部分和未排序的部分。初始时，已排序部分只包含序列的第一个元素，未排序部分包含剩余的所有元素。算法通过逐个从未排序部分取出元素，将其插入到已排序部分的适当位置，以此方式逐步扩大已排序部分，直至整个序列变得有序。

具体步骤如下：

初始化：假设第一个元素已经被排序。
遍历未排序部分：从第二个元素开始，每次取出一个元素，记为key。
比较并移动：将key与已排序部分的元素从后向前比较，如果key小于正在比较的元素，则将该元素向后移动一位，为key腾出位置。这个过程一直持续到找到一个小于或等于key的元素，或者key移动到了已排序部分的起始位置。
插入：将key插入到找到的合适位置。
重复步骤2-4：直到未排序部分的所有元素都被取出并插入到已排序部分中。

代码实现

// 函数定义：使用直接插入排序算法对整型数组a进行排序，n为数组的元素个数
void InsertSort(int* a, int n)
{
    int i = 0;

    // 外层循环：遍历数组中的每一个元素，除了最后一个，因为后面没有元素需要和它比较了
    for (i = 0; i < n - 1; i++)
    {
        int end = i; // 初始化已排序部分的最后一个元素的索引
        int tmp = a[end + 1]; // 暂存未排序部分的第一个元素，准备将其插入到已排序部分

        // 内层循环：将tmp与已排序部分的元素从后往前比较，找到tmp的正确位置
        while (end >= 0)
        {
            // 如果暂存的元素小于当前比较的已排序元素，则将该元素后移一位，为tmp腾位置
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--; // 继续与前一个元素比较
            }
            else
            {
                // 找到了tmp应该插入的位置，跳出循环
                break;
            }
        }

        // 将tmp插入到正确的位置
        a[end + 1] = tmp;
    }
}

时间复杂度:

最好情况（输入数组已经是排序状态）：

        O(n)，因为此时不需要内部的while循环，每个元素只需比较一次即可确认其位置。

最坏情况（输入数组是逆序的或是随机分布，需要大量的交换操作）：

        O(n^2)，每插入一个新元素都要与它之前的元素比较，比较和移动的总次数大约为n(n-1)/2。

平均情况：

        也是O(n^2)，考虑到随机数据情况下，每次插入操作平均需要比较和移动大约n/2次。

空间复杂度：

        O(1)，因为直接插入排序是原地排序算法，除了输入数组外，只需要常数个额外的变量（如本例中的i, end, tmp）来辅助完成排序，所以空间复杂度为常量阶。

希尔排序

图片演示：

基本思想

将直接插入排序算法通过增量（或称为间隔）的概念进行改进，以此来提高排序效率。具体步骤如下：

选择增量：首先选择一个增量gap，通常开始时gap会设置为数组长度的一半，然后逐渐减小这个增量（比如每次减半），直到gap为1。
分组排序：将整个数组分成多个子序列，每个子序列包含相距gap个元素的项。然后，对每个子序列应用直接插入排序算法。由于子序列中的元素相隔较远，这种插入排序能较快地将部分元素移至其最终位置，即使整个序列还不完全有序。
减小增量：重复上述过程，但每次减小gap的值（常见的做法是除以2，直到gap为1）。随着gap的减小，子序列越来越短，直到每个子序列只包含一个元素，这时实际上就是整个序列进行直接插入排序。
最终排序：当gap减至1时，整个数组几乎已经是部分有序状态，此时进行最后一次直接插入排序，可以高效地完成排序，因为大部分元素已经在正确的位置附近。

代码实现

// 函数定义：使用希尔排序算法对整型数组a进行排序，n为数组的元素个数
void ShellSort(int* a, int n)
{
    int gap = n; // 初始化增量为数组长度，之后逐步减小

    // 当增量大于1时，继续执行以下循环
    while (gap > 1)
    {
        gap = gap / 2; // 每次循环将增量缩小一半，直至为1
        
        int i = 0;

        // 对当前增量gap，进行直接插入排序
        for (i = 0; i < n - gap; i++) // 遍历数组，跳过gap步长的元素
        {
            int end = i; // 记录待插入元素的前一个位置
            int tmp = a[end + gap]; // 暂存待插入的元素值
            
            // 插入排序逻辑，将tmp插入到左侧已排序的子序列中正确的位置
            while (end >= 0) 
            {
                // 若tmp小于其前面的元素，则将该元素后移，为tmp腾位置
                if (tmp < a[end]) 
                {
                    a[end + gap] = a[end];
                    end -= gap; // 继续检查前一个元素
                }
                else
                {
                    // 找到tmp的正确插入位置，退出循环
                    break;
                }
            }
            // 将tmp放入最终确定的位置
            a[end + gap] = tmp;
        }
    }
}

时间复杂度:

最好情况和平均情况：

时间复杂度依赖于所选择的间隔序列（增量序列）。对于某些特别设计的增量序列希尔排序可以达到较好的平均时间复杂度，大约为O(n^1.3)至O(n^1.5)。增量序列的选择是为了尽量减少数据的逆序程度，从而提高排序效率。

最坏情况：

时间复杂度通常是O(n^2)，这发生在增量序列选择不当，导致数组排序效率低下的情况下。

空间复杂度：

希尔排序是原地排序算法，除了数组本身外，它只需要少量的额外空间（例如用于交换和计算的临时变量），因此其空间复杂度为O(1)。

选择排序

动图演示：

基本思想

核心是在未排序的序列中找到最小（或最大）的元素，将其放到序列的起始位置，然后再从剩余未排序的元素中寻找下一个最小（或最大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

具体步骤如下：

初始化：假定序列中的第一个元素是最小（或最大）元素，此元素可以认为已经被排序。
遍历未排序部分：从数组的第二个元素开始，遍历数组中未排序的部分。
查找最小（或最大）值：在未排序的元素中寻找最小（或选择最大值排序则寻找最大）的元素。
交换：将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。此时，未排序部分的第一个元素被认为是已排序的。
重复步骤2-4：缩小未排序部分的范围，重复执行步骤2至步骤4，直到整个序列变为有序。

代码实现

// 函数定义：使用选择排序算法对整型数组a进行排序，n为数组的元素个数
void SelectSort(int* a, int n)
{
    int i = 0;

    // 外层循环：遍历数组中的每一个元素
    for (i = 0; i < n; i++)
    {
        int start = i; // 初始化最小值的索引为当前下标i
        int min = start; // 记录当前已知的最小值元素的索引
        
        // 内层循环：从当前元素开始向后寻找更小的元素
        while (start < n)
        {
            // 如果找到更小的元素，则更新min为该元素的索引
            if (a[start] < a[min])
                min = start;
            start++; // 继续向后比较
        }
        
        // 将找到的最小值与当前位置i处的元素交换
        Swap(&a[i], &a[min]);
    }
}

时间复杂度：

选择排序的时间复杂度为O(n^2)。

这是因为算法包括两个嵌套循环：外层循环遍历数组中的每个元素（共n次），内层循环负责寻找剩余未排序部分中的最小元素（最坏情况下需比较n-i次，其中i是外层循环的迭代次数）。因此，总操作次数约为n*(n-1)/2次比较和n次交换，故无论在最好、最坏还是平均情况下，时间复杂度均为O(n^2)。

空间复杂度：

选择排序的空间复杂度为O(1)。

这是因为它是一种原地排序算法，除了用于交换的临时变量外，不使用任何额外的存储空间。因此，其对内存的需求与输入数据的规模无关，属于常数级空间复杂度。

堆排序

学习堆排序，首先要学习堆的向下调整算法，因为要用堆排序，你首先得建堆，而建堆需要执行多次堆的向下调整算法。

堆的向下调整算法（前提）

堆的向下调整算法（使用前提）：
若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

向下调整算法的基本思想（以建大堆为例）：
        1.从根结点处开始，选出左右孩子中值较大的孩子。
        2.让大的孩子与其父亲进行比较。
                若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
                若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。

向下调整算法的代码实现：

// 函数定义：调整数组a中以root为根的堆（默认为大顶堆），使其满足堆性质，n表示数组大小
void AdjustDown(int* a, int n, int root)
{
    int parent = root; // 初始化父节点为当前调整的根节点
    int child = 2 * parent + 1; // 初始化左孩子节点的索引

    // 当孩子节点的索引小于数组长度时，进入循环
    while (child < n)
    {
        // 检查右孩子是否存在且是否大于左孩子，如果是，则选取右孩子作为较大的孩子节点
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }

        // 如果孩子节点的值大于父节点的值，则交换它们，以维护大顶堆的性质
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]); // 交换操作
            parent = child; // 更新父节点为当前的孩子节点，继续向下调整
            child = 2 * parent + 1; // 更新孩子节点为新的父节点的左孩子
        }
        else
        {
            // 如果无需交换，说明以parent为根的子树已经是大顶堆，结束循环
            break;
        }
    }
}

要将一个任意树调整为堆，只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整。

基本思想

利用堆这种特殊数据结构设计的排序算法，其基本思想可以概括为以下几个步骤：

构建初始堆：将待排序的序列构造成一个大顶堆（若要升序排序）或小顶堆（若要降序排序）。在这个过程中，从最后一个非叶子节点开始，对每个非叶子节点执行“下沉”操作，确保每个子树满足堆的性质，最终整个序列变成一个大顶堆或小顶堆。在这个堆中，序列的最大值（大顶堆）或最小值（小顶堆）位于堆顶。

交换并调整：将堆顶元素（即当前最大或最小值）与序列末尾的元素交换，这样就把当前的最大（或最小）元素放到了正确的位置。然后，减小堆的大小（因为最后一个元素已经是有序的了），忽略刚才交换到末尾的元素，对剩下的元素重复步骤1，再次调整剩余元素构成堆。

重复上述过程：不断重复步骤2，每次交换后都会得到一个新的最大（或最小）元素，并将其放在序列的正确位置上。直到整个序列变为有序。

代码实现

// 函数定义：使用堆排序算法对整型数组a进行排序，n为数组的元素个数
void HeapSort(int* a, int n)
{
    int i = 0;

    // 构建初始大顶堆
    // 从最后一个非叶子节点开始，向前遍历至根节点，对每个节点执行"下沉"操作
    for (i = (n - 1 - 1) / 2; i >= 0; i--) // 注意：最后一个非叶子节点的索引为 (n-1)/2 的向下取整
    {
        AdjustDown(a, n, i); // 调用AdjustDown函数调整以i为根的子树为大顶堆
    }

    int end = n - 1; // 初始化end为数组最后一个元素的索引

    // 排序过程
    while (end) // 当end不为0时，继续循环
    {
        // 将堆顶元素（当前最大值）与数组末尾元素交换，保证最大值位于正确位置
        Swap(&a[0], &a[end]);

        // 交换后，减小堆的大小（忽略已排序的最大值），对剩下的元素重新调整为大顶堆
        AdjustDown(a, end, 0); // 注意：此时只需在前end个元素中调整堆

        end--; // 缩小排序范围，准备下一次交换
    }
}

时间复杂度：

堆排序的时间复杂度为O(n log n)。

具体来说，构建初始堆的过程时间复杂度为O(n)，因为每个节点最多下沉一次，总共需要至多n次操作。调整堆和交换顶部元素的过程需要重复n-1次，每次调整的时间复杂度为O(log n)，因此这部分的总时间复杂度为O(n log n)。将这两部分相加，整体的时间复杂度仍为O(n log n)，且这个复杂度在最好、最坏和平均情况下都保持不变。

空间复杂度：

空间复杂度为O(1)。

堆排序是一种原地排序算法，除了用于交换元素的少量临时变量外，不需要额外的存储空间。

冒泡排序

动图演示：

基本思想

通过重复遍历要排序的数列，比较相邻元素的值，如果顺序错误（比如在升序排序中，前一个元素大于后一个元素），就交换它们的位置。这个过程重复进行，直到没有再需要交换的元素为止，这时数列就已经排序完成。该算法得名于较小的元素会像水泡一样逐渐“浮”到数列的顶端。

具体步骤如下：

遍历数组：从数组的第一个元素开始，比较相邻的两个元素。
交换位置：如果前一个元素大于后一个元素（升序排列的情况下），就交换它们的位置。这样，每一轮遍历结束后，最大的元素会被“冒泡”到数组的末尾。
重复过程：对除了已经排好序的末尾元素之外的所有元素重复上述过程，直到整个数组排序完成。

代码实现

// 函数定义：使用冒泡排序算法对整型数组a进行排序，n为数组的元素个数
void BubbleSort(int* a, int n)
{
    int end = 0; // 初始化end为数组最后一个元素的索引

    // 主循环，控制遍历数组的轮次
    for (end = n - 1; end >= 0; end--) // 每轮结束后，已排序的元素范围扩大，因此end递减
    {
        int exchange = 0; // 初始化exchange标志，用于记录本轮遍历是否有发生交换
        int i = 0;

        // 内层循环，负责具体比较和交换相邻元素
        for (i = 0; i < end; i++) // 只需比较到end前的元素，因为end位置的元素自然就是这一轮的最大值
        {
            if (a[i] > a[i + 1]) // 如果当前元素大于下一个元素（升序排列条件）
            {
                Swap(&a[i], &a[i + 1]); // 交换这两个元素的位置
                exchange = 1; // 发生了交换，设置exchange为1
            }
        }

        // 优化：如果某轮遍历中没有发生交换，说明数组已经完全有序，提前结束排序
        if (exchange == 0)
            break;
    }
}

时间复杂度：

最好情况（数组已经是有序）：

此时外层循环只执行一次，内层循环也只需遍历一次即可发现无须交换，因此时间复杂度为O(n)。

最坏和平均情况：

需要进行完整的n-1轮遍历，每轮遍历中进行n-i次比较（i从0开始递增），因此总比较次数大约为n*(n-1)/2。所以，最坏和平均情况下的时间复杂度为O(n^2)。

空间复杂度：

该冒泡排序实现是原地排序，除了用于交换的临时变量外，不需要额外的存储空间，因此空间复杂度为O(1)。这意味着它是就地排序，空间效率高。

快速排序

基本思想

基本思想基于分治法策略。

具体步骤如下：

选取基准值（Pivot）：从数组中挑选一个元素作为基准值。这个基准值的选择可以是数组的第一个元素、最后一个元素、中间元素或者通过某种策略随机选择，但选择的不同会影响排序的性能。

分区（Partition）：重新排列数组，所有小于基准值的元素放在基准值之前，所有大于基准值的元素放在基准值之后。经过这一步骤后，基准值就位于数组的中间位置，这个位置称为“枢轴点”。这个操作称为“分区”操作，是快速排序算法中最关键的部分。

递归排序子数组：递归地对基准值左右两侧的子数组（即基准值前的子数组和基准值后的子数组）重复上述两个步骤。递归的终止条件是子数组只剩下一个或零个元素，这时可以认为子数组已经排序完成。

快速排序的三种常见实现方法包括Hoare版本、挖坑法、以及前后指针法，下面是这些方法的基本概念和简要说明：

1. Hoare版本

这是快速排序最原始的实现方式，由Tony Hoare在1960年代初提出。在Hoare版本中，算法首先选择一个基准值（通常选择数组的第一个元素），然后定义两个指针，一个从前向后扫描，一个从后向前扫描。这两个指针会在数组中移动，直到它们相遇或交错。从前向后扫描的指针寻找大于基准值的元素，从后向前扫描的指针寻找小于基准值的元素，一旦找到就交换这两个元素的位置。当指针交错时，分区完成，基准值被放置在其最终的排序位置上，此时基准值左边的元素都小于它，右边的元素都大于它。之后，对基准值两边的子数组递归地应用同样的过程。

2. 挖坑法

挖坑法也是快速排序的一种实现，它的特点是直接将基准值（通常选择第一个元素）拿出来作为“坑”，然后从数组的剩余部分开始遍历，找到适合填入这个“坑”的元素（即小于基准值的元素填入，如果在降序排序中则为大于基准值的元素），并将这个元素挖出来填入“坑”中，原位置形成新的“坑”，继续这个过程，直到遍历完整个数组。最后将最初的基准值填入最后一个挖出的“坑”中。这种方法避免了直接交换元素，而是通过移动元素来达到排序的目的，但其实质仍然是进行分区操作。

3. 前后指针法

前后指针法是另一种实现快速排序分区的方式，它的基本思想与Hoare版本类似，但具体实现细节有所区别。在前后指针法中，通常选择数组的第一个元素作为基准值，并将其移出数组。然后定义两个指针，一个在数组的开头（前指针），一个在数组的末尾（后指针）。前指针寻找大于基准值的元素，后指针寻找小于基准值的元素，一旦找到就交换这两个元素。这个过程一直进行，直到两个指针相遇，然后将基准值放回相遇点，使得相遇点左边的元素都不大于基准值，右边的元素都不小于基准值。接下来，对这两部分分别递归地进行排序。

这三种方法的核心都是通过一趟遍历将数组划分为两个部分，并递归地对这两部分继续排序，从而达到整个数组排序的目的。不同的方法在基准值的选择和指针移动策略上有所差异，但都遵循快速排序的基本思想。

代码实现

递归实现

1.Hoare版本

// 快速排序的Hoare版本实现
void QuickSort1(int* a, int begin, int end)
{
    if (begin >= end) // 基准情形：如果区间开始索引大于等于结束索引，说明区间内只有一个元素或没有元素，无需排序，直接返回
        return;

    int left = begin; // 左指针初始化为区间的起始位置
    int right = end; // 右指针初始化为区间的结束位置
    int keyi = left; // 基准索引初始化为左指针位置，基准值为a[keyi]

    // 使用双指针法进行分区操作
    while (left < right) 
    {
        // 右指针向左移动，直到找到一个小于等于基准值的元素
        while (left < right && a[right] >= a[keyi]) 
        {
            right--;
        }
        // 左指针向右移动，直到找到一个大于基准值的元素
        while (left < right && a[left] <= a[keyi]) 
        {
            left++;
        }
        // 交换左右指针指向的元素，确保左半部分元素都不大于基准值，右半部分元素都不小于基准值
        if (left < right) 
        {
            Swap(&a[left], &a[right]); // 交换元素的函数
        }
    }
    
    // 左右指针相遇，交换基准值与相遇点的值，使得基准值归位
    int meeti = left; 
    Swap(&a[keyi], &a[meeti]);

    // 对基准值左侧的子数组进行递归排序
    QuickSort1(a, begin, meeti - 1);
    // 对基准值右侧的子数组进行递归排序
    QuickSort1(a, meeti + 1, end);
}

2.挖坑法版本

// 快速排序的挖坑法实现
void QuickSort2(int* a, int begin, int end)
{
    if (begin >= end) // 基本情况检查：如果起始索引大于等于结束索引，说明区间内没有元素或仅有一个元素，无需排序，直接返回
        return;

    int left = begin; // 初始化左指针为区间起始位置
    int right = end; // 初始化右指针为区间结束位置
    int key = a[left]; // 选取基准值，即区间起始位置的元素

    // 使用挖坑法进行分区操作
    while (left < right) 
    {
        // 右指针左移，直到找到一个小于等于基准值的元素
        while (left < right && a[right] >= key) 
        {
            right--;
        }
        // 将找到的小于等于基准值的元素填入基准值“挖出”的“坑”中（即数组的最左侧）
        a[left] = a[right];
        
        // 左指针右移，直到找到一个大于基准值的元素
        while (left < right && a[left] <= key) 
        {
            left++;
        }
        // 将找到的大于基准值的元素填入右指针当前位置（之前存放了一个小于等于基准值的元素）
        a[right] = a[left];
    }
    
    // 左右指针相遇，此时left（或right）的位置即为基准值的正确位置
    int meeti = left; 
    a[meeti] = key; // 将基准值放回其最终确定的位置

    // 对基准值左侧的子数组进行递归排序
    QuickSort2(a, begin, meeti - 1);
    // 对基准值右侧的子数组进行递归排序
    QuickSort2(a, meeti + 1, end);
}

3.前后指针版本

// 快速排序的前后指针法实现
void QuickSort3(int* a, int begin, int end)
{
    if (begin >= end) // 基础情况：如果起始索引大于等于结束索引，说明区间为空或只有一个元素，无需排序，直接返回
        return;

    int midIndex = GetMidIndex(a, begin, end); // 三数取中
    Swap(&a[begin], &a[midIndex]); // 将中间索引处的元素（基准值）与起始位置的元素交换，确保基准值在数组的第一个位置

    int prev = begin; // 初始化"前指针"，指向待排序部分的第一个元素（基准值之前的元素，初始时指向基准值）
    int cur = begin + 1; // 初始化"当前指针"，从基准值的下一个元素开始遍历
    int keyi = begin; // 基准值的索引

    // 使用前后指针法进行分区操作
    while (cur <= end) 
    {
        // 如果当前元素小于基准值，并且前指针还没有到达当前元素的位置（避免自我交换）
        if (a[cur] < a[keyi] && ++prev != cur) 
        {
            Swap(&a[prev], &a[cur]); // 交换前指针指向的元素与当前元素，使小元素移动到基准值左侧
        }
        cur++; // 移动当前指针，检查下一个元素
    }
    
    // 找到前指针和当前指针相遇的位置，即为基准值的正确位置
    int meeti = prev; 
    Swap(&a[keyi], &a[meeti]); // 将基准值放到最终正确的位置

    // 对基准值左侧的子数组进行递归排序
    QuickSort3(a, begin, meeti - 1);
    // 对基准值右侧的子数组进行递归排序
    QuickSort3(a, meeti + 1, end);
}

非递归实现

快速排序的非递归实现通常利用栈来模拟递归的过程，以管理待排序区间的边界。

// 快速排序非递归版本
void QuickSortIterative(int* a, int n) 
{
    if (n <= 1) return; // 基本情况：数组为空或只有一个元素，无需排序

    int stack[n]; // 使用栈来保存未排序区间的左右边界
    int top = -1; // 栈顶指针

    stack[++top] = 0; // 将初始左边界（0）压入栈
    stack[++top] = n - 1; // 将初始右边界（n-1）压入栈

    while (top >= 0) 
    { // 当栈不空时
        int right = stack[top--]; // 弹出右边界
        int left = stack[top--]; // 弹出左边界

        int pivotIndex = Partition(a, left, right); // 执行分区操作，返回基准值索引

        // 如果基准值左边还有元素未排序，则将左边界和基准值索引-1压入栈
        if (pivotIndex - 1 > left) 
        {
            stack[++top] = left;
            stack[++top] = pivotIndex - 1;
        }

        // 如果基准值右边还有元素未排序，则将基准值索引+1和右边界压入栈
        if (pivotIndex + 1 < right) 
        {
            stack[++top] = pivotIndex + 1;
            stack[++top] = right;
        }
    }
}

// 分区操作
int Partition(int* a, int left, int right) 
{
    int pivot = a[left]; // 选择最左侧元素作为基准值
    int i = left + 1; // i指向左侧第一个可能比基准值大的元素
    int j = right; // j指向右侧第一个可能比基准值小的元素

    while (true) 
    {
        while (i <= j && a[i] <= pivot) i++; // 从左向右找第一个大于基准值的元素
        while (i <= j && a[j] >= pivot) j--; // 从右向左找第一个小于基准值的元素
        if (i >= j) break; // 如果i和j交错，停止循环
        Swap(&a[i], &a[j]); // 交换i和j位置的元素
    }

    Swap(&a[left], &a[j]); // 将基准值放到正确的位置
    return j; // 返回基准值的索引
}

时间复杂度：

最优情况：

当每次划分都很均匀时，每次都能将数组分成几乎相等的两部分，此时的时间复杂度为 O(nlog⁡n)O(nlogn)。这是由于每次划分操作都将问题规模减半，总共需要进行 log⁡nlogn 层递归，每层递归的合并操作需要线性时间 O(n)O(n)。

平均情况：

在大多数随机分布的数据集上，快速排序的平均时间复杂度也是 O(nlog⁡n)O(nlogn)。这是由于期望每次划分都能较好地平衡左右两个子数组的大小，从而保证了较好的平均性能。

最差情况：

当输入数组已经是有序或者接近有序，每次划分只能将数组分为一个元素和一个大得多的部分，导致快速排序退化为冒泡排序，此时的时间复杂度为 O(n2)O(n2)。为了避免这种情况，实际应用中通常会采用随机选择基准值或使用三数取中等策略来优化。

空间复杂度：

递归栈空间：

快速排序的空间复杂度主要取决于递归调用的深度，最好情况下（每次划分均衡），递归树的深度为 log⁡nlogn，因此空间复杂度为 O(log⁡n)O(logn)。但在最坏情况下，递归深度可能达到 nn，这时的空间复杂度为 O(n)O(n)。

其他空间：

除了递归调用栈之外，快速排序在原地进行元素比较和交换，不需要额外的存储空间，因此这部分的空间复杂度为 O(1)O(1)。

归并排序

动图演示：

基本思想

基于分治思想的高效排序算法。

具体步骤如下：

分解（Divide）：将当前的无序序列分成两个（或多个，但通常是两个）尽可能相等的子序列。如果子序列只有一个元素，则认为它是有序的，无需进一步分解。

递归排序（Conquer）：递归地对两个子序列分别进行归并排序。即不断重复分解和递归排序的过程，直到所有子序列都变为单个元素的有序序列。

合并（Combine）：将两个有序的子序列合并成一个有序序列。合并的过程中，通过比较两个子序列的首元素，将较小的元素先放入结果序列，然后移动指针到下一个元素，重复此过程，直到一个子序列为空，之后直接将另一个子序列的剩余部分复制到结果序列的末尾。

代码实现

递归实现

// 子函数定义：递归实现归并排序，a为待排序数组，left和right为当前子序列的左右边界索引，tmp为临时数组用于合并
void _MergeSort(int* a, int left, int right, int* tmp)
{
    if (left >= right) // 如果区间只有一个元素，直接返回（递归基准情形）
        return;

    int mid = left + (right - left) / 2; // 计算中间索引以划分左右子序列

    // 分别对左右子序列进行归并排序
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);

    // 合并两个有序子序列
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int i = left; // i为临时数组的索引

    // 比较并合并两个子序列中的元素
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }

    // 复制剩余元素到临时数组，如果有的话
    while (begin1 <= end1)
        tmp[i++] = a[begin1++];
    while (begin2 <= end2)
        tmp[i++] = a[begin2++];

    // 将临时数组中的结果复制回原数组
    int j = 0;
    for (j = left; j <= right; j++)
        a[j] = tmp[j];
}

// 主体函数定义：调用_MergeSort函数实现整个数组的归并排序，n为数组长度
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n); // 为临时数组分配内存
    if (tmp == NULL) // 检查内存分配是否成功
    {
        printf("malloc fail\n");
        exit(-1); // 分配失败则打印错误信息并退出程序
    }

    // 调用子函数进行归并排序，传入临时数组
    _MergeSort(a, 0, n - 1, tmp);

    free(tmp); // 释放临时数组所占内存
}

非递归实现

// 子函数定义：非递归方式合并两个已排序的子数组，a为原数组，tmp为临时数组，
// begin1和end1定义第一个子数组的边界，begin2和end2定义第二个子数组的边界
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
    int j = begin1; // j为原数组中待赋值的起始索引
    int i = begin1; // i为临时数组的当前索引

    // 比较并合并两个子数组中的元素
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }

    // 复制剩余元素到临时数组，如果有的话
    while (begin1 <= end1)
        tmp[i++] = a[begin1++];
    while (begin2 <= end2)
        tmp[i++] = a[begin2++];

    // 将合并后的有序序列从临时数组复制回原数组
    for (; j <= end2; j++)
        a[j] = tmp[j];
}

// 主体函数定义：非递归实现归并排序，a为待排序数组，n为数组长度
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n); // 为临时数组分配内存
    if (tmp == NULL) // 检查内存分配是否成功
    {
        printf("malloc fail\n");
        exit(-1); // 分配失败则打印错误信息并退出程序
    }

    int gap = 1; // 初始化间隔（步长）
    while (gap < n) // 当间隔小于数组长度时进行循环
    {
        int i = 0;
        for (i = 0; i < n; i += 2 * gap) // 遍历数组，每次跳过gap长度
        {
            int begin1 = i, end1 = i + gap - 1; // 定义第一个子数组边界
            int begin2 = i + gap, end2 = i + 2 * gap - 1; // 定义第二个子数组边界
            if (begin2 >= n) // 如果第二个子数组起始位置超出数组范围，跳出循环
                break;
            if (end2 >= n) // 调整第二个子数组的结束位置，避免越界
                end2 = n - 1;
            _MergeSortNonR(a, tmp, begin1, end1, begin2, end2); // 合并两个子数组
        }
        gap *= 2; // 下一轮迭代时，间隔翻倍
    }

    free(tmp); // 释放临时数组所占内存
}

时间复杂度：

归并排序的时间复杂度在所有情况下都是O(n log n)，这里的n是数组中元素的数量。

这是因为归并排序采用了分治法策略，将数组分成越来越小的子数组，然后再合并这些子数组。分治过程中，每一层递归会将问题规模减半，需要log n层递归；每层递归中，合并操作需要线性时间O(n)，因此总体时间复杂度为O(n log n)。

空间复杂度：

归并排序的空间复杂度为O(n)。

这是因为在合并子数组的过程中，需要一个与原数组相同大小的临时数组来存储合并后的有序序列。即使在实际操作中某些实现可以通过原地修改减少一部分空间使用，但主要的空间消耗依然来自于这个额外的存储需求，故空间复杂度维持在O(n)级别。

计数排序

动图演示：

基本思想

通过计算待排序数组中每个元素的出现次数，然后根据这些信息将每个元素放到其在输出数组中的正确位置上，从而实现排序。

具体步骤如下：

确定范围：首先遍历整个待排序数组，找出数组中的最大值和最小值，以便了解所需计数数组（也称作计数桶）的大小。计数数组的索引代表原始数组中的元素值，而计数数组中的值则是该元素在原始数组中出现的次数。

计数：创建一个计数数组，其长度为最大值与最小值之差加一（即数组的范围大小）。遍历原始数组，对于每个元素，将计数数组中对应索引的值加一。这一步实际上是在统计每个元素出现的频次。

累加（可选）：为了能够直接根据计数数组确定每个元素在输出数组中的最终位置，需要对计数数组进行一次累加操作。从计数数组的第二个元素开始，每个元素都加上前一个元素的值。这样，计数数组中的每个索引位置就存储了小于等于该索引值的元素总数。

排序：再次遍历原始数组，对于每个元素，根据其值查找计数数组对应的计数值，将元素放入输出数组的相应位置，并将计数值减一，以反映该元素已被放置。这一步实际上是在根据统计信息放置元素到最终排序位置。

输出或复制：完成上述步骤后，输出数组即为排序完成的数组。在某些实现中，可能会直接在原数组上修改排序，而不是使用额外的输出数组。

代码实现

// 计数排序函数
void CountSort(int* a, int n)
{
    // 初始化最小值和最大值为数组的第一个元素
    int min = a[0];
    int max = a[0];

    // 遍历数组以找到最大值和最小值
    for (int i = 0; i < n; i++)
    {
        if (a[i] < min)
            min = a[i]; // 更新最小值
        if (a[i] > max)
            max = a[i]; // 更新最大值
    }

    // 计算数组元素的范围，用于决定计数数组的大小
    int range = max - min + 1;

    // 动态分配计数数组，并初始化所有元素为0
    int* count = (int*)calloc(range, sizeof(int));
    if (count == NULL) // 检查内存分配是否成功
    {
        printf("Memory allocation failed.\n"); // 分配失败提示
        exit(-1); // 结束程序
    }

    // 计数阶段：统计每个元素出现的次数
    for (int i = 0; i < n; i++)
    {
        count[a[i] - min]++; // 增加对应元素计数
    }

    // 根据计数数组将元素放回原数组，实现排序
    int i = 0;
    // 遍历计数数组
    for (int j = 0; j < range; j++)
    {
        // 当前索引j在计数数组中的值表示原数组中值为j+min的元素个数
        while (count[j] > 0) // 当计数大于0时
        {
            a[i++] = j + min; // 放回原数组并更新索引
            count[j]--; // 减少计数
        }
    }

    // 释放计数数组占用的内存
    free(count);
}

时间复杂度：

最好、平均和最坏情况： 计数排序的时间复杂度均为 O(n+k)，其中 nn 是数组中元素的数量，kk 是输入数据范围（即数组中最大值与最小值的差加一）。这是因为计数排序需要遍历数组两次（一次计算每个元素的出现次数，一次根据计数重建排序数组），以及一次遍历计数数组来累加计数，这三者的时间复杂度分别是 O(n), O(n), 和 O(k)。由于 kk 是独立于 nn 的常数，所以在大 nn 的情况下，时间复杂度近似为线性的 O(n)。

空间复杂度：

计数排序的空间复杂度为 O(k)，这是因为需要额外的空间来存储计数数组，计数数组的大小取决于输入数据的范围，即最大值与最小值之间的差加一。即使数组本身可能包含较少的唯一元素，计数排序仍然需要为整个范围分配空间。