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

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

前言:

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

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

        例如:

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

相关文章

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

python连接本地SQL server详细图文教程

《python连接本地SQLserver详细图文教程》在数据分析领域,经常需要从数据库中获取数据进行分析和处理,下面:本文主要介绍python连接本地SQLserver的相关资料,文中通过代码... 目录一.设置本地账号1.新建用户2.开启双重验证3,开启TCP/IP本地服务二js.python连接实例1.

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比