前言

之前我们学习了八大排序中的前四种：冒泡排序、选择排序、插入排序、希尔排序，今天我们继续学习并实现剩下的四种排序算法：堆排序、快速排序、归并排序、计数排序。

测试数据和交换函数

我们先将上篇的测试数据和交换函数粘贴到这里：

#include <stdio.h>
 
int main()
{
    int arr[] = { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 };
    int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
 
    for (int i = 0; i < sz; i++)//打印数组
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

//交换两元素
void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

正文开始

五、堆排序

堆排序是一种效率很高的排序算法，它的出现源自于堆这种数据结构。如果你对堆这种数据结构不是很熟悉，可以看看这篇文章：

https://developer.aliyun.com/article/1635160?spm=a2c6h.13262185.profile.11.2fd52c70a7ygyK

堆排序的核心思想是：利用堆顶总是堆最小值（最大值）的特性，对数组元素进行建堆，每次取出堆顶元素完成排序。

具体步骤如下（默认升序）：

1.首先遍历数组元素，针对每一个元素进行向上调整，建大堆。

2.将堆顶与数组的最后元素交换，换到堆顶位置的元素进行向下调整，确保堆顶为最大值。

3.此时数组最后一个元素已经就位，接下来将剩余部分看作一个数组，重复第二步，直到所有元素就位为止。

这里阐释一下建大堆的原因：由于我们是对数组排升序，也就是说数组元素是按照顺序依次从小到大排放的，最后一个元素就是数组的最大值。建大堆就类似于选择排序的做法，找出数组的最大值，放到数组末尾，然后依次向前排放......总结成一句话就是：升序建大堆，降序建小堆。

画图演示一下排序过程：

接下来，我们开始实现堆排序：

//堆排序
void HeapSort(int* arr, int n)
{
    for (int i = 0; i < n; i++)//遍历使每个元素向上调整，建大堆
    {
        AdjustUp(arr, i);//向上调整算法
    }
    for (int i = n - 1; i > 0; i--)
    {
        Swap(&arr[0], &arr[i]);//将堆顶与堆末尾元素交换，i是当前堆中的末尾下标
        AdjustDown(arr, 0, i);//将换上来的元素进行向下调整
    }
}

//堆的向上调整
void AdjustUp(int* arr, int child)
{
    int parent = (child - 1) / 2;//先找到父节点的下标
    while (parent >= 0)//父节点下标<0时，已越界
    {
        if (arr[child] > arr[parent])//若孩子节点的值大于父节点的值，就需要调整
        {
            Swap(&arr[child], &arr[parent]);//交换两元素
 
            //此时，新的孩子节点跑到了原来父节点的位置
            child = parent;
            parent = (child - 1) / 2;//确定新的父节点
        }
        else//其他情况说明已经调整完成，退出循环
        {
            break;
        }
    }
}

//堆的向下调整
void AdjustDown(int* arr, int parent, int n)
{
    int child = parent * 2 + 1;//先找到左孩子的下标
    while (child < n)//当孩子节点下标>=n时，已越界
    {
        //若右孩子存在，则将左孩子和右孩子进行比较，找到更大的子节点便于调整交换，保证大堆的特性
        if (child + 1 < n && arr[child] < arr[child + 1])
        {
            child++;
        }
        if (arr[parent] < arr[child])//父节点的值小于子节点，需要调整
        {
            Swap(&arr[parent], &arr[child]);
 
            //此时父节点跑到了孩子节点的位置
            parent = child;
            child = parent * 2 + 1;//确定新的孩子节点
        }
        else//其他情况，调整完成退出循环
        {
            break;
        }
    }
}

代入数据测试：

堆排序性能总结

空间复杂度：O(1)

时间复杂度：O(NlogN)

稳定性：不稳定

由于堆排序每次从堆顶取出最值并排列，所以它是一种选择性排序。相比直接选择排序，它的效率非常高，是一种很常用的排序算法。

六、快速排序

快速排序，也就是我们常说的“快排”，它以其高效的排序效率而著称。它的核心思想是：将待排序数组划分成近乎均等的两份，左半部分的数值都比右半部分的数值小。接着递归性地将这两份数据继续按照以上规则划分，直到每一部分都是最小单元为止。此时，数组已经排序完成。

当我们划分数组时，需要寻找一个基准值作为参考，一部分小于这个基准值，另一部分大于基准值。在这里，我们默认将基准值定义为数组的首元素。

当然，数组划分的方法并不只是一种，所以我们接下来会详细介绍三种划分方法并且尝试实现。

我们先将快排的大框架写好：

//快速排序
void QuickSort(int* arr, int left, int right)//确定左右区间，便于后续递归
{
    if (left >= right)//左右区间相等，划分结束，回归
    {
        return;
    }
    int key = _QuickSort(arr, left, right);//子方法，按照基准值划分数组并返回基准值的下标
 
    //递归，对两部分数组分别处理，使其继续划分
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}

这里的_QuickSort子方法就是我们划分数组的操作，接下来我们逐一讲解三种划分思路：

1.hoare版本

hoare版本的划分方法是快速排序的祖师爷Tony hoare亲自发明的，也是最经典的划分方法。它的算法思想如下：

1.创建左右“指针”分别指向数组两端。

2.右指针向左走，寻找比基准值小的数据；左指针向右走，寻找比基准值大的数据。

3.将左右指针指向的数据交换。交换之后，左右指针继续移动寻找数据。

4.当左指针在右指针之后时，停止遍历，将基准值放于中间位置，并返回其地址。

画图模拟划分过程：

代码实现：

//子方法--hoare版本
int _QuickSort(int* arr, int left, int right)
{
    int keyi = left++;//基准值位于首元素位置，left走到下一个位置
    while (left <= right)//当left跑到right右边时退出循环停止寻找
    {
        while (left <= right && arr[right] > arr[keyi])//循环使right--，找到小于基准值的元素
        {
            right--;
        }
        while (left <= right && arr[left] < arr[keyi])//循环使left++，找到大于基准值的元素
        {
            left++;
        }
        if (left <= right)//如果left位于right右边，交换就会影响之前的操作
        {
            Swap(&arr[left++], &arr[right--]);//交换两元素，然后left往右走，right往左走
        }
    }
 
    //此时left位于right右，将right值与基准值交换
    Swap(&arr[right], &arr[keyi]);
    return right;//返回基准值的位置
}

代入数据测试：

2.挖坑法

挖坑法也是一种非常巧妙的划分方法，并且理解起来也比较容易。它的算法思想如下：

1.先创建左右“指针”分别指向数组两端，将坑位hole定义为数组首元素的位置，并记录基准值。

2.右指针向左走，遇到比基准值小的数，将该数填坑，并将右指针位置设置为新的坑位。

3.左指针向右走，遇到比基准值大的数，将该数填坑，并将左指针位置设置为新的坑位。

4.重复进行2、3步，直到当左右指针相遇时，将记录的基准值填坑，并返回该坑位的地址。

画图模拟划分过程：

动图表示：

接下来，我们尝试实现挖坑法：

//子方法--挖坑法
int _QuickSort(int* arr, int left, int right)
{
    int key = arr[left];//记录基准值
    int hole = left;//坑位初始设置为left位置
    while (left < right)//两者相遇则停止遍历
    {
        while (left < right && arr[right] >= key)//循环查找比基准值小的元素
        {
            right--;
        }
        //找到了
        arr[hole] = arr[right];//填坑
        hole = right;//将right位置设置为新坑位
 
        while (left < right && arr[left] <= key)//循环查找比基准值大的元素
        {
            left++;
        }
        //找到了
        arr[hole] = arr[left];//填坑
        hole = left;//将left设置为新坑位
    }
    arr[hole] = key;//将基准值填坑
    return hole;//返回坑位
}

代入测试：

3.lomoto版本

lomoto版本的划分方法算是这三者中代码量最少的了。这里介绍一下它的算法思路：

1.定义前后“指针”：prev指向首元素，cur指向其下一个元素，基准值默认为首元素。

2.当cur遇到比基准值小的元素时，prev往后走一步，然后与cur指向的元素交换。cur一直向后查找，直到超过数组边界为止。

3.交换基准值与prev指向的元素，并返回此时基准值的地址。

画图模拟划分过程：

动图表示：

代码实现如下：

//子方法--lomoto前后指针法
int _QuickSort(int* arr, int left, int right)
{
    int keyi = left;//基准值为第一个元素
    int prev = left, cur = left + 1;//定义前后指针
    while (cur <= right)//cur越界则停止循环
    {
        if (arr[cur] < arr[keyi] && ++prev != cur)//遇到小的元素，prev就向后走一步。若此时指针相等没必要交换
        {
            Swap(&arr[cur], &arr[prev]);
        }
        cur++;//cur向后走
    }
    Swap(&arr[prev], &arr[keyi]);//交换prev值于基准值
    return prev;//返回此时基准值的位置
}

测试运行：

4.快速排序的非递归实现

之前我们学习的三种划分方法，都是基于递归的大框架实现的。那么快速排序是否可以用非递归的方法来实现呢？当然可以，不过需要借助一种数据结构：栈。

它的实现逻辑是：将待划分区间的右边界下标和左边界下标入栈，之后循环取栈顶元素，通过取到的左右下标来确定划分的区间。一次划分完成后，再将基准值左侧区间和右侧区间入栈，然后读取栈顶元素，循环往复，直到栈空为止。

接下来我们尝试实现：

//快排非递归
void QuickSortNR(int* arr, int left, int right)
{
    ST st;//创建栈
    STInit(&st);//初始化
    STPush(&st, right);//右边界入栈
    STPush(&st, left);//左边界入栈
    while (!STEmpty(&st))//若栈不为空，则进入循环
    {
        int begin = STTop(&st);//先出栈的为右边界
        STPop(&st);
 
        int end = STTop(&st);//后出栈的为左边界
        STPop(&st);
 
        //这里使用lomoto划分
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end)
        {
            if (arr[cur] < arr[keyi] && ++prev != cur)
            {
                Swap(&arr[cur], &arr[prev]);
            }
            cur++;
        }
        Swap(&arr[prev], &arr[keyi]);
 
        int key = prev;//记录基准值位置
        if (begin < key - 1)//判断左子区间是否有效
        {
            STPush(&st, key - 1);//右边界入栈
            STPush(&st, begin);//左边界入栈
        }
        if (key + 1 < end)//判断右子区间是否有效
        {
            STPush(&st, end);//右边界入栈
            STPush(&st, key + 1);//左边界入栈
        }
    }
    STDestroy(&st);//排序完成后，销毁栈
}

