数据结构——排序
排序算法
- 前言
- 一、认识排序
- 排序的概念
- 常见的排序算法
- 排序实现的接口
- 二、常见排序算法的实现
- 插入排序
- 直接插入排序
- 希尔排序
- 选择排序
- 直接选择排序
- 堆排序
- 交换排序
- 冒泡排序
- 三、各个排序的效率比较
- 四、完整代码演示:
- 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) 输…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...