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

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

前言:

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

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

        例如:

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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Centos环境下Tomcat虚拟主机配置详细教程

《Centos环境下Tomcat虚拟主机配置详细教程》这篇文章主要讲的是在CentOS系统上,如何一步步配置Tomcat的虚拟主机,内容很简单,从目录准备到配置文件修改,再到重启和测试,手把手带你搞定... 目录1. 准备虚拟主机的目录和内容创建目录添加测试文件2. 修改 Tomcat 的 server.X

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring Boot拦截器Interceptor与过滤器Filter详细教程(示例详解)

《SpringBoot拦截器Interceptor与过滤器Filter详细教程(示例详解)》本文详细介绍了SpringBoot中的拦截器(Interceptor)和过滤器(Filter),包括它们的... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)详细教程1. 概述1

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使