运行测试：

5.快速排序性能总结

空间复杂度：O(logN)(创建函数栈帧)

时间复杂度：O(NlogN)

稳定性：不稳定

快速排序的效率非常高，经常作为排序的首选算法。不过可以发现，我们刚才介绍的三种划分方法都对与基准值相同值的数据没有明确规定如何划分，这将导致在大量数据相同的情况下，运行效率大幅降低。之后博主会和大家分享快速排序的升级版--三路快排，它将很大程度的优化此类问题。

七、归并排序

归并排序是一种高效的排序算法，理解起来也比较容易。它的核心思想是：将复杂的排序问题分解成许多个“小问题”，然后将问题的结果进行合并，以达到排序的效果。具体来讲就是：

1.首先将待排序数组进行折半划分，直到划分后的每一部分都是最小单位（一个元素）。

2.将最小单位视为一个已经有序的数组，然后与其他的有序数组进行合并（合并两个有序数组），合并之后的大数组仍然有序。

3.所有数组全部合并好后，排序完成。

归并排序的图解：

接下来，我们尝试实现归并排序：

//归并排序
void MergeSort(int* arr, int n)
{
    int* tmp = (int*)malloc(n * sizeof(int));//创建临时数组暂存合并好的数据
    if (tmp == NULL)
    {
        exit(1);
    }
    _MergeSort(arr, 0, n - 1, tmp);//子方法，完成划分与合并
    free(tmp);//销毁临时数组
    tmp = NULL;
}

