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

简介: 本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。

前言

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


测试数据和交换函数

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

#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++类和对象的内容。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤

相关文章
|
1月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
53 4
|
14天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
39 1
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
87 8
|
1月前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码,可作为课程设计项目参考,代码有详细的注释,另外编译可运行文件也已经打包,windows电脑双击即可运行效果
32 1
|
存储 人工智能 算法
|
存储 人工智能 算法
c语言排序算法总结
一.希尔(Shell)排序法 /* Shell 排序法 */ #include void sort(int v[],int n) {      int gap,i,j,temp;      for(gap=n/2;gap>0;gap ...
1254 0
|
11天前
|
存储 C语言 开发者
【C语言】字符串操作函数详解
这些字符串操作函数在C语言中提供了强大的功能,帮助开发者有效地处理字符串数据。通过对每个函数的详细讲解、示例代码和表格说明,可以更好地理解如何使用这些函数进行各种字符串操作。如果在实际编程中遇到特定的字符串处理需求,可以参考这些函数和示例,灵活运用。
31 10
|
11天前
|
存储 程序员 C语言
【C语言】文件操作函数详解
C语言提供了一组标准库函数来处理文件操作,这些函数定义在 `<stdio.h>` 头文件中。文件操作包括文件的打开、读写、关闭以及文件属性的查询等。以下是常用文件操作函数的详细讲解,包括函数原型、参数说明、返回值说明、示例代码和表格汇总。
29 9
|
11天前
|
存储 Unix Serverless
【C语言】常用函数汇总表
本文总结了C语言中常用的函数,涵盖输入/输出、字符串操作、内存管理、数学运算、时间处理、文件操作及布尔类型等多个方面。每类函数均以表格形式列出其功能和使用示例,便于快速查阅和学习。通过综合示例代码,展示了这些函数的实际应用,帮助读者更好地理解和掌握C语言的基本功能和标准库函数的使用方法。感谢阅读,希望对你有所帮助!
28 8
|
11天前
|
C语言 开发者
【C语言】数学函数详解
在C语言中,数学函数是由标准库 `math.h` 提供的。使用这些函数时,需要包含 `#include <math.h>` 头文件。以下是一些常用的数学函数的详细讲解,包括函数原型、参数说明、返回值说明以及示例代码和表格汇总。
28 6