算法-排序-冒泡排序

2019-11-06 06:20:39

字體：大中小

來源：轉載

供稿：網友

原理

　　所謂冒泡排序法，就是對一組數字進行從大到小或者從小到大排序的一種算法（因為越大或越小的元素會經由交換慢慢“浮”到數列的頂端，故名）。具體方法是，從第一個數值開始，如果相鄰兩個數的排列順序與我們的期望不同，則將兩個數的位置進行交換；如果其與我們的期望一致，則不用交換。一般地，如果有N個數需要排序，則需要進行（N-1）趟起泡，改進版的冒泡排序需要排序的次數可能會有所減少。　　下面這個算法是我們很容易想到的：

void bubble_sort1(int a[],int n) { int i, j; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } }}

　　根據上面排序的算法，我們以{1，3，6，5，8，4}為例進行分析。首先這樣的算法對六個數來說需要排5趟，每一趟的結果如下：　　第一趟：{1，3，5，6，4，8} 　　第二趟：{1，3，5，4，6，8} 　　第三趟：{1，3，4，5，6，8} 　　第四趟：{1，3，4，5，6，8} 　　第五趟：{1，3，4，5，6，8} 　　像上面這種情況，其實我們只用了三趟數據就已經有序了，那怎樣改進才能不用每次都要排（N-1）趟呢？　　其實我們可以在每次發生數據交換的地方做一個標記，如果發生了數據交換，我們就繼續排下去，如果沒有發生數據交換，那就說明數據已經是有序的了，此時我們就可以不用再排下去了。從而使排序更高效一些。我們可以使用下面的改進版本的冒牌排序：

void bubble_sort2(int a[], int n) { int i, j, flag; for (i = n - 1; i > 0; i--) { flag = 0; for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = 1; } } if (flag==0) { //若沒有發生交換，說明數據已經有序 break; } }}

冒泡排序的時間復雜度

　　冒泡排序的時間復雜度是O(N2)。　　假設被排序的數列中有N個數。遍歷一趟的時間復雜度是O(N)，需要遍歷多少次呢？N-1次！因此，冒泡排序的時間復雜度是O(N2)。

冒泡排序的穩定性

　　冒泡排序是穩定的算法，它滿足穩定算法的定義。　　算法穩定性 – 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。所以這個排序算法是穩定的！

一個完整的示例

#include<stdio.h>//求數組的長度#define LEN(array) (sizeof(array))/(sizeof(array[0]))//交換兩個數#define swap(a,b) (a^=b,b^=a,a^=b)// 使用時要傳址//void swap(int* x, int* y) {// int tep = *x;// *x = *y;// *y = tep;//}void bubble_sort1(int a[],int n) { int i, j; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } }}void bubble_sort2(int a[], int n) { int i, j, flag; for (i = n - 1; i > 0; i--) { flag = 0; for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = 1; } } if (flag==0) { //若沒有發生交換，說明數據已經有序 break; } }}void main() { int i; int a[] = { 1,3,2,8,5,7}; int len = LEN(a); 　　　運行結果如下：　　　冒泡排序運行結果