专栏首页Python编程和深度学习经典排序算法和python详解(二):冒泡排序、双向冒泡排序、插入排序和希尔排序

经典排序算法和python详解(二):冒泡排序、双向冒泡排序、插入排序和希尔排序

经典排序算法和python详解(二):冒泡排序、双向冒泡排序、插入排序和希尔排序

内容目录

一、冒泡排序(Bubble Sort)二、冒泡排序法改进三、双向冒泡排序法四、插入排序五、希尔排序(插入排序改进)

一、冒泡排序(Bubble Sort)

冒泡排序是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。冒泡排序也是一个嵌套的循环,如果列表是已经排好序的,冒泡排序不会执行任何的交换,在最坏的情况下,为平方阶复杂度。

下面给两种python实现代码: 代码一

def BubbleSort(x):
   i = len(x) - 1
   while i > 0:
       j = 0
       while j < i:
           if x[j] > x[j + 1]:
               swap(x,j,j+1)
           j += 1
       i -= 1
   return x

代码二

def bubbleSort(list):
   for i in range(1, len(list)):
    for j in range(0, len(list)-i):
        if list [j] > list [j+1]:
            list [j], list [j + 1] = list [j + 1], list [j]
    return list

两种方法本质都是一样的,一种通过for循环遍历取值,一种通过while和+1遍历取值,最终都需要通过对比相邻数值的大小使得更大的值慢慢后移,达到排序的目的。

我们用[2,3,4,1,5]举例,

代码一中i 的取值范围为【4-3-2-1】,j的取值范围为【0-1-2-3】

当i= 4,j = 0,判断list [j = 0] = 2不大于list [j + 1 = 1] = 3,不用交换。 j = 1,判断list [j = 1] = 3不大于list [j + 1 = 2] = 4,不用交换。 j = 2,判断list [j = 2] = 4大于list [j + 1 = 3] = 1,交换后列表为[2,3,1,4,5]。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。 当i= 3,j = 0,判断list [j = 0] = 2不大于list [j + 1 = 1] = 3,不用交换。 j = 1,判断list [j = 1] = 3大于list [j + 1 = 2] = 1,交换后列表为[2,1,3,4,5]。 j = 2,判断list [j = 2] = 3不大于list [j + 1 = 3] = 4,不用交换。 当i= 2,j = 0,判断list [j = 0] = 2大于list [j + 1 = 1] = 1,交换后列表为[1,2,3,4,5]。 j = 1,判断list [j = 1] = 2不大于list [j + 1 = 2] = 3,不用交换。 最终的排序结果为[1,2,3,4,5]。

代码二中i的取值范围为【1-2-3-4】,j的取值范围为【0,1,2,3】

当i = 1,j = 0,判断list [j = 0] = 2不大于list [j + 1 = 1] = 3,不用交换。 j = 1,判断list [j = 1] = 3不大于list [j + 1 = 2] = 4,不用交换。 j = 2,判断list [j = 2] = 4大于list [j + 1 = 3] = 1,交换后列表为[2,3,1,4,5]。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。 当i = 2,j = 0,判断list [j = 0] = 2不大于list [j + 1 = 1] = 3,不用交换。 j = 1,判断list [j = 1] = 3大于list [j + 1 = 2] = 1,交换后列表为[2,1,3,4,5]。 j = 2,判断list [j = 2] = 3不大于list [j + 1 = 3] = 4,不用交换。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。 当i = 3,j = 0,判断list [j = 0] = 2大于list [j + 1 = 1] = 1,交换后列表为[1,2,3,4,5]。 j = 1,判断list [j = 1] = 2不大于list [j + 1 = 2] = 3,不用交换。 j = 2,判断list [j = 2] = 3不大于list [j + 1 = 3] = 4,不用交换。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。

当i = 4,j = 0,判断list [j = 0] = 1不大于list [j + 1 = 1] = 2,不用交换。 j = 1,判断list [j = 1] = 2不大于list [j + 1 = 2] = 3,不用交换。 j = 2,判断list [j = 2] = 3不大于list [j + 1 = 3] = 4,不用交换。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。 最终的排序结果为[1,2,3,4,5]。

