【排序算法动画解】排序介绍及冒泡排序

二十二画程序员 等级 1125 1 0

本文为系列专题【数据结构和算法:简单方法】的第 12 篇文章。

  1. 数据结构 | 顺序表
  2. 数据结构 | 链表
  3. 数据结构 | 栈
  4. 数据结构 | 队列
  5. 数据结构 | 双链表和循环链表
  6. 数据结构 | 二叉树的概念和原理
  7. 数据结构 | 二叉树的创建及遍历实现
  8. 数据结构 | 线索二叉树
  9. 数据结构 | 二叉堆
  10. 算法 | 顺序查找和二分查找
  11. 数据结构 | 二叉查找树

本文先简单介绍一下什么是排序,然后再结合动画介绍暴力排序和冒泡排序。

1. 什么是排序?

排序在日常生活中无处不在。比如考试成绩的排名、体育课的从低到高的队形、网购时按价格升序排列或降序排列等等。

姓名 学号 班级 成绩
张三 1001 2班 100
李四 1003 1班 90
王五 1000 3班 80
赵六 1006 2班 70

在该表格中,我们称一行数据为一条记录,其中姓名、学号等数据项是关键字,关键字是我们排序的依据。关键字可以是主关键字或次关键字,甚至是若干数据项的组合。

比如,在该表格中,我们是按照成绩(次关键字)从高到低降序排序的。也可以按照学号排序,或者按照学号和成绩同时排序:先按成绩降序排列,成绩相同的,按照学号升序排列。

所以,对多条记录排序的本质是对关键字的排序,如果排序依据是多个关键字,可以转化为单个关键字的排序。

所谓排序,是指按指定的关键字,将某个序列的所有元素以有序的方式排列起来

如何实现排序呢?

比如上体育课时按身高的排序,就是比较两个人的身高,然后矮的站前面,高的站后面。如果高的在前,矮的在后,就交换位置;否则就用不动。

没错,排序是借助比较和交换来实现的。比较的是关键字,这是我们排序的依据。交换的是两个元素的位置,通常我们不真的交换位置,而是借助中间变量的赋值来实现交换位置的效果。