//子方法
void _MergeSort(int* arr, int left, int right, int* tmp)
{
    if (left >= right)//当左右区间相同（只有一个元素）时，停止划分
    {
        return;
    }
    int mid = (left + right) / 2;//折半
 
    //递归划分数组
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);
 
    //划分结束，开始合并
    int begin1 = left, end1 = mid;//定义第一个有序数组的左右边界
    int begin2 = mid + 1,end2 = right;//定义第二个有序数组的左右边界
    int index = begin1;//tmp数组的起始下标
 
    //合并操作
    while (begin1 <= end1 && begin2 <= end2)//两者都未越界进入循环
    {
        if (arr[begin1] < arr[begin2])//小的元素先放进去
        {
            tmp[index++] = arr[begin1++];
        }
        else
        {
            tmp[index++] = arr[begin2++];
        }
    }
    //此时，必有一个数组没有越界，则将该数组剩下的元素放进tmp
    while (begin1 <= end1)
    {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = arr[begin2++];
    }
 
    //最后将tmp数组中排序好的元素放回原数组
    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }
}

运行结果测试：

归并排序性能总结

空间复杂度：O(N)（创建临时数组）

时间复杂度：O(NlogN)

稳定性：稳定

归并排序的效率非常高，且性能稳定，特别是在需要保持元素顺序、处理链表数据或进行外部排序时，它的优势尤为明显。

