排序算法的稳定性
-
稳定的排序算法会让原本有相等键值的记录维持相对次序 -
不稳定的排序算法可能会改变相等键值的记录的相对次序
冒泡排序
冒泡排序的思想就是比较相邻之间的元素，如果 array[j] > array[j+1],则就会互换相邻之间的元素。这样每轮迭代完后，总有一个元素可以到达此元素应该到达的位置。
a、重复比较相邻的元素,如果前面的比后面的大,就交换它们两个位置
b、每次遍历整个数组,遍历完成后,下一次遍历的范围往左缩1位
c、重复前面步骤,直到排序完成
冒泡排序算法 时间复杂度是O(n^2)，空间复杂度是 O(1)，是稳定的排序算法
def bobbleSort(array):
print("原:",array)
n = len(array) # 得到数组的长度
for i in range(n-1):
for j in range(n-1-i):
if array[j] > array[j+1]:
tmp=array[j]
array[j]=array[j+1]
array[j+1]=tmp
#array[j], array[j+1] = array[j+1], array[j]
print(array)
print("-" * 21)
print(array)
bobbleSort([6, 4, 1, 3, 5, 2])
原: [6, 4, 1, 3, 5, 2]
[4, 1, 3, 5, 2, 6]
[1, 3, 4, 2, 5, 6]
[1, 3, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
---------------------
[1, 2, 3, 4, 5, 6]
当数组为test=[1,2,3,4,5,6,7]时，它原本就是有序的，不需要换位的，但此代码还会循环len-1次才输出结果，无意义
冒泡排序优化
代码中加入标志flag，flag=True说明本轮排序交换过位置，如果flag=False说明本轮排序没有交换位置，即数组是有序的了，跳出循环。
最好情况时间复杂度为O(1) 如：test=[1,2,3,4,5,6,7]
最差情况时间复杂度为O(n^2) 如：test=[6,7,1,2,3,4,5]
def bobbleSort(array):
print("原:",array)
n = len(array) # 得到数组的长度
for i in range(n-1):
flag=False
for j in range(n-1-i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
flag=True # 交换过
# 如果flag为True,说明本轮没有交换位置
if not flag:
break
print(array)
print("-" * 21)
print(array)
bobbleSort([6,7,1,2,3,4,5])
原: [6, 7, 1, 2, 3, 4, 5]
[6, 1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 6, 7]
---------------------
[1, 2, 3, 4, 5, 6, 7]
总结
冒泡排序是一种时间复杂度较高的排序算法，所以大部分时候都是在教科书中出现，在实际的项目或者使用过程中很少有它的身影。