写在前面&＃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;冒泡排序是稳定的排序算法。
京公网安备 11010802041100号