二、冒泡排序法改进

在最好的情况下,冒泡排序法依然会执行每个循环但不进行任何交换操作,可以设定一个标记判断冒泡排序法在一次内层循环中是否进行了交换,如果没有,说明算法已经使排好序的,就可以直接返回,不过这种方法只是对最好的情况进行了改进。 Python代码:

def BubbleSort_1(x):
   i = len(x) - 1
   while i > 0 :
       flag = False
       j = 0
       while j < i:
           if x[j] > x[j + 1]:
               swap(x,j,j+1)
               flag = True
           j += 1
       if not flag:
           return x
       i -= 1
   return x

该代码就是设定一个标记flag,判断在一次内层循环中是否进行了交换,如果没有交换,说明算法已经使排好序的,就可以直接返回作为最终输出。

三、双向冒泡排序法

之前我们在选择排序中引入了双向选择排序来改进方法,冒泡排序法也可以采用双向冒泡,比如在升序排序中,序列中较小的数字又大量存在于序列的尾部,这样每次移动大数字到末尾,会让小数字在向前移动得很缓慢,针对这一问题,可以采用双向冒泡排序法,也称鸡尾酒排序法对传统的冒泡排序法进行改进。

双向冒泡排序法由两个方向同时进行冒泡,首先由左向右为大元素移动方向,从右向左为小元素移动方向,然后每个元素都依次执行。在第i次移动后,前i个和后i个元素都放到了正确的位置。

Python代码:

def BidirectionalBubbleSort(x):
   i = 0
   while i<= len(x)//2:###两侧一起向中心移动,因此为一半
       flag = False
       for j in range(i ,len(x) - i - 1):
           if x[j]>x[j+1]:
               swap(x, j, j+1)
               flag=True
       for j in range(len(x)- 1 - i,i,-1):
           if x[j]<x[j-1]:
               swap(x, j, j-1)
               flag=True
       if not flag:
           return x
       i += 1
   return x

我们用[2,3,4,1,5,6]举例, 代码中i 的取值范围为【0-1-2-3】,两个循环中j的取值范围为【0-1-2-3-4】和【5-4-3-2-1】 当i= 0 对于较大值: j = 0,判断list [j = 0] = 2不大于list [j + 1 = 1] = 3,不用交换。 j = 1,判断list [j = 1] = 3不大于list [j + 1 = 2] = 4,不用交换。 j = 2,判断list [j = 2] = 4大于list [j + 1 = 3] = 1,交换后列表为[2,3,1,4,5,6]。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。 j = 4,判断list [j = 4] = 5不大于list [j + 1 = 5] = 6,不用交换。 对于较小值: j = 5,判断list [j = 5] = 6不小于list [j - 1 = 4] = 5,不用交换。 j = 4,判断list [j = 4] = 5不小于list [j - 1 = 3] = 4,不用交换。 j = 3,判断list [j = 3] = 4不小于于list [j - 1 = 2] = 1,不用交换。 j = 2,判断list [j = 2] = 1小于list [j - 1 = 1] = 3,交换后列表为[2,1,3,4,5,6]。 j = 1,判断list [j = 1] = 1小于list [j - 1 = 0] = 2,交换后列表为[1,2,3,4,5,6]。 当i= 1 对于较大值: j = 0,判断list [j = 0] = 1不大于list [j + 1 = 1] = 2,不用交换。 j = 1,判断list [j = 1] = 2不大于list [j + 1 = 2] = 3,不用交换。 j = 2,判断list [j = 2] = 3不大于list [j + 1 = 3] = 4,不用交换。 j = 3,判断list [j = 3] = 4不大于list [j + 1 = 4] = 5,不用交换。 j = 4,判断list [j = 4] = 5不大于list [j + 1 = 5] = 6,不用交换。 对于较小值: j = 5,判断list [j = 5] = 6不小于list [j - 1 = 4] = 5,不用交换。 j = 4,判断list [j = 4] = 5不小于list [j - 1 = 3] = 4,不用交换。 j = 3,判断list [j = 3] = 4不小于list [j - 1 = 2] = 3,不用交换。 j = 2,判断list [j = 2] = 3不小于list [j - 1 = 1] = 2,不用交换。 j = 1,判断list [j = 1] = 2不小于list [j - 1 = 0] = 1,不用交换。 此时flag = False,在这一轮中没有任何交换,可以直接退出程序,返回最终的排序结果为[1,2,3,4,5]。

