文章目錄
- 前言
- 一、什麼是冒泡排序？
- 二、算法思想
- 三、執行個體講解
- 四、算法分析
-
- 1.時間複雜度
- 2.空間複雜度
- 五、代碼實作
- 六、運作結果
- 總結
前言
相信大家在學習資料結構算法的時候經常會遇到的問題就是，老師講解完這個算法思想，自己也聽懂了，但一到自己寫代碼就寫不出來，或者是即便自己模模糊糊的照着網上的代碼自己寫出來了，但是過幾天就又忘了，其實這就是我們沒有深刻的了解的這個算法的思想。
接下來，我就結合圖例給大家詳細的講解一下。
一、什麼是冒泡排序？
冒泡排序的名字是因為元素排序的過程像水中的氣泡一樣一個一個的浮出水面，元素也一個一個從大到小（從小到大）的排序完成。
二、算法思想
1、兩兩相鄰的元素進行比較，如果前面元素大于後面元素就交換兩個元素的位置，最終的結果是最大的一個元素移動到了最後的位置。 我們暫稱這個過程為冒泡。
2、如果有n個元素那麼【冒泡操作】重複n-1次即可排序完成。
我們來看一個動圖來體會一下冒泡排序算法。
三、執行個體講解
我們有一個待排序序列是：【3,44,38,5,47,15,36】
如果要将這7個元素進行排序那麼需要進行6趟冒泡才能完成排序。
第一趟冒泡：
①第一個元素和第二個元素進行比較，第一個小于第二個位置不變。
②第二個元素和第三個元素比較，前面元素44大于後面元素38，是以交換兩元素的位置。
③交換完成後，繼續比較第三個和第四個元素的大小，前面元素44大于後面元素5，是以交換兩元素的位置。
③交換完成後，繼續比較第四個和第五個元素的大小，前面元素44小于後面元素47，是以兩元素的位置不變。
`
④繼續比較第五個和第六個元素的大小，前面元素47大于後面元素15，是以交換兩元素的位置。
⑤交換完成後，繼續比較第三個和第四個元素的大小，前面元素47大于後面元素36，是以交換兩元素的位置。
第一趟冒泡總結： 經過第一趟的冒泡，成功将這個序列中最大的元素47移動到了最後面，那麼我們在重複執行5次這個冒泡的過程，即可将所有元素從大到小排序完成了。外層for循環控制循環的趟數。
四、算法分析
1.時間複雜度
O(n2)
2.空間複雜度
空間複雜度由于需要開辟一個臨時空間是以是：O(1)
五、代碼實作
#include<stdio.h>
void Print(int array[],int len){
for(int i=0;i<len;i++){
printf("%d ",array[i]);
}
}
void BubbleSort(int array[],int len){
int tem;
//外層循環控制 排序的趟數 n個元素排序需要循環n-1次 【1】
for(int i=0;i<len-1;i++) {
//内層循環控制比較的次數 n個元素第i趟比較n-i次 【2】
for(int j=0;j<len-1-i;j++) {
//比較相鄰的元素大小 目的：将最大的元素選出到移動到最後
if(array[j]>array[j+1]){
tem = array[j];
array[j] = array[j+1];
array[j+1] = tem;
}
}
}
printf("\n\n排序完成！\n");
}
int main(){
int array[] = {3,44,38,5,47,15,36};
int len = sizeof(array) / sizeof(int);
printf("原始序列為：\n");
Print(array,len);
BubbleSort(array,len);
printf("\n排序後序列為：\n");
Print(array,len);
}
六、運作結果
總結
當我在學習完這個冒泡排序算法的時候嘗試自己寫代碼，但是有兩個地方我覺得容易出現問題所有在這裡說明一下：
【1】第一個for循環是控制進行幾次冒泡的，是以循環的次數的是待排序序列元素個數減一次。
【2】第二個for循環是控制每一趟冒泡兩兩元素間進行比較的，j從0到n-1,j+1從1到n這個地方我第一次 忽略-1，即j從0到n,那麼j+1就會超過了排序序列的最大長度。