经典排序算法和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]。