冒泡排序

基本思想：從后往前（或者從前往后）兩兩比較相鄰元素的值，若為逆序，則交換他們，直到序列比較完。當一整趟下來都沒有元素被移動，代表算法可以提前結(jié)束。好比于關(guān)鍵字小的元素逐漸往上漂浮直到冒出水面，關(guān)鍵字打的元素如石頭一般下沉到水底。

void BubbleSort(ElemType A[], int n) {for(int i=0; i<n-1; i++){flag = false; //表示本趟冒泡是否發(fā)生交換的標志for(int j=n-1; j>i; j--){if(A[j-1] > A[j]){swap(A[j-1], A[j]);flag = true;}}if(flag == false)break; } }

空間效率：O（1）

時間效率：比較次數(shù)：n（n-1）/2；移動次數(shù)：3n（n-1）/2；時間復(fù)雜度O（n2）

穩(wěn)定性：不會交換相同關(guān)鍵字的元素順序

雙向冒泡排序

荷蘭國旗問題

設(shè)有一個僅有紅、白、藍三個顏色的條塊組成的條塊序列，要求時間復(fù)雜度為O（n），使得按照紅、白、藍的順序排好，即組成荷蘭國旗的圖案

typedef enum {RED, WHITE, BLUE} color;void Flag_Arrange(color a[], int n) {int i=0, j=0, k=n-1;while(j<=k){switch(a[j]){case RED:swap(a[i], a[j]);i++;j++;break;case WHITE:j++;break;case BLUE:swap(a[j], a[k]);k--; //不進行j++是因為防止交換后a[j]仍是藍色的情況break;}} }

總結(jié)

以上是生活随笔為你收集整理的更好用的冒泡排序、双向冒泡排序，拓展荷兰国旗问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。