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

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

前言:

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

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

        例如:

        最简单的冒泡排序,时间复杂度为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

相关文章

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

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

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

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

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

HTML img标签和超链接标签详细介绍

《HTMLimg标签和超链接标签详细介绍》:本文主要介绍了HTML中img标签的使用,包括src属性(指定图片路径)、相对/绝对路径区别、alt替代文本、title提示、宽高控制及边框设置等,详细内容请阅读本文,希望能对你有所帮助... 目录img 标签src 属性alt 属性title 属性width/h

CSS3打造的现代交互式登录界面详细实现过程

《CSS3打造的现代交互式登录界面详细实现过程》本文介绍CSS3和jQuery在登录界面设计中的应用,涵盖动画、选择器、自定义字体及盒模型技术,提升界面美观与交互性,同时优化性能和可访问性,感兴趣的朋... 目录1. css3用户登录界面设计概述1.1 用户界面设计的重要性1.2 CSS3的新特性与优势1.

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布局和层叠关