排序算法(动图详细讲解)(直接插入排序,希尔排序,堆排序,冒泡排序)

本文主要是介绍排序算法(动图详细讲解)(直接插入排序,希尔排序,堆排序,冒泡排序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

        排序的方式有很多种,不同的排序思想是不一样的。

        但是排序的时间复杂度和空间复杂度也都有区别。

        例如:

        最简单的冒泡排序,时间复杂度为O(N)

        对排序的时间复杂度为O(N*logN)

接下来就来仔细分析每种排序的思路,并写出代码。

插入排序:

 基本思想:
        直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

总而言之要插入第n个数,必须保证前面n-1个数是有序的。

直接插入排序:

        直接动画展示:

        

注意事项:

        1、在插入下一个元素时,必须保证前面的元素是有序的

        2、取出一个元素后,与其他元素比较,如果其他元素比去除的元素大,则往后覆盖,否则插入在比较元素的后面

代码如下:

        

void InsertSort(int *a,int n)
{int end = 0;int tmp = a[end + 1];for (int i = 0; i < n-1; i++){end = i;tmp = a[end + 1];//记录后一个元素while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

直接插入排序的特性总结:
1. 元素集合越接近有序,直接插入排序算法的时间效率越高
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1),它是一种稳定的排序算法
4. 稳定性:稳定 

希尔排序(缩小增量排序):

      希尔排序法又称缩小增量法。希尔排序法的基本思想是:

        先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

简而言之,希尔排序就是直接插入排序的进阶版,考虑了一个更加优化的一个算法。

思路如下:

gap表示第一个数经过gap个到下一个数。(这里gap不是表示一相隔几个数):

例如:

主要思想就是,先进行两两比较,如果是升序,就先将小的数换到左边,大的换到右边。

直到gap等于1时,就回到了直接插入排序。(这里的gap可以自己设定,只需最后等于1即可)

此时进行直接插入排序时效率会提升不少。

这样进行效率会高很多。

代码如下:

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;}}
}

选择排序:

基本思想:
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

直接选择排序:

 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素。

过程如下:

代码如下:

void swap(int *a,int *b)
{int c = *a;*a = *b;*b = c;
}
void SelectSort(int *a,int n)//方式一
{int min = 0;for (int i = 0; i < n; i++){min = i;for (int j = i; j < n; j++){if (a[j] < a[min]){min = j;}}swap(&a[min], &a[i]);}
}

堆排序:

        堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆
        (如果对堆不太了解的话,可以看之前的博客哦,快速学习初阶“堆“(数据结构C语言)-CSDN博客)

代码如下:
        

void AdjustDown(int *a,int n,int root)
{int child = root * 2 + 1;while (child<n){if (child+1<n&&a[child + 1] > a[child]){child++;}if (a[child] > a[root]){swap(&a[child], &a[root]);root = child;child = root * 2 + 1;}else{break;}}
}
void HeapSort(int *a,int n)
{//建大堆for (int i = 0; i < (n - 1 - 1) / 2; i++){AdjustDown(a,n,i);}//堆排序for (int j = 0; j < n; j++){swap(&a[0], &a[n -j-1]);//先交换堆顶和堆尾AdjustDown(a,n-1-j,0);//直接对剩下的向下调整}
}

冒泡排序:

        简单说就是从右往左排,如或是升序,依次比较找最大的。如果是降序,一次比较找最小的。(这个很简单就不多说啦。)

代码如下:

void BubbleSort(int *a,int n)
{int i = 0;for (i = 0; i < n-1; i++){for (int j = 0; j < n - i-1; j++){if (a[j] > a[j + 1]){swap(&a[j], &a[j + 1]);}}}
}


        

这篇关于排序算法(动图详细讲解)(直接插入排序,希尔排序,堆排序,冒泡排序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1133140

相关文章

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)