【排序算法】八大排序(上)(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;
}

一、冒泡排序

       冒泡排序是一种简单的排序算法,易于初学者理解和学习。它的核心思想就是重复遍历数组,比较相邻两个元素,如果它们的顺序错误,则交换之。直到数组中没有顺序错误的情况,则排序已经完成


       它的具体步骤描述如下:


1.遍历数组,比较所有的相邻元素,如果前者大于后者(默认升序),则交换它们。


2.当遍历到数组最后一对相邻元素后,数组中最后一个元素会是最大的数。此时一趟冒泡排序完成。


3.重新遍历数组比较相邻元素(最后一个元素除外,因为已经是最大的了)。一趟结束后,数组中第二大的元素将位于倒数第二个位置。


4.重复进行上述步骤(已经就位的元素除外),直到所有元素均不需要再交换。


动图表示:



接下来,我们尝试实现冒泡排序:

void BubbleSort(int* arr, int n)
{
    //外层循环控制排序的趟数
    for (int i = 0; i < n - 1; i++)//每一趟排序使一个元素就位,n个元素的数组需要n-1趟排序(最后一趟会使前两个元素就位)
    {
        //内层循环控制需要比较的相邻元素
        for (int j = 0; j < n - 1 - i; j++)//每一趟结束后,需要比较的元素便减少一个,所以要减去i
        {
            if (arr[j] > arr[j + 1])//若前者大于后者,说明顺序错误,需要交换
            {
                Swap(&arr[j], &arr[j + 1]);//交换两元素
            }
        }
    }
}

不难发现,如果没有到达排序的趟数,但是数组已经有序,程序就会继续进行不必要的元素比较,运行效率降低。基于这一点,我们可以做出如下改进:

void BubbleSort(int* arr, int n)
{
    //外层循环控制排序的趟数
    for (int i = 0; i < n - 1; i++)//每一趟排序使一个元素就位,n个元素的数组需要n-1趟排序(最后一趟会使前两个元素就位)
    {
        int flag = 1;//假设数组已经有序
 
        //内层循环控制需要比较的相邻元素
        for (int j = 0; j < n - 1 - i; j++)//每一趟结束后,需要比较的元素便减少一个,所以要减去i
        {
            if (arr[j] > arr[j + 1])//若前者大于后者,说明顺序错误,需要交换
            {
                Swap(&arr[j], &arr[j + 1]);//交换两元素
 
                flag = 0;//发生了交换,说明数组并非有序
            }
        }
        if (flag == 1)//如果数组已经有序,则不需要排序,直接退出循环
        {
            break;
        }
    }
}

接下来,我们对测试数组进行排序:

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]);
    BubbleSort(arr, sz);//冒泡排序
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

运行结果:



可以看到,排序成功了。


冒泡排序的特性总结


空间复杂度:O(1)


时间复杂度:O(N^2)


稳定性(相同值的元素排序前后的相对次序是否保持不变):稳定


无论数组是否有序,都有大量元素被重复地进行比较和交换,运行效率不高


二、选择排序

       选择排序是一种比较接近人类思想的排序算法,它的核心思想非常简单:从数组中寻找最小(最大)元素,将其放于数组第一个位置(最后一个位置)处,然后再从剩余的元素中寻找最小(最大)值,放到数组第二个位置(倒数第二个位置)处......


       具体步骤如下:


1.首先遍历数组,寻找到数组中最小的元素,将其与数组的首元素进行交换。


2.开始遍历数组的剩下部分,寻找最小值,与该部分的首元素进行交换。


3.重复第二步,直到“该部分”只有一个元素为止,说明数组已经排序好。


动图表示:



接下来,我们尝试代码实现选择排序:

void SelectSort(int* arr, int n)
{
    //外层循环控制遍历次数以及遍历的起始位置
    for (int i = 0; i < n; i++)
    {
        int mini = i;//假设最小值位于遍历部分的首元素处
        //内层循环,寻找最小值
        for (int j = mini + 1; j < n; j++)
        {
            if (arr[j] < arr[mini])//将更小的元素标记为mini
            {
                mini = j;
            }
        }
        Swap(&arr[i], &arr[mini]);//将最小值与遍历部分的首元素交换
    }
}

