基本的五大排序算法

目录

一,直接插入算法

二,希尔排序算法

三,选择排序

四,堆排序

五,冒泡排序算法


简介:

        排序算法目前是我们最常用的算法之一,据研究表明,目前排序占用计算机CPU的时间已高达百分之30到百分之50。可见,高效率的排序算法是我们必须掌握的基本算法之一,本篇博客就先跟大家介绍五种常用的排序算法:直接插入算法,希尔算法,选择算法,堆排序算法,冒泡算法。

一,直接插入算法

        直接插入算法的原理与我们打扑克牌时,进行不摸牌排序的效应一样。平常我们在打扑克牌时会不断的摸牌,每当我们摸到一个牌时就会往里面插入,使得我们手中的排有序。直接插入算法与之同理,其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列种,直到所有的记录插入完为止,得到一个新的有序序列,即摸牌效应,如下图,是插入排序的示意图:cbbddbcf00724df98c8b5eba624928ea.gif


        明白以上原理后,接下来要思考的是此算法的效率如何,不难发现,当为最好情况时(即有序排列),将一次性直接遍历整个数组,时间复杂度为O(N);当为最坏情况是(即要跟排列的顺序相反),需要一直往首元素插入,此时的时间复杂度为O(N^2)。具体代码如下:

#include <stdio.h>
//直接插入算法
void InsertSort(int* a, int n) {for (int i = 0; i < n - 1; i++) {// [0,end]有序,把end+1位置的插入到前序序列,控制[0,end+1]有序int end = i;int next = a[i + 1];// 升序排列while (end >= 0) {if (a[end] > next) {a[end + 1] = a[end];}else {break;}end--;}a[end + 1] = next;}
}
int main() {int a[] = { 5,9,7,3,0,1,4,2,6,8 };InsertSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++) {fprintf(stdout, "%d ", a[i]);}puts("");return 0;
}

运行图:

8c03d4451dab45979beda78308fd8322.png


二,希尔排序算法

        希尔排序是以插入排序为基础的排序。首先,该算法要设置一个分组,然后再用直接插入算法的思想进行预排序,预排序是将数据分组排序,每组数据之间有着一定的间距。如下图:

c00f8c71fda44afab1b44f5fdaa8d8f3.png

        上图中,第一组数据:9,5,8,5。第二组数据:1,7,6。第三组数据:2,4,3。三组数据先分别用直接插入算法进行预排序,排序后第一组数据为5,5,8,9。第二组数据为1,6,7。第三组数据为2,3,4。经过这些预排序后,整体的数据为5  1  2  5  6  3  8  7  4  9(不同颜色代表不同组中的数据,可直观的看出)。

        其中,将数据进行预排序的目的是大的数据更快的到后面去,小的数据更快的到前面去,其中,间距越大跳得越快,越不接近有序;间距越小跳得越慢,越接近有序,当间距为1时,直接为有序,因为,当间距为1时就是直接插入排序。

        希尔算法运用得原理就是给定一个间距值进行预排序,当间距值大于1时进行的排序为预排序,当间距值等于1时的排序就是直接插入排序,即排序已完成。本算法的效率很高,但时间复杂度很难计算出,暂时先不研究这个,代码实现具体如下:

#include <stdio.h>
//希尔排序算法
void ShellSort(int* a, int n) {int grab = n;//开始时,设置间距grab = n;//当grab == 1时为直接插入算法,当grab > 1时为预排序while (grab != 1) {//grab /= 2;//不断的缩减grab的大小,直到grab == 1排序完成//由于grab一次性的缩减比较小,导致算法效率较低,以下的grab为改进算法,提高算法效率grab = grab / 3 + 1;//不断缩减间距grab的大小,直到grab == 1排序完成//以下是根据间距grab的大小来进行的插入排序for (int j = 0; j < grab; j++) {for (int i = j; i < n - grab; i += grab) {int end = i;int x = a[i + grab];while (end >= 0) {if (a[end] > x) {a[end + grab] = a[end];}else {break;}end -= grab;}a[end + grab] = x;}}}
}
int main() {int a[] = { 5,9,7,3,0,1,4,2,6,8 };ShellSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++) {fprintf(stdout, "%d ", a[i]);}puts("");return 0;
}

