【数据结构】十二、八种常用的排序算法讲解及代码分享

目录

一、插入排序

1)算法思想

2)代码

二、希尔排序

1)算法思想

2)代码

三、选择排序

1)算法思想

2)代码

四、堆排序

1)什么是最大堆

2)如何创建最大堆

3)算法思想

4)代码

五、冒泡排序

1)算法思想

2)代码

六、快速排序

1)算法思想

2)代码

七、归并排序

1)算法思想

2)代码

八、基数排序/桶排序(只对整数类型有效)

1)算法思想

2)代码


一、插入排序

1)算法思想

插入排序即将一个无序的元素集合中的元素一个个插入到子集合中合适的位置,直到原集合中的元素全部加入到子集合中。

2)代码

//插入排序
void Insert_Sort(DataType a[], int n)
{
    DataType temp;
    for (int i = 0; i < n - 1; i++)   //0 到 i 的数据已排序好
    {
        temp = a[i + 1];
        int j = i;
        while (j >= 0 && a[j] > temp) //如果是小于号则递增排序,如果是大于号则递减排序
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

二、希尔排序

1)算法思想

希尔排序算是插入排序的进阶版本,先把待排序的元素分为若干个小组,然后对每个小组进行插入排序

这里的“增量(span)”代表将相邻span的元素分为一组,span的取值一般取n/2

2)代码

//希尔排序
void Shell_Sort(DataType a[], int n)
{
    int span = n / 2;
    DataType temp;
    while (span > 0)
    {
        for (int i = 0; i < span; i ++)  //将数组分为span个小组
        {
            //对各组进行插入排序
            for (int k = i; k < n - span; k += span)
            {
                temp = a[k + span];
                int j = k;
                while (j >= 0 && a[j] > temp)
                {
                    a[j + span] = a[j];
                    j -= span;
                }
                a[j + span] = temp;
            }
        }
        span /= 2;
    }
}

三、选择排序

1)算法思想

每次从待排序的集合中选择最小(或最大)的元素放到集合的最前面,元素集合不断缩小,当待排序集合为空时代表排序结束。

2)代码

//选择排序
void Select_Sort(DataType a[], int n)
{
    DataType temp;
    for (int i = 0; i < n; i++)
    {
        DataType min = a[i];
        int k = i;
        for (int j = i; j < n; j++)
        {
            if (a[j] < min)
            {
                min = a[j];
                k = j;
            }
        }
        temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
}

四、堆排序

1)什么是最大堆

1、完全二叉树结构;

2、双亲节点的值都比其孩子节点大。

2)如何创建最大堆

对于一个线性表,很容易可以将其转换为完全二叉树,因为线性表元素的下标是一一对应着完全二叉树的节点。我们先来记住两个重要的对应:

  1. (n-2)/ 2 :表示最后一个非叶子节点;

  2.    2 * i + 1 :表示第i个节点的左孩子;

将数组调整为大根堆的过程:

对应代码如下:

//其中n为数组a中的元素个数,h为要调整的元素的下标
static void CreatHeap(DataType a[], int n, int h)
{
    int flag = 0,i = h;
    DataType temp = a[i];
    int j = 2 * i + 1;   //先让j指向h左孩子节点的下标

    while (j < n && flag != 1)
    {
        //寻找左右孩子节点中的较大者,j为其下标
        if (j < n - 1 && a[j] < a[j + 1]) j++;    //第一个判断条件为该节点是否有右孩子,第二个判断条件为右孩子是否比左孩子大,若是,则j代表右节点的下标
        if (temp > a[j]) flag = 1;
        else {
            a[i] = a[j];          //将j位置的值上移,并且j更新为其左孩子节点的值
            i = j;
            j = 2 * i + 1;     
        }
    }
    a[i] = temp;
}

//创建大根堆
static void InitCreatHeap(DataType a[], int n)
{
    for (int i = (n - 2) / 2; i >= 0; i--)            //(n-2)/2表示左后一个非叶子节点的下标
        CreatHeap(a, n, i);
}

3)算法思想

通过第二部分的操作,我们已经成功地把数组转换为了大根堆,接下来只需要不断将根节点元素与数组末尾元素进行交换,再更新大根堆即可。

为什么不从最后面的叶子节点开始拿?因为我们无法保证最后一个元素一定是最小的!

例如:(a)将88和5进行交换,随后为保持为大根堆,5与76交换,再与50交换,得到(b)。

4)代码

