python冒泡排序算法
-
冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,一层一层的将较大的元素往后移动,其现象和气泡在上升过程中慢慢变大类似,故成为冒泡排序。
def bubble_sort(arr): """冒泡排序""" # 第一层for表示循环的遍数,表示总得长度,代表每个元素遍历次数 for i in range(len(arr) - 1): # 第二层for表示具体比较哪两个元素,根据每个元素从第一到最后0-j 进行排序 for j in range(len(arr) - 1 - i): if arr[j] > arr[j + 1]: # 如果前面的大于后面的,则交换这两个元素的位置 arr[j], arr[j + 1] = arr[j + 1], arr[j] print(arr) return arr return arr if __name__ == '__main__': arr = [7,6,5,4,3,2,1] bubble_sort(arr)
冒泡排序是一种简单直接暴力的排序算法,为什么说它暴力?因为每一轮比较可能多个元素移动位置,而元素位置的互换是需要消耗资源的,所以这是一种偏慢的排序算法,仅适用于对于含有较少元素的数列进行排序。
- 稳定性:我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置,所以相同元素的相对顺序不可能改变,所以它是稳定排序
- 比较性:因为排序时元素之间需要比较,所以是比较排序
- 时间复杂度:因为它需要双层循环n*(n-1)),所以平均时间复杂度为O(n^2)
- 空间复杂度:只需要常数个辅助单元,所以空间复杂度为O(1),我们把空间复杂度为O(1)的排序成为原地排序(in-place)
- 记忆方法:想象成气泡,一层一层的往上变大