运行图:

becf500f9ba94dafb29bbf8610299968.png


三,选择排序

1,选择排序的基本思想:

        每一次从待排序的数据元素中选出最小或最大的一个元素,存放在系列的起始位置,即进行一趟选择,直到全部待排序的数据元素排完,其中时间复杂度:O(N^2)。空间复杂度:O(1)。如下图:

1b799e0b19b44a5bad38455dd945756e.gif


        以上就是选择排序的基本套路,但我们仔细思考下来,其实这种方法还有优化空间,当数据进行一趟选择时,我们可直接选出最大数和最小数,将其放在开头或末尾。然后再次进行遍历,直到头尾遍历相遇为止。代码如下:

#include <stdio.h>
//选择算法
void Swap(int* x1, int* x2) {int t = *x1;*x1 = *x2;*x2 = t;
}
void SelectSort(int* a, int n) {int begin = 0, end = n - 1;while (begin < end) {int max = begin, min = begin;//进行一趟遍历,确定最小值和最大值的下标,当前面遍历等于end时排序就已排好for (size_t i = begin + 1; i < end; i++) {if (a[max] < a[i]) {max = i;}if (a[min] > a[i]) {min = i;}}Swap(a + max, a + end);//当min在最后时,max与原先的end交换了位置,所以这时的end的下标已经变了if (min == end) {min = max;}Swap(a + min, a + begin);//前面排好,往后前进begin++;//后面排好,往前前进end--;}
}
int main() {int a[] = { 5,9,7,3,0,1,4,2,6,8 };SelectSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++) {fprintf(stdout, "%d ", a[i]);}puts("");return 0;
}

运行图:

bb38e77485f7424887864e60aafa71a5.png


四,堆排序

        堆排序跟二叉堆排序一模一样,即先建立堆结构,然后进行堆的调整,使整体有序。要注意的是,升序排列首选大堆,降序排列首选小堆建立。(这一原理运用的是二叉树的知识,如若感觉有困难,就必须先把二叉树的堆结构再学习下。不建议直接上来搞这一块知识)。其中结构上是选择堆结构上的选择排序,结构图如下:

7ce2be480a244150a4d25854eb4de07c.png

        由于原理与之前的二插堆一样,在这里就不做过多结构上的说明,下面是代码的实现和讲解:

#include <stdio.h>
void Swap(int* x1, int* x2) {int t = *x1;*x1 = *x2;*x2 = t;
}
//归并算法
void Adjustdown(int* a, int n, int parent) {int child = 2 * parent + 1;while (child < n) {if (child + 1 < n && a[child] < a[child + 1]) {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) {//从最后一层走起,因为要保证导入的parent往下都是有序的,即大堆建立for (int i = (n - 1 - 1) / 2; i >= 0; i--) {Adjustdown(a, n, i);}//大堆建立后根为最大数,然后进行排序int end = n - 1;while (end > 0) {Swap(a, a + end);//因为根为最大数,要升序就要把最大数放入最后Adjustdown(a, end, 0);end--;}
}
int main() {//归并算法int a[] = { 5,9,7,3,0,1,4,2,6,8 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++) {fprintf(stdout, "%d ", a[i]);}puts("");return 0;
}

运行图:

733610906033452682b0570acb3e9784.png


五,冒泡排序算法

        冒泡排序是一种交换排序,所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,此种交换的特点是将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动,其中时间复杂度:O(N^2);空间复杂度:O(1)。

冒泡排序的原理图:

c28419fdc0f441048b337a84ca87b598.gif

此种排序非常简单,具体代码如下:

#include <stdio.h>
void Swap(int* x1, int* x2) {int t = *x1;*x1 = *x2;*x2 = t;
}
//冒泡排序算法
void BubbleSort(int* a, int n)
{for (size_t j = 0; j < n; j++){//用x进行控制,可提升算法的效率int x = 0;for (size_t i = 1; i < n - j; i++){//进行排序,当没有进入此步时,说明是有序的if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);x = 1;}}//当x == 0时,说明序列是有序的,可直接跳出,提升算法的效率if (x == 0){break;}}
}
int main() {//冒泡算法int a[] = { 5,9,7,3,0,1,4,2,6,8 };BubbleSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++) {fprintf(stdout, "%d ", a[i]);}puts("");return 0;
}

运行图:

6060a2e144b746dc96dd61380f7eb6e4.png


总:在五种排序算法中,效率最高的是希尔排序,效率最低的是冒泡排序,堆排序与希尔不相上下,但堆排序实现起来比较麻烦,因此个人建议首选希尔,直接插入算法比选择排序算法和冒泡略高一筹,但在进行大量数据排序时,效率都不高,因此,在五大基本排序中,希尔排序为最佳选择。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux环境下gdb调试方法与演示

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【Linux专栏】&#x1f388; 本专栏旨在分享学习Linux的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 演示环境&#xff1…

OpenCV 14(角点特征Harris和Shi-Tomasi)

一、角点 角点是图像很重要的特征,对图像图形的理解和分析有很重要的作用。角点在三维场景重建运动估计&#xff0c;目标跟踪、目标识别、图像配准与匹配等计算机视觉领域起着非常重要的作用。在现实世界中&#xff0c;角点对应于物体的拐角&#xff0c;道路的十字路口、丁字路…

BP神经网络的MATLAB实现(含源代码)

BP(back propagation)神经网络是1986年由Rumelhart和McClelland为首的科学家提出的概念&#xff0c;是一种按照误差逆向传播算法训练的多层前馈神经网络&#xff0c;是应用最广泛的神经网络模型之一 具体数学推导以及原理在本文不做详细介绍&#xff0c;本文将使用MATLAB进行B…

106.从中序与后序遍历序列构造二叉树

力扣题目链接(opens new window) 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如&#xff0c;给出 中序遍历 inorder [9,3,15,20,7]后序遍历 postorder [9,15,7,20,3] 返回如下的二叉树&#xff1a; class Solution { public:Tr…

c++-vector

文章目录 前言一、vector介绍二、vector使用1、构造函数2、vector 元素访问3、vector iterator 的使用4、vector 空间增长问题5、vector 增删查改6、理解vector<vector< int >>7、电话号码的字母组合练习题 三、模拟实现vector1、查看STL库源码中怎样实现的vector2…

【Java 进阶篇】JDBC查询操作详解

在数据库编程中&#xff0c;查询是一项非常常见且重要的操作。JDBC&#xff08;Java Database Connectivity&#xff09;提供了丰富的API来执行各种类型的查询操作。本篇博客将详细介绍如何使用JDBC进行查询操作&#xff0c;包括连接数据库、创建查询语句、执行查询、处理结果集…

ElasticSearch第四讲:ES详解:ElasticSearch和Kibana安装

ElasticSearch第四讲&#xff1a;ES详解&#xff1a;ElasticSearch和Kibana安装 本文是ElasticSearch第四讲&#xff1a;ElasticSearch和Kibana安装&#xff0c;主要介绍ElasticSearch和Kibana的安装。了解完ElasticSearch基础和Elastic Stack生态后&#xff0c;我们便可以开始…

关于算法复杂度的几张表

算法在改进今天的计算机与古代的计算机的区别 去除冗余 数据点 算法复杂度 傅里叶变换

ASUS (k013) ME176CX不进入系统恢复出厂设置的方法

k013 me176cx ASUS k013 ME176CX不进入系统恢复出厂设置的方法 当忘记系统密码或系统异常导致无法进入系统时&#xff0c;可以按以下步骤尝试不进入系统恢复出厂设置来解决。 注意&#xff1a;执行恢复出厂设置前&#xff0c;请先将资料备份至外接设备&#xff0c;否则资料都…

基于MFC和OpenCV实现人脸识别

基于MFC和OpenCV实现人脸识别 文章目录 基于MFC和OpenCV实现人脸识别1. 项目说明1. 创建项目2. 启动窗口3. 登录窗口-添加窗口、从启动窗口跳转4. 启动窗口-美化按钮5. 登录窗口-美化按钮、雪花视频6. 注册窗口-美化按钮、雪花视频、从启动窗口跳转7. 注册窗口-开启摄像头8. 注…

知识图谱小白入门(1):neo4j的安装与CQL的使用

文章目录 序一、安装neo4j1.1 下载neo4j1.2 安装JDK1.3 BUG&#xff1a;dbms failed to start 二、CQL语法2.1 CQL语法创建节点查询节点创建关系查询关系2.2 习题 习题答案 序 知识图谱&#xff0c;是一种实体间的信息与关系知识的网状结构&#xff0c;借用图论中点与边的概念…

自动驾驶中的感知模型:实现安全与智能驾驶的关键

自动驾驶中的感知模型&#xff1a;实现安全与智能驾驶的关键 文章目录 引言感知模型的作用感知模型的技术安全与挑战结论 2023星火培训【专项营】Apollo开发者社区布道师倾力打造&#xff0c;包含PnC、新感知等的全新专项课程上线了。理论与实践相结合&#xff0c;全新的PnC培训…

力扣练习——链表在线OJ

目录 提示&#xff1a; 一、移除链表元素 题目&#xff1a; 解答&#xff1a; 二、反转链表 题目&#xff1a; 解答&#xff1a; 三、找到链表的中间结点 题目&#xff1a; 解答&#xff1a; 四、合并两个有序链表&#xff08;经典&#xff09; 题目&#xff1a; 解…

opencv实现目标跟踪及视频转存

创建跟踪器 def createTypeTracker(trackerType): 读取视频第一帧&#xff0c;选择跟踪的目标 读第一帧。 ok, frame video.read() 选择边界框 bbox cv2.selectROI(frame, False) 初始化跟踪器 tracker_type ‘MIL’ tracker createTypeTracker(tracker_type) 用第一…

SpringBoot的全局异常拦截

在 Spring Boot 中&#xff0c;可以通过使用 ControllerAdvice 注解和 ExceptionHandler 注解来实现全局异常拦截。 RestControllerAdvice RestControllerAdvice 是 Spring Framework 提供的注解&#xff0c;用于定义全局异常处理类&#xff0c;并且结合 ExceptionHandler 注…

Rabbitmq安装-docker版

1.简介 2.安装消息队列 下载地址https://www.rabbitmq.com/download.html 使用docker方式安装 需要先下载docker&#xff0c;参考文章https://blog.csdn.net/weixin_43917045/article/details/104747341?csdn_share_tail%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22arti…

基于matlab创作简易表白代码

一、程序 以下是一个基于MATLAB的简单表白代码&#xff1a; % 表白代码 clc; % 清除命令行窗口 clear; % 清除所有变量 close all; % 关闭所有图形窗口 % 输入被表白者的名字 name input(请输入被表白者的名字&#xff1a;, s); % 显示表白信息 fprintf(\n); fprintf(亲爱的…

力扣刷题-哈希表-三数之和

15 三数之和 给你一个包含 n 个整数的数组 nums&#xff0c;判断 nums 中是否存在三个元素 a&#xff0c;b&#xff0c;c &#xff0c;使得 a b c 0 &#xff1f;请你找出所有满足条件且不重复的三元组。 注意&#xff1a; 答案中不可以包含重复的三元组。 示例&#xff1a…

由于计算机中丢失msvcp110.dll的解决方法与msvcp110.dll丢失修复方法

相信大家在打开电脑软件或许游戏都有遇到过电脑提示找不到msvcp110.dll文件&#xff0c;导致软件游戏打不开&#xff0c;我们应该怎么办&#xff1f;不用着急&#xff0c;今天小编我分享我找了很久成功解决问题的方法给大家&#xff0c;希望可以帮到各位。 1. 使用DLL修复工具&…

【word】从正文开始设置页码

在写报告的时候&#xff0c;会要求有封面和目录&#xff0c;各占一页。正文从第3页开始&#xff0c;页码从正文开始设置 word是新建的 分出三节&#xff08;封面、目录、正文&#xff09; 布局--->分割符--->分节符--->下一页 这样就能将word分为3节&#xff0c;分…