冒泡排序C++及Python實現及優化

來自專欄經典排序演算法

冒泡排序應該是大家最早接觸的排序演算法，剛開始學習C語言時候一般都會學習冒泡排序。下面來我們一起來複習一下冒泡排序吧。

冒泡排序（Bubble Sort）是一種交換排序。

演算法思想：從數組中第一個數開始，依次遍曆數組中的每一個數，通過相鄰元素，兩兩比較交換，每一輪循環找出剩餘未排序數的中的最大數並將其交換到未排序數列的末尾。即通過交換，較大數會往下沉到序列末尾，較小數會往上冒到序列頂端，這就是名字「冒泡」的由來。

演算法穩定性：穩定

演算法複雜度：

平均時間複雜度：

最壞時間複雜度：

最好時間複雜度：O(n)，只有在優化之後，且數列為正序時候才能達到。

空間複雜度：O(1)

時間複雜度分析過程：其外層循環執行 N - 1次。內層循環最多的時候執行N次，最少的時候執行1次，平均執行 次。

所以循環體內的比較交換約執行 。按照計算複雜度的原則，去掉常數，去掉最高項係數，其複雜度為

代碼如下：

#include <iostream>void Swap(int A[], int i, int j){ int temp = A[i]; A[i] = A[j]; A[j] = temp;}void BubbleSort(int A[], int n){ for (int i = 0; i < n - 1; i++) // 每次最大元素就像氣泡一樣"浮"到數組的最後 { for (int j = 0; j < n - 1 - i; j++) // 依次比較相鄰的兩個元素,使較大的那個向後移 { if (A[j] > A[j + 1]) // 如果條件改成A[i] >= A[i + 1],則變為不穩定的排序演算法 { Swap(A, j, j + 1); } } }}

優化1：

• 針對問題：
  數據的順序排好之後，冒泡演算法仍然會繼續進行下一輪的比較，直到 n-1次，後面的比較沒有意義的。
• 方案：
  設置標誌位flag，如果發生了交換flag設置為true；如果沒有交換就設置為false。
  這樣當一輪比較結束後如果flag仍為false，即：這一輪沒有發生交換，說明數據的順序已經排好，沒有必要繼續進行下去。

void BubbleSort(int A[], int n){ bool didSwap = true; // 設置標誌位 for (int i = 0; i < n - 1; i++) // 每次最大元素就像氣泡一樣"浮"到數組的最後 { didSwap = false; for (int j = 0; j < n - 1 - i; j++) // 依次比較相鄰的兩個元素,使較大的那個向後移 { if (A[j] > A[j + 1]) // 如果條件改成A[i] >= A[i + 1],則變為不穩定的排序演算法 { Swap(A, j, j + 1); didSwap = true; } } if(didSwap == false) break; }}

優化2：

• 針對問題： 已經遍歷出部分有序的序列後，那部分也不用進行遍歷，即發生交換的地方之後的地方不用遍歷。
• 方案：一標誌性變數pos,用於記錄每趟排序中最後一次進行交換的位置。由於pos位置之後的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。

void BubbleSort(int arr[], int len){ int i,temp; //記錄位置，當前所在位置和最後發生交換的地方 int current,last = len - 1; while(last > 0) { for(i = current = 0;i < last;++i){ if(arr[i] > arr[i+1]){ temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; //記錄當前的位置，如果沒有發生交換current值即for循環初始化的0 current = i; } } //若current = 0即已經沒有可以交換的元素了，即已經有序了 last = current; }}

還有一種優化方式，就是進行正方向兩個方向的雙向冒泡排序，在每一趟循環中，同時找到待排序的數組的最大值和最小值，從而使排序趟數大大減少，這種排序也叫做雞尾酒排序，實現較為簡單，這裡就不進行介紹了。

Python代碼：

def bubbleSort(input_list): if len(input_list) == 0: return [] sorted_list = input_list for i in range(len(sorted_list) - 1): for j in range(len(sorted_list) - 1): if sorted_list[j + 1] < sorted_list[j]: sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j] print(sorted_list) return sorted_list

推薦閱讀：