专栏首页飞总聊IT【漫画】七种最常见的排序算法(动图版)

【漫画】七种最常见的排序算法(动图版)

本文由河北小博投稿发布

https://blog.csdn.net/qq_32799165/article/details/87878876

一、冒泡排序

  • 冒泡排序是排序算法中较为简单的一种,英文称为 Bubble Sort。它遍历所有的数据,每次对相邻元素进行两两比较,如果顺序和预先规定的顺序不一致,则进行位置交换;这样一次遍历会将最大或最小的数据上浮到顶端,之后再重复同样的操作,直到所有的数据有序。
  • 如果有n个数据,那么需要的比较次数,所以当数据量很大时,冒泡算法的效率并不高。
  • 当输入的数据是反序时,花的时间最长,当输入的数据是正序时,时间最短。

步骤

  • 从前往后依次比较相邻的元素。如果前一个元素比后一个二元素大,交换二者位置。(数列遍历一遍后,最大数被移动到末尾)。
  • 重复步骤1(已确定位置的数据不需要再参与排序)。
  • 完成排序。

动画演示

python代码实现如下:

优化:某一趟遍历如果没有数据交换,则说明已经排好序了,因此不用再进行迭代了。用一个标记记录这个状态即可。设置标志位flag,如果发生了交换flag设置为true;如果没有交换就设置为false。这样当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去,排序结束。

二、选择排序

  • 选择排序简单直观,英文称为 Selection Sort,先在数据中找出最大或最小的元素,放到序列的起始;然后再从余下的数据中继续寻找最大或最小的元素,依次放到排序序列中,直到所有数据样本排序完成。很显然,选择排序也是一个费时的排序算法,无论什么数据,都需要 O(n²) 的时间复杂度,不适宜大量数据的排序。
  • 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

步骤

  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置 。
  2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复步骤2,直到所有元素均排序完毕。

动画演示

python代码实现如下:

三、插入排序

  • 插入排序英文称为Insertion Sort,它通过构建有序序列,对于未排序的数据序列,在已排序序列中从后向前扫描,找到相应的位置并插入,类似打扑克牌时的码牌。插入排序有一种优化的算法,可以进行拆半插入。
  • 基本思路是先将待排序序列的第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列;然后从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置,直到所有数据都完成排序;如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。

步骤

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)。

动画演示

python代码实现如下:

四、快速排序

  • 快速排序,英文称为Quicksort,又称划分交换排序partition-exchange sort简称快排。
  • 快速排序使用分治策略来把一个序列分为两个子序列。首先从数列中挑出一个元素,并将这个元素称为「基准」pivot。重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面,相同的数可以到任何一边。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区partition操作。之后,在子序列中继续重复这个方法,直到最后整个数据序列排序完成。
  • 快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)。事实上,快速排序通常明显比其他算法更快,因为它的内部循环可以在大部分的架构上很有效率地达成。

步骤

  1. 从数列中挑出一个元素,称为"基准"(pivot)。
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

动画演示

python代码实现如下:

五、希尔排序

  • 希尔排序也称递减增量排序,是插入排序的一种改进版本,英文称为Shell Sort,效率虽高,但它是一种不稳定的排序算法。
  • 插入排序在对几乎已经排好序的数据操作时,效果是非常好的;但是插入排序每次只能移动一位数据,因此插入排序效率比较低。
  • 希尔排序在插入排序的基础上进行了改进,它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对全部数据进行依次直接插入排序。

步骤

  1. 将元素分为n列,并对每列进行插入排序。
  2. 将n列元素按行进行合并。
  3. 重复步骤1-2,其中元素的列数为上次的一半。

动画演示

python代码实现如下:

六、归并排序

  • 归并排序英文称为 Merge Sort,它是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。
  • 将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
  • 归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法。

步骤

  1. 递归分解,将数组分解成left和right。如果这两个数组内部数据是有序的(转向步骤2-4);如果无序,则对数组进行二分,直至分解出的小组只有一个元素,此时认为该小组内部有序。
  2. 合并两个有序数组,比较两个数组的最前面的数,谁小就先取谁,该数组的指针往后移一位。
  3. 重复步骤2,直至一个数组为空。
  4. 最后把另一个数组的剩余部分复制过来即可。

动画演示

python代码实现如下:

七、堆排序

  • 堆排序,英文称 Heapsort,是指利用堆这种数据结构所设计的一种排序算法。堆排序在 top K问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的,虽然实质上还是一维数组。二叉堆是一个近似完全二叉树。
  • 二叉堆具有以下性质:
  1. 父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
  2. 每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆)。

步骤

  1. 根据初始数组取构建一个完全二叉树,保证所有的父节点比子节点的数值大。
  2. 每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为最大堆。

动画演示

python代码实现如下:

七种常见排序算法效率比较

本文分享自微信公众号 - 飞总聊IT(feiitworld)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:如何找到两个数组的中位数?

    上图这两个给定数组A和B,一个长度是6,一个长度是5,归并之后的大数组仍然要保持升序,结果如下:

    用户1564362
  • 宋仲基宋慧乔没能找到对的人,算法能帮我们找到么?

    场景描述:寻找能够相伴一生的灵魂伴侣是很多人的美好愿望,但现实往往残酷。为此,基于大数据,机器学习,AI 算法的婚恋网站和应用纷纷出招,它们能够帮助广大单身男女...

    用户1564362
  • CPU阿甘

    我是CPU, 他们都叫我阿甘, 因为我和《阿甘正传》里的阿甘一样, 有点傻里傻气的。

    用户1564362
  • 数据结构常见的八大排序算法

    前言 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下: 他们的性能...

    小莹莹
  • 【Udacity并行计算课程笔记】- Lesson 4 Fundamental GPU Algorithms (Applications of Sort and Scan)

    在介绍这节之前,首先给定一个情景方便理解,就是因为某种原因我们需要从扑克牌中选出方块的牌。

    marsggbo
  • 桶排序

    桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归...

    苦咖啡
  • 八大排序算法稳定性分析,原来稳定性是这个意思...

    2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

    谭庆波
  • 八大排序算法总结与java实现

    概述 因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法: ? 请点...

    企鹅号小编
  • 基础算法| 常用排序算法小结

    日常吹水 说到这个算法, 可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。 那么,正走在算法之路上的你, 是否还在苦苦寻求修仙之路? 是否被各种排序...

    用户1621951
  • 恕我直言你可能真的不会java第11篇-Stream API终端操作

    在本号之前写过的文章中,曾经给大家介绍过 Java Stream管道流是用于简化集合类元素处理的java API。在使用的过程中分为三个阶段。在开始本文之前,我...

    字母哥博客

扫码关注云+社区

领取腾讯云代金券