算法理解之排序-冒泡排序
冒泡排序是一种简单的排序算法, 算法依次走访未排序的元素, 然后将相邻元素依次两两比较, 将最大的元素不断移动至最后, 直到所有元素均被排序过为止. 因为最大元素是从某个位置不断"浮"上去的, 所以称为冒泡排序
算法分析
- 取得相邻的两个元素, 比较两个元素大小, 若第一个元素大于第二个元素, 则交换位置(上浮).
- 将相邻元素位置后移一位, 再次按
步骤1比较, 直至该元素比对到已排序过位置或最后位置. - 重复
步骤1与步骤2直到完成排序.
动图效果
冒泡排序.gif
时间复杂度与空间复杂度与稳定性
稳定性: 稳定
时间复杂度: O(N^2)
空间复杂度: O(1)
稳定性分析: 两外相邻的元素比较, 只要在前者大于后者于才变更位置, 其他情况下不变.
时间复杂度解析: 冒泡排序需要完成两层迭代过程, 第一层确保每个元素都进行排序.第二层来比较并排序元素.所以时间复杂度为O(N^2).
空间复杂度解析: 所有排序均在当前列表中完成, 不存在额外使用内存情况. 所以空间复杂度为O(1).
代码示例:
Python
def bubble_sort(li):
# 获取列表总长度.
li_len = len(li)
# 第一层循环, 确保所有元素被遍历
for i in range(li_len - 1):
# 第二层循环, 比较并排序元素
for j in range(li_len - i - 1):
# 比较当前元素与相邻的下个元素
if li[j] > li[j + 1]:
# 交换相邻元素
li[j], li[j + 1] = li[j + 1], li[j]
return li
- 图版本来源于: https://www.cnblogs.com/onepixel/p/7674659.html 若有不当请联系作者删除.