void Heap_Sort(DataType a[], int n)
{
    DataType temp;
    InitCreatHeap(a, n);    //先初始化整个数组为大根堆
    for (int i = n - 1; i > 0; i--)    //不断将根节点元素放与数组末尾元素进行交换
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        CreatHeap(a, i, 0);
    }
}

五、冒泡排序

1)算法思想

冒泡排序是从第一个元素开始,将相邻的元素两个两个进行比较,每趟比较都将集合中最大(或最小)的元素放到了集合末尾

2)代码

//冒泡排序
void Bubble_Sort(DataType a[], int n)
{
    DataType temp;
    int flag = 1;            //判断是否提前排序完成
    for (int i = n; i > 0 && flag; i--)
    {
        flag = 0;
        for (int j = 0; j < i-1; j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;                //仍然有元素进行交换,排序未完成
            }
        }
    }
}

六、快速排序

1)算法思想

快速排序定义了一个数组的下界low和上界high,然后通过两端的指针不断与low处的元素进行比较,将比low处的元素小的元素放到左边,将所有比他大的元素放到右边,这样一来,该元素的左边的元素都比他小,右边的元素都比他大,然后递归对左边和右边的集合进行快速排序即可。

2)代码

//快速排序
static void QuickSort(DataType a[], int low,int high)
{
    int i = low, j = high;
    DataType temp = a[low];

    while (i < j) {
        while (i < j && temp <= a[j])j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }

        while (i < j && temp >= a[i])i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
    }

    a[i] = temp;
    if(i>low) QuickSort(a, low, i - 1);
    if(j<high) QuickSort(a, j + 1, high);
}

诶!🧐这个排序有点不一样,前面的排序参数都是数组和元素个数,但是它居然有三个参数!逼死强迫症!为了使用时方便统一,我们封装一下:

//快速排序
void Quick_Sort(DataType a[], int n)
{
    QuickSort(a, 0, n - 1);   //注意上界和下界都是可取的
}

七、归并排序

1)算法思想

将具有n个元素的数组a看成n个长度为1的有序子数组,然后从第一个子数组开始,把相邻的两个子数组两两合并,然后再将合并后的数组两两合并,直到只剩下最后一个数组。

2)代码

//一次二路归并算法
static void Merge(DataType a[], int n, DataType swap[], int k)
{
    //k为有序子数组的长度,一次二路归并排序后的有序子数列存于swap
    int lower1 = 0;   //第一个有序子序列的下界
    int lower2, upper1, upper2,m = 0,i,j;
    while (lower1 + k <= n - 1) {
        lower2 = lower1 + k;       //第二个有序子数组的下界
        upper1 = lower2 - 1;       //第一个有序子数组的上界
        upper2 = (lower2 + k - 1 <= n - 1) ? lower2 + k - 1 : n - 1;//第二个有序子数组的上界

        //合并两个有序子数组
        for (i = lower1,j = lower2; i <= upper1 && j <= upper2; m++) {
            if (a[i] < a[j]) {
                swap[m] = a[i++];
            }
            else swap[m] = a[j++];
        }

        //如果子数组2已存完,则把数组1中剩余的元素存入swap
        while (i <= upper1) swap[m++] = a[i++];

        //如果子数组1已存完,则把数组2中剩余的元素存入swap
        while (j <= upper2) swap[m++] = a[j++];

        lower1 = upper2 + 1;
    }
    //如果原数组不能构成两组子数组,则直接存入swap
    for (int i = lower1; i < n; i++, m++)
        swap[m] = a[i];
}

//二路归并排序
void Merge_Sort(DataType a[], int n)
{
    DataType* swap = (DataType*)malloc(sizeof(DataType) * n);
    int k = 1;
    while (k < n)
    {
        Merge(a, n, swap, k);
        for (int i = 0; i < n; i++)
            a[i] = swap[i];
        k *= 2;
    }
    free(swap);
}

八、基数排序/桶排序(只对整数类型有效)

1)算法思想

设待排序的元素是m位的d进制的数,不足m位的在高位补0,设置d个桶(实际上是队列),其编号为0、1、2…d-1。首先按照元素的低位的数组依次把各元素放入相应编号的队列中,然后从小到大的编号依次出队列,放回到原数组,这样就完成了一轮排序。接着按高一位的数值再次放入桶中,再出队列,直到进行m轮排列,数组中的元素就有序了。

2)代码

这里我们使用链式队列

