冒泡算法python動态示範

冒泡算法

文章目錄

• 冒泡算法python動态示範
• • 冒泡算法
  • 冒泡算法python實作
  • 算法動态示範
  • 示範圖檔儲存

冒泡算法（後冒法）：

1、每次隻确定一個元素;

2、且隻有相鄰的元素進行交換;

3、兩個相鄰元素比較，如果該元素比它後面相鄰的元素小，則交換兩元素位置，一輪結束，确定一個元素位置已排好序列的最前面；

4、下輪從未排好序的元素開始下一輪排序，直到所有元素都排好。

優化：

1、如果不再發生交換時則停止循環;

2、在每輪結束後記錄最後一次交換的下标以便于減少周遊次數;

3、每次進行冒泡算法時最好将原清單進行複制,在複制清單進行操作防止改變原表。

冒泡算法python實作

def bubble_sotr(our_list):
    our_sorted_list = our_list[:]  # 防止改變原清單
    last_index = len(our_sorted_list) - 1#改進可以每次記錄最後交換的位置，不再交換的元素不需要進行排序
    for i in range(len(our_sorted_list)):  
        flag = True
        for j in range(last_index):
            if our_sorted_list[j] > our_sorted_list[j + 1]:
                flag = False
                our_sorted_list[j], our_sorted_list[j + 1] = our_sorted_list[j + 1], our_sorted_list[j]
                last_index = j
        if flag:
            break
    return our_sorted_list

#測試
our_list = [57, 98, 4, 3, 1, 5, 23, 4, 5, 6, 78, 79]
our_sorted_list = bubble_sotr(our_list)
print(our_list)#[57, 98, 4, 3, 1, 5, 23, 4, 5, 6, 78, 79]
print(our_sorted_list)#[1, 3, 4, 4, 5, 5, 6, 23, 57, 78, 79, 98]


           

算法動态示範

import matplotlib.pyplot as plt
def draw_bubble_sort(our_list):
    PAUSE_TIME = 4 / len(our_list)

    fig = plt.figure()
    ax = fig.add_subplot(1, 1, 1)
    ax.axis()
    plt.ion()
    our_sorted_list = our_list[:]  # 防止改變原清單
    last_index = len(our_sorted_list) - 1
    for i in range(len(our_sorted_list)):
        flag = True
        for j in range(last_index):
            if our_sorted_list[j] > our_sorted_list[j + 1]:
                flag = False
                our_sorted_list[j], our_sorted_list[j + 1] = our_sorted_list[j + 1], our_sorted_list[j]
                last_index = j
            plt.cla()#清除畫布
            ax.bar(range(len(our_sorted_list)), our_sorted_list, align='center')
            for a, b in zip(range(len(our_sorted_list)), our_sorted_list):
                ax.text(a, b + 0.05, b, ha='center')
            ax.bar(j, our_sorted_list[j], color='r', align='center')
            ax.bar(j + 1, our_sorted_list[j + 1], color='y', align='center')
            plt.pause(PAUSE_TIME)
        if flag:
            break
    return our_sorted_list

           

實驗結果：

示範圖檔儲存

雖然我們畫出了動态示範圖，但是圖檔的儲存比較麻煩。這裡我們使用 FuncAnimation() 來儲存。

首先我們需要一個動态更新函數，這裡我們建立一個更新類。

class Undate:
    def __init__(self, our_list, change_indexs):#初始化
        self.our_list = our_list#注意這裡的清單不再是我們需要排序的清單，而是排序過程中所有出現的清單可能性的集合
        self.fig = plt.figure()
        self.ax = self.fig.add_subplot(1, 1, 1)
        self.ax.axis()
        self.count = 0 #用于計數，讀取變化的清單
        self.change_indexs = change_indexs

    def update(self, j):#更新函數
        self.ax.cla()
        self.ax.bar(range(len(self.our_list[self.count])), self.our_list[self.count], align='center')
        for a, b in zip(range(len(self.our_list[self.count])), self.our_list[self.count]):
            self.ax.text(a, b + 0.05, b, ha='center')
        self.ax.bar(j, self.our_list[self.count][j], color='r', align='center')
        self.ax.bar(j + 1, self.our_list[self.count][j + 1], color='y', align='center')
        self.count += 1

    def iter_fun(self):	#疊代函數，生成器，用于讀取排序過程中變化的序列号
        for i in self.change_indexs:
            yield i

           

原來的排序函數需要重新寫：

def draw_bubble_sotr(our_list):
    PAUSE_TIME = 4 / len(our_list)

    fig = plt.figure()
    ax = fig.add_subplot(1, 1, 1)
    ax.axis('equal')
    plt.ion()

    our_sorted_list = our_list[:]  # 防止改變原清單
    last_index = len(our_sorted_list) - 1
    change_indexs = [] #計錄變化的清單序列
    change_list = []   #存儲變化的序列
    for i in range(len(our_sorted_list)): 
        flag = True
        for j in range(last_index):
            if our_sorted_list[j] > our_sorted_list[j + 1]:
                flag = False
                our_sorted_list[j], our_sorted_list[j + 1] = our_sorted_list[j + 1], our_sorted_list[j]
                last_index = j
            change_indexs.append(j) #加入清單序列号
            temp = our_sorted_list[:]
            change_list.append(temp)	#加入清單序列
        if flag:
            break

    return our_sorted_list, change_indexs, change_list
           

儲存動态圖：

our_list = [57, 98, 4, 3, 1, 5, 23, 4, 5, 6, 78, 79]
our_sorted_list, change_indexs, change_list = draw_bubble_sotr(our_list)
#建立更新類
up = Undate(change_list, change_indexs)
#調用FuncAnimation()函數，參數fig為畫布，參數func為需要傳入的更新函數、參數frames為需要傳給#func函數的參數，參數interval設定繪制速率。
ani = FuncAnimation(fig=up.fig, func=up.update, frames=up.iter_fun(), interval=400)
ani.save('bubble_sort.gif')#儲存圖檔