冒泡排序

冒泡排序(Bubble Sort)

  1.     冒泡排序是一种简单的排序算法。它重复地遍历容器中所有要排序的元素，一次比较两个元素，如果它们的顺序错误就交换它们的位置。遍历元素的工作是重复地进行直到没有再需要交换为止，也就是说该容器中的元素已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法思路

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动画演示

9.7 冒泡排序 - 图1

代码实现

  1. def BS(nums):
  2.     n = len(nums)
  3.     for i in range(n-1):
  4.         for j in range(n-1-i):
  5.             if nums[j] > nums[j+1]:     # 如果当前元素大于下一个元素就交换他们的位置
  6.                 nums[j], nums[j+1] = nums[j+1], nums[j]
  7.         # print(nums)   # 查看排序过程
  8.     return nums
  10. print(BS(nums=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
  1.     运行结果：
  1. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    排序过程：

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  1. [3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50]
  2. [3, 5, 38, 15, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50]
  3. [3, 5, 15, 36, 26, 27, 2, 38, 4, 19, 44, 46, 47, 48, 50]
  4. [3, 5, 15, 26, 27, 2, 36, 4, 19, 38, 44, 46, 47, 48, 50]
  5. [3, 5, 15, 26, 2, 27, 4, 19, 36, 38, 44, 46, 47, 48, 50]
  6. [3, 5, 15, 2, 26, 4, 19, 27, 36, 38, 44, 46, 47, 48, 50]
  7. [3, 5, 2, 15, 4, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  8. [3, 2, 5, 4, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  9. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  10. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  11. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  12. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  13. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  14. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  15. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

复杂度分析

    时间复杂度分析：当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，那么可以判断出就是n-1次的比较，没有数据交换，此时时间复杂度为O(n)。当最坏的情况，即待排序是逆序的情况，此时需要比较

9.7 冒泡排序 - 图2%3D%5Cfrac%7Bn(n-1)%7D%7B2%7D%0A#card=math&code=%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D%7Bi%7D%3D1%2B2%2B%7B%5Ccdots%7D%2B%28n-1%29%3D%5Cfrac%7Bn%28n-1%29%7D%7B2%7D%0A)

次，此时的时间复杂度为O(n^2)。

    空间复杂度：每次比较的结果直接存储到原列表中，不再需要别的空间存储，所以空间复杂度为O(1)。

优缺点

        优点：不需要额外的存储空间开销。

        缺点：冒泡排序的效率主要差在每个数据项在找到最终位置之前，必须要经过多次比对和交换，其中大部分操作是无效的。

        在平时，我们经常将冒泡排序作为时间效率较差的排序算法，来作为其他算法的对比基准。

性能改进

        根据冒泡排序的缺点，我们可以通过检测每趟比对是否发生过交换来提前确定排序是否完成。这也是其他排序算法无法做到的。