文章目录

一、排序算法的稳定性二、排序算法--冒泡排序1、定义2、python实现1）无优化时间复杂度 2）优化版时间复杂度

一、排序算法的稳定性

稳定性：如果一个排序算法是稳定的，当有两个相等键值的记录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前

比如： 假设以下的数对将要以他们的第一个数字来排序 (4,1) (3,1) (3,7) (5,6) 在这个状况下，有可能产生两种不同的结果，一个是让相等键值的记录维持相对的次序，另一个则没有 维持次序：（3，1）（3，7）（4，1）（5，6） 次序被改变：（3，7）（3，1）（4，1）（5，6） 即，(3,1) 原来就在(3,7)之前，排序后(3，1)始终都在(3,7)之前为稳定的排序算法 我们比较的是3，无关于后面的7和1，如果排序后(3,1)和(3,7)顺序改变，则为不稳定算法

二、排序算法–冒泡排序

1、定义

是一种简单的排序算法 冒泡排序算法的步骤：

比较相邻的元素。先比较第一个和第二个，如果第一个比第二个大，就交换这两个元素的顺序，接下来比较第二个和第三个元素……对每一对相邻的元素作同样的工作，从队列的开始到结尾。这步做完后，最后的元素会是最大的数针对所有的元素重复以上的步骤，除了最后一个(通过一个个比较得出的最大的值)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

交换过程图示(第一次)：

那么我们需要进行n-1次冒泡过程，直到所有的元素都轮一次

2、python实现

1）无优化

两次遍历中： 第一次为判断每个值与其他值的大小的循环； 第二次为当前值与其他值的比较的循环。 第二次在第一次的基础下，第一次循环到哪个数时，第二次的次数就是这个数之前的个数-1

def bubble_sort(alist): n=len(alist) # 共要排列多少次 for i in range(n-1): # 班长从投走到尾，一次排列的循环 for j in range(n-1-i): if alist[j]>alist[j+1]: alist[j],alist[j+1]=alist[j+1],alist[j] if __name__ == '__main__': list=[44,54,73,23,1,2,53,67,88,32,21] print(list) bubble_sort(list) print(list)

结果：

[44, 54, 73, 23, 1, 2, 53, 67, 88, 32, 21] [1, 2, 21, 23, 32, 44, 53, 54, 67, 73, 88]

时间复杂度

最优时间复杂度：O(n)（表示遍历一次发现没有任何可以交换的元素，排序结束）最坏时间复杂度：O(n²)稳定性：稳定

2）优化版

import time def bubble_sort(alist): n=len(alist) # 共要排列多少次 for i in range(n-1): # 班长从投走到尾，一次排列的循环 count=0 for j in range(n-1-i): if alist[j]>alist[j+1]: alist[j],alist[j+1]=alist[j+1],alist[j] count += 1 if 0 == count: # 添加一个count，需要交换时，也就是两个数的顺序不满足条件时，+1 # 当count为0时表示前面的元素都是满足顺序的，没有经过交换 # 因此在后续的循环中不再需要作比较 return if __name__ == '__main__': list=[44,54,73,23,1,2,53,67,88,32,21] print(list) bubble_sort(list) print(list)

结果：

[44, 54, 73, 23, 1, 2, 53, 67, 88, 32, 21] [1, 2, 21, 23, 32, 44, 53, 54, 67, 73, 88]

时间复杂度

此时，如果出现最优复杂度的序列时，就不会再按照代码每个元素都遍历