python冒泡排序理解_八大排序python实现精讲（一）冒泡排序

写在前面&＃xff0c;排序算法属于面试中绝对不会错过的一道题&＃xff0c;不管是原理&＃xff0c;手撕&＃xff0c;变形&＃xff0c;优化&＃xff0c;全都是考点。

接下来更的几篇文章争取全面考虑&＃xff0c;从面试官的角度解析排序算法以及对应回答~如果喜欢的话可以点赞收藏关注&＃xff01;及时收获知识~

总结

先来总结一下即将展开的八大排序算法。

排序算法可以依据以下几个标准划分成不同的类别&＃xff08;来自维基百科排序算法&＃xff09;&＃xff1a;计算的时间复杂度&＃xff08;最差、平均、和最好性能&＃xff09;

空间复杂度&＃xff08;所需额外辅助存储空间&＃xff09;

稳定性&＃xff1a;稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的&＃xff0c;当有两个相等键值的纪录R和S&＃xff0c;且在原本的列表中R出现在S之前&＃xff0c;在排序过的列表中R也将会是在S之前

依据排序的方法&＃xff1a;插入、交换、选择、合并等等。

一图概览排序算法

冒泡排序(Bubble Sort)

从最简单的开始讲起。冒泡排序属于非常好理解的排序算法了。这是我上学的时候接触的第一个排序算法&＃xff0c;记忆犹新~

算法思想

思想很简单&＃xff0c;从左到右&＃xff0c;比较两个相邻的元素。如果这两个数字顺序不是升序&＃xff0c;就交换这两个数字&＃xff0c;小的在前大的在后。直到最后没有数字需要交换。

由于数字越大&＃xff0c;越往下沉&＃xff0c;沉到数组的最后位置。数字越小&＃xff0c;越上浮&＃xff0c;浮到数组最前位置&＃xff0c;所以叫做冒泡排序~

动图非常直观~ &＃xff08;图片来自网络&＃xff09;冒泡排序属于交换类

算法步骤

从左到右:比较两个相邻元素&＃xff0c;看是否为升序&＃xff0c;即第一个元素小于第二个元素。如果不是升序&＃xff0c;交换这两个元素在数组中的位置。

每一对相邻元素&＃xff0c;都要做一次这样的比较。假设数组长度为n&＃xff0c;需要比较n-1次。这样比较一轮&＃xff0c;最大的数字会沉到数组最右侧。下一次则不需要比较最后的数字。

重复&＃xff0c;没有元素需要交换为止。

代码实现

import random

def gen_random_data(start, end, number):

# 用于生成数据的方法&＃xff0c;数字大小在start到end之间&＃xff0c;共number个数字

res &＃61; []

for i in range(number):

res.append(random.randint(start,end))

return res

def Bubble_Sort(array):

for i in range(1, len(array)):

for j in range(len(array) - i):

if array[j] > array[j &＃43; 1] :

tmp &＃61; array[j]

array[j] &＃61; array[j &＃43; 1]

array[j&＃43;1] &＃61; tmp

真的太困了。。改进思路与总结明天写~如果对这个系列内容感兴趣&＃xff0c;可以收藏关注点赞~明天继续更&＃xff01;真的不鸽了&＃xff01;困到恍惚

-----------------20200513更新-----------------

改进思路

假设有数组[2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;7&＃xff0c;6]&＃xff0c;冒泡排序&＃xff0c;需要进行5趟排序。但是第一趟排序进行后&＃xff0c;数组变为[2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7]&＃xff0c;已经有序&＃xff0c;不需要再进行排序了。但是按照上面的经典排序&＃xff0c;仍然需要进行4趟排序。

改进方法可以考虑设置一个标志位&＃xff0c;当某趟排序没有产生数据交换&＃xff0c;就代表数组已经有序&＃xff0c;这样就可以结束排序。

def Bubble_Sort_Opt(array):

flag &＃61; True

for i in range(1, len(array)):

if flag:

flag &＃61; False

for j in range(len(array) - i):

if array[j] > array[j &＃43; 1] :

tmp &＃61; array[j]

array[j] &＃61; array[j &＃43; 1]

array[j&＃43;1] &＃61; tmp

# print(array)

flag &＃61; True

总结

冒泡排序属于最经典的排序算法&＃xff0c;由于其直观性&＃xff0c;很容易被应试者作为第一个解决办法想到。

由于每次交换&＃xff0c;只需要临时存储一个数字&＃xff0c;所以空间复杂度为O(1)。

最好情况是数据是已经有序的&＃xff0c;这样遍历一次就可以结束&＃xff0c;最好时间复杂度为O(n)。

最坏情况是数据是逆序&＃xff0c;这样每次遍历都需要交换一次&＃xff0c;最坏时间复杂度为

。

由于出现两个相同数字不会导致交换&＃xff0c;所以相同数字相对位置不变&＃xff0c;冒泡排序是稳定的排序算法。