冒泡排序的時間複雜度是O(N^2)
冒泡排序的思想: 每次比較兩個相鄰的元素, 如果他們的順序錯誤就把他們交換位置
比如有五個數: 12, 35, 99, 18, 76, 從大到小排序, 對相鄰的兩位進行比較
- 第一趟:
- 第一次比較: 35, 12, 99, 18, 76
- 第二次比較: 35, 99, 12, 18, 76
- 第三次比較: 35, 99, 18, 12, 76
- 第四次比較: 35, 99, 18, 76, 12
經過第一趟比較後, 五個數中最小的數已經在最後面了, 接下來隻比較前四個數, 依次類推
-
第二趟
99, 35, 76, 18, 12
-
第三趟
99, 76, 35, 18, 12
-
第四趟
99, 76, 35, 18, 12
比較完成
冒泡排序原理: 每一趟隻能将一個數歸位, 如果有n個數進行排序,隻需将n-1個數歸位, 也就是說要進行n-1趟操作(已經歸位的數不用再比較)
#!/usr/bin/env python
# coding:utf-8
def bubbleSort(nums):
for i in range(len(nums)-1): # 這個循環負責設定冒泡排序進行的次數
for j in range(len(nums)-i-1): # j為清單下标
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
nums = [5,2,45,6,8,2,1]
print bubbleSort(nums)
缺點: 冒泡排序解決了桶排序浪費空間的問題, 但是冒泡排序的效率特别低