//桶排序
//针对整数类型
void Radix_Sort(DataType a[], int n, int m, int d)  //m位的d进制数
{
    int k, power = 1;
    QueuePtr* tub = (QueuePtr*)malloc(sizeof(QueuePtr) * d);
    if (tub == NULL)
    {
        printf("内存分配失败!\n");
        return;
    }
    for (int i = 0; i < d; i++) {
        LinkQueue_Init(&tub[i]);
    }

    //进行m次存放
    for (int i = 0; i < m; i++) {
        if (i == 0)power = 1;
        else power *= d;

        //将元素按关键字第k位的数值放入相应队列
        for (int j = 0; j < n; j++) {
            k = a[j] / power - (a[j] / (power * d)) * d;
            LinkQueue_Add(&tub[k], a[j]);
        }

        //顺序回收各队列中的元素至数值a中
        k = 0;
        for (int j = 0; j < n; j++) {
            while (!LinkQueue_Empty(tub[j])) {
                a[k++] = LinkQueue_Pop(&tub[j]);
            }
        }
    }
}

以上就是今天分享的全部内容,最后感谢你观看完我的文章,如果文章对你有帮助,可以点赞收藏评论,这是对作者最好的鼓励!不胜感激🥰

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/694199.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

电脑回收站清空了怎么恢复回来?分享四个好用数据恢复方法

电脑回收站清空了还能恢复回来吗&#xff1f;在使用电脑过程中&#xff0c;很多小伙伴都不重视电脑的回收站,&#xff0c;有用的没用的文件都往里堆积。等空间不够的时候就去一股脑清空回收站。可有时候会发现自己还需要的文件在回收站里&#xff0c;可回收站已经被清空了……那…

单灯双控开关原理

什么是单灯双控&#xff1f;顾名思义&#xff0c;指的是一个灯具可以通过两个不同的开关或控制器进行控制。 例如客厅的主灯可能会设置成单灯双控&#xff0c;一个开关位于门口&#xff0c;另一个位于房间内的另一侧&#xff0c;这样无论你是从门口进入还是从房间内出来&#x…

Meta首席AI科学家Yann LeCun指出生成式AI的不足

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

sqli-labs 靶场 less-11~14 第十一关、第十二关、第十三关、第十四关详解:联合注入、错误注入

SQLi-Labs是一个用于学习和练习SQL注入漏洞的开源应用程序。通过它&#xff0c;我们可以学习如何识别和利用不同类型的SQL注入漏洞&#xff0c;并了解如何修复和防范这些漏洞。Less 11 SQLI DUMB SERIES-11判断注入点 尝试在用户名这个字段实施注入,且试出SQL语句闭合方式为单…

插卡式仪器模块:数字万用表模块(插卡式)

• 6 位数字表显示 • 24 位分辨率 • 250 KSPS 采样率 • 电源和数字 I/O 均采用隔离抗噪技术 • 电压、电流、电阻、电感、电容的高精度测量 • 二极管/三极管测试 通道122输入 阻抗 电压10 MΩHigh-Z, 10 MΩ电流10 Ω50 mΩ / 2 Ω / 2 KΩ输入范围电压 5 V0–60 V电流…

Java桥接模式

桥接模式 最重要的是 将 抽象 与 实现 解耦 , 通过组合 在 抽象 与 实现 之间搭建桥梁 ; 【设计模式】桥接模式 ( 简介 | 适用场景 | 优缺点 | 代码示例 )-CSDN博客 桥接模式&#xff08;Bridge Pattern&#xff09;-&#xff08;最通俗易懂的案例&#xff09;_桥接模式 例子-…

SpringAI(二)

大模型:具有大规模参数和复杂计算结构的机器学习模型.通常由深度神经网络构建而成,拥有数十亿甚至数千亿个参数.其设计目的在于提高模型的表达能力和预测性能,应对复杂的任务和数据. SpringAI是一个AI工程领域的应用程序框架 大概推出时间是2023年7月份(不确定) 目的是将S…

Java 期末复习 习题集

&#x1f496; 单选题 &#x1f496; 填空题 &#x1f496; 判断题 &#x1f496; 程序阅读题 1. 读代码写结果 class A {int m 5;void zengA(int x){m m x;}int jianA(int y){return m - y;} }class B extends A {int m 3;int jianA(int z){return super.jianA(z) m;} …

【阿里YYDS】通义千问正式开源 Qwen2

