【算法】冒泡排序算法

   冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。简单来说的话就是从第一个元素开始,然后和后面的一个进行比较,如果第一个元素比后面的一个元素大(或者小)的话,我们就交换特们的位置,然后用交换过后的元素来比较后面的元素,大于(小于)的话继续交换。一直持续到该次的尾部。然后重新从第一个元素开始继续比较和交换。直到比较完所有元素。

  步骤图示如下:

  

  代码实现如下:

 1 def Bubble_Sort(arry):
 2     if len(arry) < 2:       # 当数组中数据小于2个时,直接返回结果
 3         return arry
 4 
 5     for i in range(len(arry)):
 6         flag = False        # 当一次排序过程中,数组中的数据没有发生一次交换,则说明数组中数据都已经排序好了。直接结束
 7         for j in range(len(arry)-i-1):          # 
 8             if arry[j] < arry[j+1]:
 9                 arry[j], arry[j+1] = arry[j+1], arry[j]
10                 flag =True
11         if not flag:         # 未发生数据交换,直接返回。
12             return

 分析

   稳定性分析:在数据交换过程中,当遇到相等的数据时,不会发生交换,而是继续向后执行。则可以判断冒泡算法是稳定算法。

   时间复杂度和空间复杂度分析:冒泡排序在最好的情况下时间复杂度为O(n)(已经是有序的), 而最坏的情况下为O(n2)。 但是大部分情况下,都不会直接有序。而平均时间复杂度为O(n(n+1)/4)省去系数为O(n2)。空间复杂度为O(1)。

   原地排序:直接在数组上进行操作。

    

 有关时间复杂度分析这块之后补上详细分析。

原文地址:https://www.cnblogs.com/GoodRnne/p/10598697.html