数据结构——排序
排序算法
- 前言
- 一、认识排序
- 排序的概念
- 常见的排序算法
- 排序实现的接口
- 二、常见排序算法的实现
- 插入排序
- 直接插入排序
- 希尔排序
- 选择排序
- 直接选择排序
- 堆排序
- 交换排序
- 冒泡排序
- 三、各个排序的效率比较
- 四、完整代码演示:
- shell_insert.h
- shell_insert.c
- test.c
- 总结
前言
来喽来喽~ 二叉树的层序遍历来喽~
层序遍历那是相当有趣滴!
我的朋友,请不要迷惘,你要记住,你终有鲲鹏一日!
加油吧!从现在开始~
一、认识排序
排序的概念
排序: 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
内部排序: 数据元素全部放在内存中的排序。
外部排序: 数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
常见的排序算法
排序实现的接口
后面我们再来对这些算法接口进行实现!
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
二、常见排序算法的实现
插入排序
基本思想:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
这就像是什么呢?对啦!这就像是我们玩扑克牌时将纸牌排序一样
直接插入排序
当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移
代码实现:
void InsertSort(int* a, int n) {// [0,end]有序,把end+1位置的插入到前序序列// 控制[0,end+1]有序for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end])//如果小于则将a[end]复制覆盖到后一位,tmp保存被覆盖的值{a[end + 1] = a[end];}else{break;}--end;//每次都往前比较}a[end + 1] = tmp;//将tmp保存值插入比它小的值的前面一位}
}
直接插入排序的特性总结:
- 元素集合越接近有序,直接插入排序算法的时间效率越高
- 时间复杂度:O(N^2)
- 空间复杂度:O(1),它是一种稳定的排序算法
- 稳定性:稳定
希尔排序
例:动图中gap=n/2
图例:
代码实现
void ShellSort(int* a, int n) {int gap = n;while (gap > 1)//当gap<=1则说明已经进行了最后的插入排序{gap = gap / 3 + 1;//gap每次缩小相应倍数,使得排序越来越接近有序,//+1使得gap最后一次排序为直接插入排序for (int i = 0; i < n - gap; ++i){int end = i;//end为该次排序起始位置下标int tmp = a[end + gap];//每次间隔gap个位置进行比较while (end >= 0)//此处为直接插入思想{if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//a[end + gap] = tmp;}}
}
希尔排序的特性总结:
稳定性:不稳定
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。*
希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定:
选择排序
基本思想:
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。
直接选择排序
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重复上述步骤,直到集合剩余1个元素
代码实现:
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;//记录末尾和开始位置while (begin < end)//当begin小于end说明数组没有被完全排序{// [begin, end]int mini = begin, maxi = begin;//将开始位置的值的下标赋予mini,maxifor (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi])//比开始位置值大则maxi记录这一位置的下标{maxi = i;}if (a[i] < a[mini])//比开始位置值小则mini记录这一位置的下标{mini = i;}}Swap(&a[begin], &a[mini]);//最小值与开始值交换// max如果被换走了,修正一下if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}
直接选择排序的特性总结:
- 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
- 时间复杂度:O(N^2)
- 空间复杂度:O(1)
- 稳定性:不稳定
堆排序
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
对于堆排序不熟悉的话可以看看前面的文章哦!
堆排序
代码实现:
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 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 = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆// O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
堆排序的特性总结:
- 堆排序使用堆来选数,效率就高了很多。
- 时间复杂度:O(N*logN)
- 空间复杂度:O(1)
- 稳定性:不稳定
交换排序
基本思想: 所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。
冒泡排序
冒泡排序应该是大家最熟悉的排序方式了吧!
代码实现:
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){int exchange = 0;//设置一个初值为0的变量,看这一次排序数组是否有变化for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;//如果发生了交换,则将exchange的值变为1}}if (exchange == 0)//exchange为0的话说明这一趟排序数组是有序的//所以跳出这一趟循环{break;}}
}
冒泡排序的特性总结:
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度:O(N^2)
- 空间复杂度:O(1)
- 稳定性:稳定
三、各个排序的效率比较
测试函数的定义
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = N - 1; i >= 0; --i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();SelectSort(a5, N);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("SelectSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);
}
测试结果:
从这次时间效率来看
堆排序>希尔排序>直接插入>选择排序>冒泡排序
四、完整代码演示:
shell_insert.h
#pragma once
#include<stdio.h>
void PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
void BubbleSort(int* a, int n);
void HeapSort(int* a, int n);
void SelectSort(int* a, int n);
shell_insert.c
#include "shell_insert.h"void PrintArray(int*a,int n) {for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void Swap(int* x, int* y) {int tmp = *x;*x = *y;*y = tmp;
}void InsertSort(int* a, int n) {for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];}else{break;}--end;}a[end + 1] = tmp;}
}void ShellSort(int* a, int n) {int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){int exchange = 0;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0){break;}}
}void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 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 = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}
test.c
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = N - 1; i >= 0; --i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();SelectSort(a5, N);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("SelectSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);
}int main()
{TestOP();return 0;
}
总结
今天的学习就到这里吧!
排序是一个相当有趣的课程!
相信大家学习完了之后也有与我相同的感受吧!
本篇文章图片部分来自网络!
相关文章:

