Python之冒泡排序

- 日理万妓 2022-02-20 01:42 183阅读 0赞

**冒泡排序(Bubble Sort)：**  
是一种简单的、非常低效的排序算法。冒泡排序依次地走访要排序的数列，一次比较两个元素，如果他们的顺序错误（如从大到小、首字母从A到Z）就把他们交换位置，直到没有相邻元素需要交换，即该数列已经排序完成。这个算法名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

**短路冒泡排序：**  
在某次遍历过程中没有发生交换，说明整个排序已完成，无需继续遍历，遍历提前结束，这就是短路冒泡排序。

冒泡排序在平均和最坏情况下的时间复杂度都是 O(n²)，最好情况下都是 O(n)，空间复杂度是 O(1)。

**示例：**

# 普通冒泡排序
    def bubbleSort(alist):
    	n = len(alist) - 1 										#此处减1可减少下方遍历时重复计算
    	for passnum in range(n, 0, -1):							#共需遍历n次，因1个元素是不需要再遍历的
    		for i in range(passnum):							#1次循环遍历
    			if alist[i] > alist[i+1]:						#升序排列
    				alist[i], alist[i+1] = alist[i+1], alist[i]	#Python特有的交换方式
    
    # 短路冒泡排序
    def shortBubbleSort(alist):
    	n = len(alist) - 1 										
    	exchanges = False 										#初始化为未交换过
    	for passnum in range(n, 0, -1):					
    		for i in range(passnum):					
    			if alist[i] > alist[i+1]:				
    				alist[i], alist[i+1] = alist[i+1], alist[i]	
    				exchanges = True 							#有交换
    		if exchanges == False:								#若本次遍历无交换，则
    			break 											#说明已按升序排序，无需继续遍历，跳出
    
    alist = [53, 26, 93, 17, 77, 31, 44, 55, 20]
    bubbleSort(alist)
    print(alist)
    blist = [53, 26, 93, 17, 77, 31, 44, 55, 20]
    shortBubbleSort(blist)
    print(blist)

**结果：**

[17, 20, 26, 31, 44, 53, 55, 77, 93]
    [17, 20, 26, 31, 44, 53, 55, 77, 93]