冒泡排序
基本思想
冒泡法也称沉底法,没相邻两个记录关键字比较大小,大的记录往下沉(也可以小的网上浮).每一遍把最后一个下沉的位置记下,下一遍只需检查比较到此位置;到所有记录都不发生变化时,整个过程结束(每交换一次,记录减少一个反序数).
举例
有一组数据( 83, 16, 9, 96, 27, 75, 42, 69,34 ),在开始时 83 与 16 互相比较,因为 83>16,所以两个元素互换,然后比较 83>9,83 与 9 互换,接着比较 83<96,所以不变,然后互换的元素有(96,27),(96,75),(96,69)(96,34),所以在第一趟排序结束时找到最大的值 96,把它放在最下面的位置.
重复每一趟排序都会将最大的一个元素放在工作区域的最低位置,且每趟排序的工作区域都比前一趟排序少一个元素,如此重复直到没有互换产生才停止.
python 代码
效率分析
## 冒泡排序
def bubble_sort(SList):
L = len(SList)
while L > 0:
for i in range(L - 1):
if SList[i] > SList[i+1]:
SList[i],SList[i+1] = SList[i+1],SList[i] # 交换它们的值
L -= 1
print(SList)
if __name__ == '__main__':
SList = [ 83, 16, 9, 96, 27, 75, 42, 69, 34]
bubble_sort(SList)
空间效率:O(1)
时间效率:总共要进行 n-1 趟冒泡,对 i 个记录的表进行一趟冒泡需要 i-1 次关键字的比较.
总比较次数 = 1/2*n*(n-1)
移动次数 = 3/2*n*(n-1)
时间复杂度为 O(n2)
冒泡排序是一种稳定排序.
来源: http://www.bubuko.com/infodetail-2461676.html