数据结构——排序
排序算法 前言一、认识排序排序的概念常见的排序算法排序实现的接口 二、常见排序算法的实现插入排序直接插入排序希尔排序 选择排序直接选择排序堆排序 交换排序冒泡排序 三、各个排序的效率比较四、完整代码演示:shell_insert.hshell_insert.ctest.c 总结 前言 来…...
资深java面试题及答案整理
编写 Java 程序时, 如何在 Java 中创建死锁并修复它? 经典但核心Java面试问题之一。 如果你没有参与过多线程并发 Java 应用程序的编码,你可能会失败。 如何避免 Java 线程死锁? 如何避免 Java 中的死锁?是 Java 面试的热门问题之…...

buuctf-[网鼎杯 2020 朱雀组]phpweb
1.打开网站,吓我一跳 2.查看源代码,主要看到timezone,然后这个页面是五秒就会刷新一次 一开始去搜了这个,但是没什么用 3.使用bp抓包 会发现有两个参数,应该是用func来执行p 4.修改func和p file_get_contents&#…...

SpringBoot实战(二十四)集成 LoadBalancer
目录 一、简介1.定义2.取代 Ribbon3.主要特点与功能4.LoadBalancer 和 OpenFeign 的关系 二、使用场景一:Eureka LoadBalancer服务A:loadbalancer-consumer 消费者1.Maven依赖2.application.yml配置3.RestTemplateConfig.java4.DemoController.java 服务…...
文件挂载nas挂载
准备资源 nas服务器: 192.168.1.2 分配的nas卷名: mynasvolumename 在本地机器挂载nas卷 mkdir -p /mnt/localmountdir 执行挂载 mount -t nfs 192.168.1.2:mynasvolumename/ /mnt/localmountdir 本地进入nas目录 cd /mnt/localmountdir 可以…...

电影格式怎么转换mp4?电影格式转换教程
电影格式怎么转换mp4?平时喜欢看电影的小伙伴都知道,平时我们下载到的电影文件格式可谓是五花八门,如Mp4、Flv、AVI、WMV、MKV、MOV等。然而,相较于其他常用格式,MP4是一种使用最为广泛的视频格式,并且文件…...

HarmonyOS之 组件的使用
一 容器 1.1 容器分类 Column表示沿垂直方向布局的容器。Row表示沿水平方向布局的容器。 1.2 主轴和交叉轴 主轴:在Column容器中的子组件是按照从上到下的垂直方向布局的,其主轴的方向是垂直方向;在Row容器中的组件是按照从左到右的水平方向…...

IAM:身份验证与授权
身份验证和授权可能听起来相似,但在核心功能方面它们是不同的。身份验证和授权是在用户尝试访问其资源时执行的安全过程。身份验证和授权在防止网络安全漏洞和加强组织的安全系统方面发挥着至关重要的作用。 验证:验证用户的身份 - 用户是谁?…...

