冒泡排序
冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序步骤
- 算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
# 冒泡排序
def bubble_sort(array):
'''
原始冒泡排序：从小到大
'''
compare_count = 0
for i in range(len(array) - 1): # n个数，只需要n-1次冒泡
for j in range(len(array) - i - 1):
compare_count += 1
if array[j] > array[j+1]:
array[j], array[j + 1] = array[j + 1], array[j]
print("bubble_sort circle num:", compare_count)
return array
- 冒泡排序
n个数，只需要n-1轮冒泡即可。 - 冒泡排序第
i轮冒泡完毕后，肯定会将索引为n-i-1的位置排序好，因此只需要循环到j= n-i-2即可 - 没有进行交换，说明数据已经有序
- 最后一个被交换的元素下标即为无序和有序的边界
冒泡排序优化
优化一：
冒泡排序优化：本次循环没有冒泡（交换），说明数据已经有序，可以直接退出
# -*- coding:utf-8 -*-
def bubble_sort2(array):
'''
冒泡排序优化：本次循环没有冒泡（交换），说明数据已经有序，可以直接退出
'''
compare_count = 0
for i in range(len(array) - 1):
swapped_flag = False
for j in range(len(array) - i - 1):
compare_count += 1
if array[j] > array[j+1]:
array[j], array[j+1] = array[j + 1], array[j]
swapped_flag = True
if not swapped_flag:
break
print('bubble_sort2 circle num:', compare_count)
return array
优化2
bubble_sort2的基础上再优化。
优化思路：在排序的过程中，数据可以从中间分为两段，一段是无序状态，另一段是有序状态。每一次循环的过程中，记录最后一个交换元素的索引，它便是有序和无序状态的边界下一次仅循环到边界即可，从而减少循环次数，达到优化。
# 冒泡排序优化：本次循环没有冒泡（交换），说明数据已经有序，可以直接退出
def bubble_sort3(array):
'''
bubble_sort2的基础上再优化。
优化思路：在排序的过程中，数据可以从中间分为两段，一段是无序状态，另一段是有序状态。
每一次循环的过程中，记录最后一个交换元素的索引，它便是有序和无序状态的边界
下一次仅循环到边界即可，从而减少循环次数，达到优化。
'''
compare_count = 0
last_swapped_index = 0
border = len(array) - 1 # 有序和无序的分界线
for i in range(len(array) - 1):
swapped_flag = False
for j in range(border):
compare_count += 1
if array[j] > array[j+1]:
array[j], array[j+1] = array[j + 1], array[j]
swapped_flag = True
last_swapped_index = j
if not swapped_flag:
break
border = last_swapped_index
print('bubble_sort3 circle num:', compare_count)
return array
3. 循环次数比较
if __name__ == '__main__':
array = [2, 4, 1, 3, 5, 8, 7, 8, 4, 9]
array2 = [] + array
array3 = [] + array
print('-'*20)
print bubble_sort(array)
print('-'*20)
print bubble_sort2(array2)
print('-'*20)
print bubble_sort3(array3)
输出：
--------------------
('bubble_sort circle num:', 45)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
--------------------
('bubble_sort2 circle num:', 35)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
--------------------
('bubble_sort3 circle num:', 31)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
冒泡排序复杂度
1.时间复杂度：
最小时间复杂度：最好的情况是数据一开始就是有序的，因此一次冒泡即可完成
最大时间复杂度：最坏的情况就是数据一开始就是倒序的，因此进行 n-1 次冒泡
- 平均时间复杂度：O(n^2)
- 最大时间复杂度：O(n^2)
- 最小时间复杂度：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