四、插入排序

插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。

插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

Python代码:

def InsertionSort(x):
   i = 1
   while i < len(x):
       j = i - 1
       item = x[i]
       while j >= 0 and item < x[j]:
           x[j + 1] = x[j]
           j -= 1
       x[j + 1] = item
       i += 1   
   return x

插入排序是每次选择并取出其中一个数值,对剩余列表寻找合适的位置进行插入。 我们用[2,3,4,1,5]举例, 代码中i 的取值范围为【1-2-3-4】, j的取值范围为【0-1-2-3】。 当i= 1 j = 0,item = list[i = 1] = 3, 判断item=3不小于list [j = 0] = 2,不用交换,item= 3赋值给list[j+1=1],列表不变。 当i= 2 j = 1,item = list[i = 2] = 4, 判断item=4不小于list [j = 1] = 3,不用交换,item= 4赋值给list[j+1=2],列表不变。 当i= 3 j = 2,item = list[i = 3] = 1, 判断item=1小于list [j = 2] = 4,list[j = 2] = 4赋值给list[j + 1 = 3],j = j – 1 = 1, item= 1赋值给list[j+1=2],列表变为[2,3,1,4,5]。 j = 1,item = list[i = 3] = 1, 判断item=1小于list [j = 1] = 3,list[j = 1] = 3赋值给list[j + 1 = 2],j = j – 1 = 0, item= 1赋值给list[j+1=1],列表变为[2,1,3,4,5]。 j = 0,item = list[i = 3] = 1, 判断item=1小于list [j = 0] = 2,list[j = 0] = 2赋值给list[j + 1 = 1],j = j – 1 = -1, item= 1赋值给list[j+1=0],列表变为[1,2,3,4,5]。 当i= 4 j = 3,item = list[i = 4] = 5, 判断item=5不小于list [j = 3] = 4,不用交换,item= 5赋值给list[j+1=4],列表不变。 最终排序结果就是[1,2,3,4,5]。

五、希尔排序(插入排序改进)

插入排序在顺序以及比较好的情况下效率高,但其大部分情况是低效率的,因为每次智能移动一位数字,希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔算法的逻辑是,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序,具体步骤如下: 1.设定一个较大间隔gap,对所有间隔为gap的数据通过插入排序法进行排序; 2.执行完之后根据某种逻辑缩小gap(代码中采用除以3取整的办法),重复上述过程,直到gap = 0。 通过以上步骤,最终得到的列表是排好序的,并且可以证明,这种方法的平均的复杂度是O(nlogn)。

Python代码:

def HashSort(x):
   gap = round(len(x)*2/3)
   while gap > 0 :    
       print('gap =  ',gap )
       i = gap
       while i < len(x):
           j = i - gap
           item = x[i]
           while j >= 0 and item < x[j]:
               x[j + gap] = x[j]
               j -= gap
           x[j + gap] = item
           i += 1
       gap = round(gap/3)
   return x