Linux——vi编辑器
目录 一、基本简介 二、命令模式下的常用按键 1、光标跳转按键 2、复制、粘贴、删除 三、编辑模式 四、末行模式 1、查找关键字并替换 2、保存退出 3、其他操作 五、模式切换 一、基本简介 1、最早可追随到1991年,全称为“Vi IMproved” 2、模式 ——命…...

【Linux学习笔记】权限
1. 普通用户和root用户权限之间的切换2. 权限的三个w2.1. 什么是权限(what)2.1.1. 用户角色2.1.2. 文件属性 2.2. 怎么操作权限呢?(how)2.2.1. ugo-rwx方案2.2.2. 八进制方案2.2.3. 文件权限的初始模样2.2.4. 进入一个…...

Aspose转pdf乱码问题
一、问题描述 在centos服务器使用aspose.word转换word文件为pdf的时候显示中文乱码(如图),但是在win服务器上使用可以正常转换 二、问题原因 由于linux服务器缺少对应的字库导致文件转换出现乱码的 三、解决方式 1.将window中字体(c:\windows\fonts)放到linux…...
table中的td内部的元素不能与td等高的问题
解决该问题的办法: td标签内部的元素使用table布局,但是需要注意的是td必须设置高度,高度为任意值都可以,虽然设置了高度,但是td依然会被内部内容的高度撑开 <template><table><tr><td><div class&q…...
Layui + Flask | 实现数据表格修改(案例篇)(09)
此案例内容比较多,建议滑到最后点击阅读原文,阅读体验更佳。后续也会录制案例视频,将在本周内上传到同名的 b 站账号。 接下来演示用 flask + layui 搭建一个学员信息管理的案例 这个案例将会利用 flask 做后端,layui table 组件做前端,基于 restful api 完成一个学员信息…...

BCC源码编译和安装
接前一篇文章:BCC源码下载 1. 进入源码根目录 进入到BCC源码根目录。命令及结果如下: $ cd bcc ~/eBPF/BCC/bcc$ ls cmake CONTRIBUTING-SCRIPTS.md docs images libbpf-tools man scripts src CMakeLists.txt …...

linux上gitlab备份与还原
三 Gitlab备份 1.gitlab安装 1.1 添加镜像地址 添加镜像地址的目的是为了提高国内用户软件下载的速度,编辑(新建)文件gitlab-ce.repo,指令: vi /etc/yum.repos.d/gitlab-ce.repo复制 输入: [gitlab-ce] namegitlab-ce # 清华…...

【精华】具身智能:人工智能的下一个浪潮
从符号主义到联结主义,智能体与真实世界的交互得到日益重视。上世纪五十年代的达特茅斯会议之后的一段时期内,对人工智能的研究主要限于符号处理范式(符号主义)。符号主义的局限性很快在实际应用中暴露出来,并催动了联…...

【线性回归、岭回归、Lasso回归分别预测患者糖尿病病情】数据挖掘实验一
Ⅰ、项目任务要求 任务描述:将“diabetes”糖尿病患者数据集划分为训练集和测试集,利用训练集分别结合线性回归、岭回归、Lasso回归建立预测模型,再利用测试集来预测糖尿病患者病情并验证预测模型的拟合能力。具体任务要求如下: …...

037:vue项目监听页面变化,动态设置iframe元素高度
第037个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 (1)提供vue2的一些基本操作:安装、引用,模板使…...
探索前端生成二维码技术:简单实用的实现方式
引言 随着智能手机的普及,二维码已经成为了现代生活中不可或缺的一部分。在许多场景下,我们都需要将某些信息或链接以二维码的形式展示出来。本文将介绍一种简单实用的前端生成二维码的技术,并给出具体的代码示例。 二维码生成原理 首先&a…...

python装13的一些写法
一些当你离职后,让老板觉拍大腿的代码 1. any(** in ** for ** in **) 判断某个集合元素,是否包含某个/某些元素 代码: if __name__ __main__:# 判断 list1 中是否包含某个/某些元素list1 [1,2,3,4]a any(x in [5,4] for x in list1) 输…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...