Qwen2–72B正式开源&#xff0c;性能全面超越开源模型Llama3-70B&#xff0c;也超过文心4.0、豆包pro、混元pro等众多中国闭源大模型。 在过去一段时间里&#xff0c;Qwen系列模型从Qwen1.5升级到Qwen2&#xff0c;Qwen2分5个尺寸&#xff0c;包括Qwen2-0.5B、Qwen2-1.5B、Qwen…

RabbitMQ-topic exchange使用方法

RabbitMQ-默认读、写方式介绍 RabbitMQ-发布/订阅模式 RabbitMQ-直连交换机(direct)使用方法 目录 1、概述 2、topic交换机使用方法 2.1 适用场景 2.2 解决方案 3、代码实现 3.1 源代码实现 3.2 运行记录 4、小结 1、概述 topic 交换机是比直连交换机功能更加强大的…

CopyOnWriteArrayList详解

目录 CopyOnWriteArrayList详解1、CopyOnWriteArrayList简介2、如何理解"写时复制"3、CopyOnWriteArrayList的继承体系4、CopyOnWriteArrayList的构造函数5、CopyOnWriteArrayList的使用示例6、CopyOnWriteArrayList 的 add方法7、CopyOnWriteArrayList弱一致性的体现…

【BUG】已解决:ModuleNotFoundError: No module named ‘transformers‘

已解决&#xff1a;ModuleNotFoundError: No module named ‘transformers‘ 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身&#xff0c;就职于医疗科技公司…

Element-UI入门

目录 1.什么是Element-UI 2.作用 3.版本历史 4.优缺点 4.1.优点 4.2.缺点 5.应用场景 6.代码示例 7.未来展望 8.总结 1.什么是Element-UI Element-UI 是由饿了么前端团队开发的一套基于 Vue.js 的桌面端组件库。提供了一整套 UI 组件&#xff0c;使开发者能够快速构…

非线性模型预测控制NMPC例子

NMPC概述 非线性模型预测控制(Nonlinear Model Predictive Control, NMPC)是一种用于控制非线性系统的高级控制策略。与线性MPC不同,NMPC需要处理系统的非线性特性,这使得优化问题更加复杂。NMPC通常使用迭代优化算法来求解非线性优化问题 NMPC基本原理 NMPC的目标是最小…

社交“学习伙伴”:Meta Llama助力对话升级

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

程序猿大战Python——pycharm软件的使用

基础配置 目标&#xff1a;了解PyCharm软件的基础配置处理。 修改背景颜色&#xff1a; Appearance -> Theme 修改字体大小&#xff1a; 搜索font -> Font 例如&#xff0c;一起完成背景、字体大小的修改。 总结&#xff1a; &#xff08;1&#xff09;如果要对PyChar…

MAX7219(模拟SPI)驱动灯环的简单应用

文章目录 一、MAX7219是什么&#xff1f;二、使用步骤1.硬件1.1 引脚说明1.2 应用电路1.2.1 驱动数码管1.2.2 驱动点阵 2.软件2.1 时序2.2 寄存器2.2.1 掉电寄存器2.2.2 译码模式寄存器2.2.3 亮度寄存器2.2.4 扫描寄存器2.2.5 显示测试寄存器 2.3 初始化2.4 控制左侧灯环特定位…

【数据结构】排序——插入排序,选择排序

前言 本篇博客我们正式开启数据结构中的排序&#xff0c;说到排序&#xff0c;我们能联想到我之前在C语言博客中的冒泡排序&#xff0c;它是排序中的一种&#xff0c;但实现效率太慢&#xff0c;这篇博客我们介绍两种新排序&#xff0c;并好好深入理解排序 &#x1f493; 个人主…

MATLAB数学建模——数据拟合

文章目录 一、简介二、多项式拟合&#xff08;一&#xff09;指令介绍&#xff08;二&#xff09;代码 三、指定函数拟合&#xff08;一&#xff09;指令介绍&#xff08;二&#xff09;代码 一、简介 曲线拟合也叫曲线逼近&#xff0c;主要要求拟合的曲线能合理反映数据的基本…

一步一学!如何通过SOLIDWORKS曲面放样绘制花瓶?

SOLIDWORKS中&#xff0c;我们对放样凸台的操作已经非常熟悉。现在&#xff0c;我们将进一步探索曲面菜单栏中的放样成型功能。 1、绘制草图 首先&#xff0c;同普通放样凸台建模相同&#xff0c;绘制放样轮廓及引导线段。 可通过创建基准面布置轮廓&#xff0c;利用穿透选项将…