八、计数排序

计数排序是一种非比较的排序，是一种典型的以空间换时间的排序算法。它的算法思路是：创建一个临时数组count,该数组中下标为 i 的元素的数值表示待排序数组中数值等于 i 的元素个数。之后通过遍历数组count把数据排到正确的位置。

具体步骤如下：

1.先找出待排序数组中的最大值max和最小值min。

2.创建count数组，其大小为 max - min + 1 ，使得它能够存放两值之间所有的数值统计。

3.遍历待排数组，统计每一个值为i的元素出现的次数，将其累加在对应count数组的下标元素中。

4.从左到右遍历数组count，每将下标 i 存放回原数组，count [ i ]就自减，直到减为0为止。

计数排序图解：

代码实现：

//计数排序
void CountSort(int* arr, int n)
{
    //首先寻找最大值和最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
 
    //确定count数组的大小，并创建数组
    int range = max - min + 1;
    int* count = (int*)malloc(range * sizeof(int));
    if (count == NULL)
    {
        exit(1);
    }
    memset(count, 0, range * sizeof(int));//将数组元素全部初始化为0，使用时要引头文件 string.h
 
    //开始统计数据存入count数组
    for (int i = 0; i < n; i++)
    {
        count[arr[i] - min]++;//数组元素与min的差值是count的对应下标，因为count的0下标处表示最小值min
    }
 
    //反向输出
    int index = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i]--)//元素-1，就输出一个下标值回去
        {
            arr[index++] = i + min;//加上与min的差值
        }
    }
 
    //最后释放count数组
    free(count);
    count = NULL;
}

计数排序性能总结

空间复杂度：O(range)

时间复杂度：O(N+range)

稳定性：稳定

计数排序的构思非常巧妙，且对于大数据量的排序，效率要远远高于其他排序算法。但是它只能对整型进行排序，而且它易受数据范围的影响，当数据的峰值差距非常大时，空间消耗会剧增，运行效率大打折扣。

程序全部代码

数据结构栈的全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int STDataType;
 
//定义栈
typedef struct Stack
{
    STDataType* arr;
    int capacity;
    int top;
}ST;
 
//初始化
void STInit(ST* ps);
 
//销毁
void STDestroy(ST* ps);
 
//判空
bool STEmpty(ST* ps);
 
//压栈
void STPush(ST* ps, STDataType n);
 
//出栈
void STPop(ST* ps);
 
//取栈顶元素
STDataType STTop(ST* ps);
 
//获取栈中有效元素个数
int STSize(ST* ps);
 