/*一个交换函数,交换数组中下标为i和j的元素位置*/
void swap(int *array, int i, int j)
{
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

在实现排序算法时,我们应当追求更少次数的比较和交换,这样才能提高算法的性能

为了后面说明问题方便起见,这里约定几个规则:

  • 只对数组排序,并约定数组长度 length = 10
  • 全部排序算法均按升序排序
  • 由于是针对数组,所以关键字就是其元素值本身。比较关键字即是比较元素值,不再区分。

2. 暴力排序(Violent Sort)

所谓暴力,是指没有任何技巧而言的方式,它直接粗暴地遍历真个数组,从而不停的进行比较和交换。这是最容易理解的排序算法。

核心思想:从数组的第一个元素开始,将每个元素作为基准元素,基准元素和其后面的所有元素比较,如果基准元素大于其后的某个元素,则与其交换位置;否则位置不变。

当基准元素和其后的所有元素比较交换完后,最小值一定被排好了,此时就说一排序完成了,每轮排序有若干次循环,用于比较和交换。像这样进行若干轮的排序后,排序就完成了。

我们需要两个变量,用于标记两个进行比较的元素下标:

  • 变量 i:某个元素的下标;
  • 变量 j:下标 i 之后的下标。

我们需要两个嵌套循环:

  • 外层循环控制轮数;
  • 内层循环控制每轮的比较和交换。

动态过程如下:

【排序算法动画解】排序介绍及冒泡排序

代码实现如下:

/* 暴力排序
 * array : 数组
 * length : 数组长度
 */
void violent_sort(int *array, int length)
{
    int i, j;
    // 外层循环,遍历数组,控制轮数
    for (i = 0; i < length; i++) {
        // 内层循环,循环比较 array[i] 和其之后的元素,控制循环次数
        for (j = i + 1; j < length; j++) {
            if (array[i] > array[j]) { // 如果大于则交换
                swap(array, i, j);
            }
        }
    }
}

通过以上的暴力排序,我们能够初体会排序的思想,即不断地比较和交换

暴力排序有其明显的缺点,即每个元素都要和其之后的所有的元素比较,这就很容易破坏整个数组的原来顺序,比如在上面的动态过程中,元素 40 在某次交换后被交换到了更靠后的位置。为了排好某个元素,而对其之后的所有元素大动干戈,甚至破坏了它们原来之间的顺序,这就影响了效率。

3. 冒泡排序(Bubble Sort)

冒泡排序是一种很简单的排序算法,由暴力排序改进而来。

核心思想:比较相邻的两个元素,当前者大于后者时,交换二者位置;否则位置不变。

注意:冒泡排序是相邻的两个元素比较并交换,而暴力排序是某个元素和其之后的所有元素比较并交换。

当数组中所有的相邻元素进行两两比较和交换后,一定会找到一个最大值,并且最大值被交换到数组尾处,此时说一轮排序完成了,一轮排序中有若干次循环,用于比较和交换。像这样进行若干轮排序后,排序就完成了。

我们需要两个变量:

  • 变量 i:用于控制轮数;

  • 变量 j:元素下标,j+1 为其相邻元素的下标。

我们需要两个嵌套循环:

  • 外层循环控制轮数
  • 内层循环控制每轮所有相邻元素的比较和交换

动态过程如下:

【排序算法动画解】排序介绍及冒泡排序

代码实现如下:

/* 冒泡排序
 * array : 数组
 * length : 数组长度
 */
void bubble_sort(int *array, int length)
{
    int i, j;
    // 外层循环,控制轮数。每一轮排好一个元素
    for (i = 0; i < length; i++) {
        // 内层循环,循环比较数组中未排序的元素
        for (j = 0; j < length - i - 1; j++) {
            // 若前者大于后者则交换
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}

由于是相邻的两个元素进行比较,所以一轮比较后,一定有一个最大的元素被交换到最右边,像“大泡泡”浮到水面上一样,所以我们称其为“冒泡排序”。

冒泡排序虽然改善了暴力排序的缺点,但仍然具有可优化的地方。

在上述动态过程中,第 7 轮(i = 6)时就已经完成排序了,但后面仍然进行了 3 轮的比较。这最后 3 轮是完全没必要的,所以我们可以改进一下,避免没必要的比较。

方法就是增加一个标志变量 unsorted,用于标志数组是否已经有序,unsorted = 0 时数组有序,unsorted = 1 时数组无序。

unsorted 通过记录在某轮排序中是否发生了交换,如果没发生,就意味着已经有序。

void bubble_sort_v3(int *array, int length)
{
    int i, j;
    int unsorted = 1; // 标识变量
    for (i = 0; i < length && unsorted; i++) {
        unsorted = 0;
        for (j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                unsorted = 1; // 发生交换,说明尚未有序
            }
        }
    }
}

虽然冒泡排序可以避免一些不必要的比较和交换,但是冒泡排序本质仍和暴力排序相似,即不断地大量交换,或是某个元素和其后所有元素的交换,或是两个相邻元素的交换。通过动图也可以看出,要使一个元素排到其正确的位置上,我们往往需要和多个元素相交换,这是影响效率的“硬伤”

完整代码请移步至 GitHub | Gitee 获取。

如有错误,还请指正。

如果觉得写的不错,可以点个赞和关注。后续会有更多数据结构和算法相关文章。

【排序算法动画解】排序介绍及冒泡排序

收藏
评论区

相关推荐

尤雨溪:TypeScript不会取代JavaScript
近日,Evrone 与 Vue.js 的作者尤雨溪进行了一次访谈,了解他对于无后端与全栈方法、以及 Vue.js 适用场景的看法,还有他本人如何在工作与生活之间取得平衡。 记者: 嗨 Evan,很荣幸你能接受我们的访谈。那就先从一个简单的问题开始:您的全职工作岗位是由 Patreon 资助的,大多数人恐怕都没有这样的机会。您能聊聊怎样在工作与生活之间找到
android view 常用的6种 View 的滑动方法
View 的滑动是Android 实现自定义控件的基础,实现View 滑动有很多种方法,在这里主要讲解6 种滑动方法,分别是layout()、offsetLeftAndRight()与offsetTopAndBottom()、LayoutParams、动画、scollTo 与scollBy,以及Scroller。   View 的滑动是Android
教你用Python制作炫酷的词云
相信大家也都通过各种渠道了解了老干妈与鹅厂的爱恨纠缠,当然其中还混入了迷惑行为的“骗子”、吃瓜吃得飞起的“阿里系”以及连称此事与我无关的“某搜索引擎”。 不过这是一篇技术文,所以无心管他到底是谁的老千妈,一心只想给大家介绍这个惊艳的好东西。 (https://imghelloworld.osscnbeijing.aliyuncs.com/4
一文搞懂什么是HTTP与HTTPS
(https://blog.csdn.net/petterp/article/details/102779257)Http与Https的区别。 在最近的开发中,深感网络相关基础知识薄弱,于是趁周末好好总结一
13. 如果自己写的 Python 程序出错了,怎么办?
本篇文章主要内容为程序错误与异常处理,顺带会说一下内置模块 logging 。 <center<font colorred缓解一下视疲劳</font</center 13. 如果自己写的 Python 程序出错了,怎么办?(https://imghelloworld.osscnbeijing.aliyuncs.com/ee1f42d25d
20 张图彻底弄懂 HTTPS 的原理
前言 近年来各大公司对信息安全传输越来越重视,也逐步把网站升级到 HTTPS 了,那么大家知道 HTTPS 的原理是怎样的吗,到底是它是如何确保信息安全传输的?网上挺多介绍 HTTPS,但我发现总是或多或少有些点有些遗漏,没有讲全,今天试图由浅入深地把 HTTPS 讲明白,相信大家看完一定能掌握 HTTPS 的原理,本文大纲如下: HTTP 为什么不安全
手把手教你用用Python爬取上道网的赞助公司名称
一、前言 上道网是一个手游发行推荐与投融资交易平台。平台聚集手游CP、手游发行、手游渠道、手游外包,投资商以及IP授权商,IP合作、一站式服务。并为之提供合作交易机会。 今天教如何去爬取上道网的赞助公司名称,方便有关人士投资。 (https://imghelloworld.osscnbeijing.aliyuncs.com/dc08ff2
Android -- Fragment 基本用法、生命周期与细节注意
引言:这篇文章,大概分析下Fragment的生命周期、实际应用方法以及使用Fragment时需要注意的地方,算是Fragment的入门级文章,理解透Fragment生命周期和一些细节,就容易理解Fragment如何与外界通信等问题了。至于对其的源码分析等更加深入的内容,本文涉及不多。 Fragment的写法就不多说了,一般是继承Fragment,然后重
安卓内存优化
Android内存 1.Android内存分配与回收机制 从Application Framework、Dalvik/Art、Linux内核三个部分来讲解关于Androd内存相关的知识 (1)Application Framework (https://imghelloworld.osscnbeijing.a
天池比赛数据挖掘心电图数据分析
Task 2 数据分析 2.1 EDA 目标 EDA的价值主要在于熟悉数据集,了解数据集,对数据集进行验证来确定所获得数据集可以用于接下来的机器学习或者深度学习使用。 当了解了数据集之后我们下一步就是要去了解变量间的相互关系以及变量与预测值之间的存在关系。 引导数据科学从业者进行数据处理以及特征工程的步骤,使数据集的结构和特征集让接下来的预测问
Apache-Tomcate安装与环境配置
1.1    Tomcate 的下载与安装 在ApacheTomcate官网(https://tomcat.apache.org/download80.cgi)选择需要的系统版本型号.(我这次选择的是win系统下的免安装版,下载之后解压后就可以使用)     在解压后准备配置系统环境变量,个人建议可以将ApacheTomcate解压放在一个单独的文
介绍 | Vue3中文文档
已经了解 Vue 2,只想了解 Vue 3 的新功能可以参阅 Vue.js 是什么Vue (读音 /vjuː/,类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是,Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层,不仅易于上手,还便于与第三方库或既有项目整合。另一方面,当与以及各种 结合使用时
Android解析ActivityManagerService(一)AMS启动流程和AMS家族
Android框架层 Android系统服务 ActivityManagerService Android框架层本文首发于微信公众号「刘望舒」 前言此前在Android系统启动流程、应用进程以及深入四大组件这三个系列文章中,都提及到了AMS,但都没有系统的来讲解它,本文就以AMS为主来进行讲解,其中会有一些知识点与这些系列文章有所重合,这里会尽量做到详尽讲解
https://cloud.tencent.com/developer/article/write/1830331
一、目标今天的目标是这个sign和appcode 二、步骤 Jadx没法上了app加了某梆的企业版,Jadx表示无能为力了。 FRIDADEXDumpDexDump出来,木有找到有效的信息。 Wallbreaker葫芦娃的Wallbreaker可以做些带壳分析,不过这个样本,用Frida的Spawn模式可以载入,Attach模式会失败。而直接用Objecti
让人茅塞顿开!mysql教程视频百度云
2021全新Java核心知识 由于内容过多,本文篇幅有限,因此小编就不详细展示了,请各位老铁认真的看完本文内容,你一定会有所收获!Java篇目录内容(涵盖Java基础及核心技术、容器、并发、JVM技术)网络篇目录内容(涵盖计算机网络知识以及HTTPS中的TLS)操作系统Linux目录内容(初始初探操作系统Linux以及系统操作)数据结构与算法目录内容(详解布