冒泡排序
冒泡排序（Bubble Sort）是一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序步驟
- 算法步驟
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
# 冒泡排序
def bubble_sort(array):
'''
原始冒泡排序：從小到大
'''
compare_count = 0
for i in range(len(array) - 1): # n個(gè)數(shù)，只需要n-1次冒泡
for j in range(len(array) - i - 1):
compare_count += 1
if array[j] > array[j+1]:
array[j], array[j + 1] = array[j + 1], array[j]
print("bubble_sort circle num:", compare_count)
return array
- 冒泡排序
n個(gè)數(shù)，只需要n-1輪冒泡即可。 - 冒泡排序第
i輪冒泡完畢后，肯定會(huì)將索引為n-i-1的位置排序好，因此只需要循環(huán)到j= n-i-2即可 - 沒有進(jìn)行交換，說明數(shù)據(jù)已經(jīng)有序
- 最后一個(gè)被交換的元素下標(biāo)即為無序和有序的邊界
冒泡排序優(yōu)化
優(yōu)化一：
冒泡排序優(yōu)化：本次循環(huán)沒有冒泡（交換），說明數(shù)據(jù)已經(jīng)有序，可以直接退出
# -*- coding:utf-8 -*-
def bubble_sort2(array):
'''
冒泡排序優(yōu)化：本次循環(huán)沒有冒泡（交換），說明數(shù)據(jù)已經(jīng)有序，可以直接退出
'''
compare_count = 0
for i in range(len(array) - 1):
swapped_flag = False
for j in range(len(array) - i - 1):
compare_count += 1
if array[j] > array[j+1]:
array[j], array[j+1] = array[j + 1], array[j]
swapped_flag = True
if not swapped_flag:
break
print('bubble_sort2 circle num:', compare_count)
return array
優(yōu)化2
bubble_sort2的基礎(chǔ)上再優(yōu)化。
優(yōu)化思路：在排序的過程中，數(shù)據(jù)可以從中間分為兩段，一段是無序狀態(tài)，另一段是有序狀態(tài)。每一次循環(huán)的過程中，記錄最后一個(gè)交換元素的索引，它便是有序和無序狀態(tài)的邊界下一次僅循環(huán)到邊界即可，從而減少循環(huán)次數(shù)，達(dá)到優(yōu)化。
# 冒泡排序優(yōu)化：本次循環(huán)沒有冒泡（交換），說明數(shù)據(jù)已經(jīng)有序，可以直接退出
def bubble_sort3(array):
'''
bubble_sort2的基礎(chǔ)上再優(yōu)化。
優(yōu)化思路：在排序的過程中，數(shù)據(jù)可以從中間分為兩段，一段是無序狀態(tài)，另一段是有序狀態(tài)。
每一次循環(huán)的過程中，記錄最后一個(gè)交換元素的索引，它便是有序和無序狀態(tài)的邊界
下一次僅循環(huán)到邊界即可，從而減少循環(huán)次數(shù)，達(dá)到優(yōu)化。
'''
compare_count = 0
last_swapped_index = 0
border = len(array) - 1 # 有序和無序的分界線
for i in range(len(array) - 1):
swapped_flag = False
for j in range(border):
compare_count += 1
if array[j] > array[j+1]:
array[j], array[j+1] = array[j + 1], array[j]
swapped_flag = True
last_swapped_index = j
if not swapped_flag:
break
border = last_swapped_index
print('bubble_sort3 circle num:', compare_count)
return array
3. 循環(huán)次數(shù)比較
if __name__ == '__main__':
array = [2, 4, 1, 3, 5, 8, 7, 8, 4, 9]
array2 = [] + array
array3 = [] + array
print('-'*20)
print bubble_sort(array)
print('-'*20)
print bubble_sort2(array2)
print('-'*20)
print bubble_sort3(array3)
輸出：
--------------------
('bubble_sort circle num:', 45)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
--------------------
('bubble_sort2 circle num:', 35)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
--------------------
('bubble_sort3 circle num:', 31)
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
冒泡排序復(fù)雜度
1.時(shí)間復(fù)雜度：
最小時(shí)間復(fù)雜度：最好的情況是數(shù)據(jù)一開始就是有序的，因此一次冒泡即可完成
最大時(shí)間復(fù)雜度：最壞的情況就是數(shù)據(jù)一開始就是倒序的，因此進(jìn)行 n-1 次冒泡
- 平均時(shí)間復(fù)雜度：O(n^2)
- 最大時(shí)間復(fù)雜度：O(n^2)
- 最小時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