运行测试:



选择排序特性总结


空间复杂度:O(1)


时间复杂度:O(N^2)


稳定性:不稳定


使用寻找最值进行交换的方式,虽然在效率上相比冒泡排序有所提升,但是依然不是很实用。


三、插入排序

       插入排序是一种适用于对少量数据进行排序的算法,它的效率要略高于冒泡排序和选择排序。就像玩扑克牌一样,它的核心思想是:将一个个数据不断插入到已经有序的数组的合适位置,从而使整个数组有序


       具体步骤如下:


1.将数组首元素视为有序。


2.将有序数组的下一个元素取出,然后开始对该元素之前的部分进行遍历,找到合适位置并插入。


3.将这部分有序数组看成整体,重复第二步,直到将最后一个元素调整完成。


动图表示:



代码实现如下:

void InsertSort(int* arr, int n)
{
    //外层循环确定遍历次数
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;//记录有序数组的末尾位置
        int tmp = arr[end + 1];//保存需要插入的元素tmp
 
        //内层循环控制对有序数组的遍历
        while (end >= 0)//当end小于0时,一次遍历结束
        {
            if (arr[end] > tmp)
            {
                arr[end + 1] = arr[end];//该值后移一位,留空缺
                end--;//继续向前走
            }
            else//当tmp值比有序数组中某元素小或相等时,说明tmp应该插入在该元素之后,终止遍历
            {
                break;
            }
        }
        arr[end + 1] = tmp;//插入到该元素之后的位置
    }
}

代入测试:



插入排序性能总结


空间复杂度:O(1)


时间复杂度:O(N^2)


稳定性:稳定


虽然在时间复杂度上没有什么变化,但是相比冒泡排序和选择排序,性能有所提升。由于它是按照顺序进行扫描并且插入的,所以相同值元素的相对位置不会改变,是一种稳定的排序算法,是排序少量数据的首选。不过面对的数据量庞大时,依然不够看。


四、希尔排序

       希尔排序又称为缩小增量排序,是一种效率很高的排序算法,算是插入排序的升级版。它的核心思想也比较简单:首先对数组进行预排序,使其接近有序,然后进行插入排序


       这里介绍一下排序的思路:


       首先选定一个增量gap(这里我们使gap=数组元素n/3),将数组中相差gap个位置的元素视为一个子序列,然后分别对这些子序列进行插入排序。当所有子序列排序结束之后,使gap的值逐渐减小(再除以3),然后再将相差gap个位置的元素构成的子序列进行插入排序......直到gap为1时,构成的序列就是数组本身,对其进行一次插入排序即可。



       当然,这里的增量gap并不是只有n/3这一种取法。他还有很多种取法,例如n/2、n/4等。但要注意:变化的gap值应尽量满足没有除1以外的公因子,并且最后一次gap的值是1


接下来,我们尝试实现希尔排序:

