冒泡排序的基本思想

從前往后（或從后往前）兩兩比較相鄰元素的值，若為逆序（即 $A\left[i?1\right]<A\left[i\right]$），則交換它們，直到序列比較完。

算法代碼

#include <iostream>
using namespace std;//冒泡排序算法 
void BubbleSort(int nums[],int n){int i,j,temp;for(i=0;i<n;i++){for(j=0;j<n-i-1;j++){		//一趟冒泡 if(nums[j]>nums[j+1]){	//逆序 temp=nums[j];		//交換 nums[j]=nums[j+1];nums[j+1]=temp;	}	}}
} //打印數組 
void printNum(int numbers[],int n){for(int i=0;i<n;i++){cout<<numbers[i]<<" ";}
}int main()
{int numbers[10]={3,44,38,5,47,15,36,26,27,2};int n=sizeof(numbers)/sizeof(numbers[0]);	//數組長度 BubbleSort(numbers,n);		//調用 BubbleSort 函數進行插入排序 printNum(numbers,n);		//打印數組 return 0;
}

算法性能分析

• 空間復雜度：$O(1)$

• 時間復雜度：$O(n^2)$

• 算法穩定性¹：穩定

---

1. 算法的穩定性：若待排序表中有兩個元素 $R_i$ 和 $R_j$，其對應的關鍵字相同即 $ke{y}_i=ke{y}_j$，且在排序前 $R_i$ 在 $R_j$ 的前面，若使用某一排序算法排序后， $R_i$ 仍在 $R_j$ 的前面，則稱這個排序算法是穩定的，否則稱排序算法是不穩定的。 ??