我们用[2,3,4,1,5,6]举例, 代码中初始gap = round(len(list) *2 / 3)=4。 当gap = 4, i = gap = 4, j = i – gap =4-4= 0, item = list[i = 4] = 5, 判断 j >=0且 item = 5 不小于 list[j= 0] = 2, item 赋值给list[ j + gap=4], 列表不变, i = i + 1 = 5, j = i – gap = 5-4=1, item = list[i = 5] = 6, 判断 j >=0且 item = 6 不小于 list[j= 1] = 3, item 赋值给list[ j + gap=5], 列表不变, 当gap = round(gap/3)) = 1, i = gap = 1, j = i – gap = 0, item = list[i = 1] = 3, 判断 j >=0且 item = 3 不小于 list[j= 0] = 2, item 赋值给list[ j + gap=1],列表不变, i = i + 1 = 2, j = i – gap = 2-1=1, item = list[i = 2] = 4, 判断 j >=0且 item = 4 不小于 list[j= 1] = 3, item 赋值给list[ j + gap=2], 列表不变, i = i + 1 = 3, j = i – gap = 3-1=2, item = list[i = 3] = 1, 判断 j >=0且 item = 1 小于 list[j= 2] = 4, list[j = 2] = 4赋值给list[j+gap=2+1=3],列表变为:[2,3,4,4,5,6], j = j – gap = 2 -1=1, item = list[i = 3] = 1,判断 j >=0且item = 1小于list[j = 1] = 3, list[j = 1] = 3赋值给list[j+gap=1+1=2], 列表变为:[2,3,3,4,5,6], j = j – gap = 1 -1=0, item = list[i = 3] = 1,判断 j >=0且item = 1小于list[j = 0] = 2, list[j = 0] = 2赋值给list[j+gap=0+1=1], 列表变为:[2,2,3,4,5,6], j = j – gap = 0 -1=-1,判断j 不大于0,则item = 1赋值给list[j+gap=-1+1=0],列表变为:[1,2,3,4,5,6]。 i = i + 1 = 4, j = i – gap = 4-1=3, item = list[i = 4] = 5, 判断 j >=0且 item = 5 不小于 list[j= 3] = 4, item=5 赋值给list[ j + gap=4], 列表不变, i = i + 1 = 5, j = i – gap = 5-1=4, item = list[i = 5] = 6, 判断 j >=0且 item = 6 不小于 list[j= 4] = 5, item=6 赋值给list[ j + gap=5], 列表不变。 最终排序后列表为[1,2,3,4,5,6]。

本文分享自微信公众号 - Python编程和深度学习(Python_Deeplearning),作者:Python编程和深度学习

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

原始发表时间:2020-03-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 经典排序算法和Python详解之(一)选择排序和二元选择排序

    稳定排序和不稳定排序内部排序和外部排序时间复杂度和空间复杂度算法一:选择排序算法二:二元选择排序法(选择排序改进)

    Minerva
  • 写在前面。

    Python是一门极其简单优雅的编程语言。2011 年 1 月,它被 TIOBE 编程语言排行榜评为 2010 年度语言,2017 年 7 月的 TIOBE 排...

    Minerva
  • 数字图像处理之图像分割算法

    图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。现有的图像分割方法主要分以下几类:基于阈值的分割方法、基于区域的分割方法、基...

    Minerva
  • python将字符串类型list转换成list

    python读取了一个list是字符串形式的'[11.23,23.34]',想转换成list类型:

    机器学习和大数据挖掘
  • python 列表学习

    你可以对列表的数据项进行修改或者是更新,你也可以使用append()方法来添加列表项

    Mirror王宇阳
  • Python中赋值、浅拷贝与深拷贝

       python中关于对象复制有三种类型的使用方式,赋值、浅拷贝与深拷贝。他们既有区别又有联系,刚好最近碰到这一类的问题,研究下。 一、赋值         ...

    用户1214487
  • Python list(列表)

    Python一共有6种序列的内置类型,list和tuple是其中最常见的。6种序列的都可以进行的操作包括索引、切片,加(实际上是连接),乘(实际上是复制)...

    Steve Wang
  • R语言数据清洗实战——高效list解析方案

    list是R语言中包容性最强的数据对象,几乎可以容乃所有的其他数据类型。 但是包容性最强也也意味着他对于内部子对象的类型限制最少,甚至内部可以存在递归结构,这样...

    数据小磨坊
  • <算法入门>快速理解7种排序算法 | python3实现(附源码)学习难度:桶排序(简化版)冒泡排序选择排序插入排序快速排序(面试常用算法)归并排序(先分后和, 分而治之)希尔排序

    算法是程序的灵魂,而排序算法 是算法的入门经典,作者在此用python亲自实现了7种主流的排序算法,并做简短的说明. ? 排序算法 学习难度: 桶排序 < 冒泡...

    zhaoolee
  • Python数据分析之锁具装箱问题问题重述问题分析建模与求解

    罗罗攀

扫码关注云+社区

领取腾讯云代金券