void ShellSort(int* arr, int n)
{
    int gap = n;//定义增量gap
 
    //循环控制预排序的次数,以及进行最后一次插入排序
    while (gap > 1)
    {
        gap = gap / 3 + 1;//首先调整gap值
 
        //进行插入排序
        //注意细节处理,是对相隔gap的元素进行排序
        for (int i = 0; i < n - gap; i++)//一次循环结束后,i++就走向了下一个子序列的起始位置
        {
            int end = i;//记录有序部分的末尾位置
            int tmp = arr[end + gap];//end+gap位置的元素视为子序列中的下一个元素
            while (end >= 0)
            {
                if (arr[end] > tmp)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;//一次向前走gap个位置
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

从代码角度看,它相比插入排序又多了一层循环,效率怎么会高于插入排序呢?实际上,有了预排序之后,最后一次插入排序所节省的时间要远远大于预排序消耗的时间


代入数据测试:



希尔排序性能总结


空间复杂度:O(1)


时间复杂度:O(N^1.3)(计算过程相对复杂)


稳定性:不稳定


相比冒泡排序,选择排序和插入排序,希尔排序的时间复杂度较低,运行效率更高,更适用于大规模数据的排序。但是它的性能不稳定,易受数据和增量选择的影响。


程序全部代码

程序全部代码如下:

#include <stdio.h>
 
//交换函数
void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
 
//冒泡排序
void BubbleSort(int* arr, int n)
{
    //外层循环控制排序的趟数
    for (int i = 0; i < n - 1; i++)//每一趟排序使一个元素就位,n个元素的数组需要n-1趟排序(最后一趟会使前两个元素就位)
    {
        int flag = 1;//假设数组已经有序
 
        //内层循环控制需要比较的相邻元素
        for (int j = 0; j < n - 1 - i; j++)//每一趟结束后,需要比较的元素便减少一个,所以要减去i
        {
            if (arr[j] > arr[j + 1])//若前者大于后者,说明顺序错误,需要交换
            {
                Swap(&arr[j], &arr[j + 1]);//交换两元素
 
                flag = 0;//发生了交换,说明数组并非有序
            }
        }
        if (flag == 1)//如果数组已经有序,则不需要排序,直接退出循环
        {
            break;
        }
    }
}
 
//选择排序
void SelectSort(int* arr, int n)
{
    //外层循环控制遍历次数以及遍历的起始位置
    for (int i = 0; i < n; i++)
    {
        int mini = i;//假设最小值位于遍历部分的首元素处
        //内层循环,寻找最小值
        for (int j = mini + 1; j < n; j++)
        {
            if (arr[j] < arr[mini])//将更小的元素标记为mini
            {
                mini = j;
            }
        }
        Swap(&arr[i], &arr[mini]);//将最小值与遍历部分的首元素交换
    }
}
 
//插入排序
void InsertSort(int* arr, int n)
{
    //外层循环确定遍历次数
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;//记录有序数组的末尾位置
        int tmp = arr[end + 1];//保存需要插入的元素tmp
 
        //内层循环控制对有序数组的遍历
        while (end >= 0)//当end小于0时,一次遍历结束
        {
            if (arr[end] > tmp)
            {
                arr[end + 1] = arr[end];//该值后移一位,留空缺
                end--;//继续向前走
            }
            else//当tmp值比有序数组中某元素小或相等时,说明tmp应该插入在该元素之后,终止遍历
            {
                break;
            }
        }
        arr[end + 1] = tmp;//插入到该元素之后的位置
    }
}
 
//希尔排序
void ShellSort(int* arr, int n)
{
    int gap = n;//定义增量gap
 
    //循环控制预排序的次数,以及进行最后一次插入排序
    while (gap > 1)
    {
        gap = gap / 3 + 1;//首先调整gap值
 
        //进行插入排序
        //注意细节处理,是对相隔gap的元素进行排序
        for (int i = 0; i < n - gap; i++)//一次循环结束后,i++就走向了下一个子序列的起始位置
        {
            int end = i;//记录有序部分的末尾位置
            int tmp = arr[end + gap];//end+gap位置的元素视为子序列中的下一个元素
            while (end >= 0)
            {
                if (arr[end] > tmp)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;//一次向前走gap个位置
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}
 
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]);
    //BubbleSort(arr, sz);
    //SelectSort(arr, sz);
    //InsertSort(arr, sz);
    ShellSort(arr, sz);
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

总结

       今天,我们学习了八大排序的其中四种:冒泡排序,选择排序,插入排序和希尔排序。在理解这些排序思想和实现它们的过程当中,我们感受到了算法之美,也加强了分析问题、解决问题的能力。之后博主会和大家分享剩下的几种排序算法。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤

相关文章
|
1月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
57 4
|
4天前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
26 3
|
22天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
52 1
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
109 7
|
1月前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码,可作为课程设计项目参考,代码有详细的注释,另外编译可运行文件也已经打包,windows电脑双击即可运行效果
32 1
|
17天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
23天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
3天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
|
10天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
19天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
下一篇
DataWorks