//初始化
void STInit(ST* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
 
//销毁
void STDestroy(ST* ps)
{
    assert(ps);
    if (ps->arr)
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
 
//判空
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
 
 
//压栈
void STPush(ST* ps, STDataType n)
{
    assert(ps);
    if (ps->capacity == ps->top)
    {
        int NewCapacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = NewCapacity;
    }
    ps->arr[ps->top++] = n;
}
 
//出栈
void STPop(ST* ps)
{
    assert(ps && !STEmpty(ps));
    ps->top--;
}
 
//取栈顶元素
STDataType STTop(ST* ps)
{
    assert(ps && !STEmpty(ps));
    return ps->arr[ps->top - 1];
}
 
//获取栈中有效元素个数
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

四种排序全部代码：

#include "Stack.h"
#include <string.h>
 
//交换两元素
void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
 
//堆的向上调整
void AdjustUp(int* arr, int child)
{
    int parent = (child - 1) / 2;//先找到父节点的下标
    while (parent >= 0)//父节点下标<0时，已越界
    {
        if (arr[child] > arr[parent])//若孩子节点的值大于父节点的值，就需要调整
        {
            Swap(&arr[child], &arr[parent]);//交换两元素
 
            //此时，新的孩子节点跑到了原来父节点的位置
            child = parent;
            parent = (child - 1) / 2;//确定新的父节点
        }
        else//其他情况说明已经调整完成，退出循环
        {
            break;
        }
    }
}
 
//堆的向下调整
void AdjustDown(int* arr, int parent, int n)
{
    int child = parent * 2 + 1;//先找到左孩子的下标
    while (child < n)//当孩子节点下标>=n时，已越界
    {
        //若右孩子存在，则将左孩子和右孩子进行比较，找到更大的子节点便于调整交换，保证大堆的特性
        if (child + 1 < n && arr[child] < arr[child + 1])
        {
            child++;
        }
        if (arr[parent] < arr[child])//父节点的值小于子节点，需要调整
        {
            Swap(&arr[parent], &arr[child]);
 
            //此时父节点跑到了孩子节点的位置
            parent = child;
            child = parent * 2 + 1;//确定新的孩子节点
        }
        else//其他情况，调整完成退出循环
        {
            break;
        }
    }
}
 
//堆排序
void HeapSort(int* arr, int n)
{
    for (int i = 0; i < n; i++)//遍历使每个元素向上调整，建大堆
    {
        AdjustUp(arr, i);//向上调整算法
    }
    for (int i = n - 1; i > 0; i--)
    {
        Swap(&arr[0], &arr[i]);//将堆顶与堆末尾元素交换，i是当前堆中的末尾下标
        AdjustDown(arr, 0, i);//将换上来的元素进行向下调整
    }
}
 
子方法--hoare版本
//int _QuickSort(int* arr, int left, int right)
//{
//  int keyi = left++;//基准值位于首元素位置，left走到下一个位置
//  while (left <= right)//当left跑到right右边时退出循环停止寻找
//  {
//      while (left <= right && arr[right] > arr[keyi])//循环使right--，找到小于基准值的元素
//      {
//          right--;
//      }
//      while (left <= right && arr[left] < arr[keyi])//循环使left++，找到大于基准值的元素
//      {
//          left++;
//      }
//      if (left <= right)//如果left位于right右边，交换就会影响之前的操作
//      {
//          Swap(&arr[left++], &arr[right--]);//交换两元素，然后left往右走，right往左走
//      }
//  }
//
//  //此时left位于right右，将right值与基准值交换
//  Swap(&arr[right], &arr[keyi]);
//  return right;//返回基准值的位置
//}
 
子方法--挖坑法
//int _QuickSort(int* arr, int left, int right)
//{
//  int key = arr[left];//记录基准值
//  int hole = left;//坑位初始设置为left位置
//  while (left < right)//两者相遇则停止遍历
//  {
//      while (left < right && arr[right] >= key)//循环查找比基准值小的元素
//      {
//          right--;
//      }
//      //找到了
//      arr[hole] = arr[right];//填坑
//      hole = right;//将right位置设置为新坑位
//
//      while (left < right && arr[left] <= key)//循环查找比基准值大的元素
//      {
//          left++;
//      }
//      //找到了
//      arr[hole] = arr[left];//填坑
//      hole = left;//将left设置为新坑位
//  }
//  arr[hole] = key;//将基准值填坑
//  return hole;//返回坑位
//}
 
//子方法--lomoto前后指针法
int _QuickSort(int* arr, int left, int right)
{
    int keyi = left;//基准值为第一个元素
    int prev = left, cur = left + 1;//定义前后指针
    while (cur <= right)//cur越界则停止循环
    {
        if (arr[cur] < arr[keyi] && ++prev != cur)//遇到小的元素，prev就向后走一步。若此时指针相等没必要交换
        {
            Swap(&arr[cur], &arr[prev]);
        }
        cur++;//cur向后走
    }
    Swap(&arr[prev], &arr[keyi]);//交换prev值于基准值
    return prev;//返回此时基准值的位置
}
 
//快速排序
void QuickSort(int* arr, int left, int right)//确定左右区间，便于后续递归
{
    if (left >= right)//左右区间相等，划分结束，回归
    {
        return;
    }
    int key = _QuickSort(arr, left, right);//子方法，按照基准值划分数组并返回基准值的下标
 
    //递归，对两部分数组分别处理，使其继续划分
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}
 
//快排非递归
void QuickSortNR(int* arr, int left, int right)
{
    ST st;//创建栈
    STInit(&st);//初始化
    STPush(&st, right);//右边界入栈
    STPush(&st, left);//左边界入栈
    while (!STEmpty(&st))//若栈不为空，则进入循环
    {
        int begin = STTop(&st);//先出栈的为右边界
        STPop(&st);
 
        int end = STTop(&st);//后出栈的为左边界
        STPop(&st);
 
        //这里使用lomoto划分
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end)
        {
            if (arr[cur] < arr[keyi] && ++prev != cur)
            {
                Swap(&arr[cur], &arr[prev]);
            }
            cur++;
        }
        Swap(&arr[prev], &arr[keyi]);
 
        int key = prev;//记录基准值位置
        if (begin < key - 1)//判断左子区间是否有效
        {
            STPush(&st, key - 1);//右边界入栈
            STPush(&st, begin);//左边界入栈
        }
        if (key + 1 < end)//判断右子区间是否有效
        {
            STPush(&st, end);//右边界入栈
            STPush(&st, key + 1);//左边界入栈
        }
    }
    STDestroy(&st);//排序完成后，销毁栈
}
 
//子方法
_MergeSort(int* arr, int left, int right, int* tmp)
{
    if (left >= right)//当左右区间相同（只有一个元素）时，停止划分
    {
        return;
    }
    int mid = (left + right) / 2;//折半
 
    //递归划分数组
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);
 
    //划分结束，开始合并
    int begin1 = left, end1 = mid;//定义第一个有序数组的左右边界
    int begin2 = mid + 1,end2 = right;//定义第二个有序数组的左右边界
    int index = begin1;//tmp数组的起始下标
 
    //合并操作
    while (begin1 <= end1 && begin2 <= end2)//两者都未越界进入循环
    {
        if (arr[begin1] < arr[begin2])//小的元素先放进去
        {
            tmp[index++] = arr[begin1++];
        }
        else
        {
            tmp[index++] = arr[begin2++];
        }
    }
    //此时，必有一个数组没有越界，则将该数组剩下的元素放进tmp
    while (begin1 <= end1)
    {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = arr[begin2++];
    }
 
    //最后将tmp数组中排序好的元素放回原数组
    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }
}
 
//归并排序
void MergeSort(int* arr, int n)
{
    int* tmp = (int*)malloc(n * sizeof(int));//创建临时数组暂存合并好的数据
    if (tmp == NULL)
    {
        exit(1);
    }
    _MergeSort(arr, 0, n - 1, tmp);//子方法，完成划分与合并
    free(tmp);//销毁临时数组
    tmp = NULL;
}
 
//计数排序
void CountSort(int* arr, int n)
{
    //首先寻找最大值和最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
 
    //确定count数组的大小，并创建数组
    int range = max - min + 1;
    int* count = (int*)malloc(range * sizeof(int));
    if (count == NULL)
    {
        exit(1);
    }
    memset(count, 0, range * sizeof(int));//将数组元素全部初始化为0，使用时要引头文件 string.h
 
    //开始统计数据存入count数组
    for (int i = 0; i < n; i++)
    {
        count[arr[i] - min]++;//数组元素与min的差值是count的对应下标，因为count的0下标处表示最小值min
    }
 
    //反向输出
    int index = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i]--)//元素-1，就输出一个下标值回去
        {
            arr[index++] = i + min;//加上与min的差值
        }
    }
 
    //最后释放count数组
    free(count);
    count = NULL;
}
 
int main()
{
    int arr[] = { 5,9,4,0,2,7,8,0,0,1,4,4,1,3,5,6,3,2,9,7 };
    int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
    
    for (int i = 0; i < sz; i++)//打印数组
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

八大排序的运行时间测试

以下是对于一百万个整形数据，八种排序算法的运行时间对比：

可以看到，不同排序算法之间的运行效率差距还是特别大的。

总结

本篇文章我们学习了八大排序的剩下四种：堆排序、快速排序、归并排序和计数排序。可以发现，不同排序算法的思想差异是非常大的，它们的运行效率以及适用场景也各有优劣。我们在对数据进行排序时，要结合各种排序思想以及它们的优缺点，选择最合适的排序算法，确保程序的高效性。之后博主会和大家分享c++类和对象的内容。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

【排序算法】八大排序（下）（c语言实现）（附源码）

前言

测试数据和交换函数

五、堆排序

六、快速排序

1.hoare版本

2.挖坑法

3.lomoto版本

4.快速排序的非递归实现

5.快速排序性能总结

七、归并排序

八、计数排序

程序全部代码

八大排序的运行时间测试

总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【排序算法】八大排序（下）（c语言实现）（附源码）

前言

测试数据和交换函数

五、堆排序

六、快速排序

1.hoare版本

2.挖坑法

3.lomoto版本

4.快速排序的非递归实现

5.快速排序性能总结

七、归并排序

八、计数排序

程序全部代码

八大排序的运行时间测试

总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景