分享一下我對C語言中冒泡排序算法的學(xué)習(xí)和理解（裂開了，足足寫了一天，自閉中…）

文章目錄

• 冒泡排序
• 算法原理
• 實(shí)例演示
• 時間復(fù)雜度
• C語言實(shí)現(xiàn)代碼
• 加入用戶輸入程序
• 對于上述程序bug的解決方案
• 對算法進(jìn)行封裝及調(diào)用
• 運(yùn)行結(jié)果
• 算法優(yōu)化
• 寫在后面

---

冒泡排序

冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們的位置交換過來，走訪數(shù)列重復(fù)地進(jìn)行直到排序完成。因為越大（小）的元素經(jīng)過交換會慢慢地"浮"到數(shù)列的頂端（尾端），就如同碳酸飲料中的氣泡一樣，故名“冒泡排序”。

---

算法原理

以從大到小降序排列為例。

• 第一輪走訪開始 ----> 比較相鄰的元素- —> 如果第一個元素比第二個元素小，就交換他們的位置，把小的放到后面 ----> 如果第二個比第三個小，同樣交換他們的位置，以此類推 ----> 第一輪走訪結(jié)束

這個時候最小的數(shù)就“浮”到最右端了

• 第二輪走訪開始 ----> 比較相鄰的元素- —> 如果第一個元素比第二個元素小，就交換他們的位置，把小的放到后面 ----> 如果第二個比第三個小，同樣交換他們的位置，以此類推 ----> 第二輪走訪結(jié)束

這時候倒數(shù)第二小的數(shù)就“浮”到倒數(shù)第二列了

• 第三輪走訪開始 ----> 比較相鄰的元素- —> 如果第一個元素比第二個元素小，就交換他們的位置，把小的放到后面 ----> 如果第二個比第三個小，同樣交換他們的位置，以此類推 ----> 第三輪走訪結(jié)束

這時候倒數(shù)第三小的數(shù)就“浮”到倒數(shù)第三列了

• 以此類推，最多經(jīng)過n-1輪循環(huán)

  …

  …

所有元素從大到小排序完成

---

實(shí)例演示

對2 3 1 5 4進(jìn)行從大到小的降序排列。

第一輪走訪開始

2 3 1 5 4（比較2和3，交換位置）

3 2 1 5 4（比較2和1，不交換位置）

3 2 1 5 4（比較1和5，交換位置）

3 2 5 1 4（比較1和4，交換位置）

3 2 5 4 1（第一輪走訪結(jié)束）

最小的數(shù)1已經(jīng)在最后面了，因此第二輪排序只需要對前面四個數(shù)進(jìn)行再比較。

第二輪走訪開始

3 2 5 4 1（比較3和2，不交換位置）

3 2 5 4 1（比較2和5，交換位置）

3 5 2 4 1（比較2和4，交換位置）

3 5 4 2 1（第二輪走訪結(jié)束）

第二小的數(shù)已經(jīng)排在倒數(shù)第二個位置了，因此第三輪排序只需要對前面三個數(shù)進(jìn)行再比較。

第三輪走訪開始

3 5 4 2 1（比較3和5，交換位置）

5 3 4 2 1（比較3和4，交換位置）

5 4 3 2 1（第三輪走訪結(jié)束）

至此，排序結(jié)束。

---

時間復(fù)雜度

• 若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。
  所需的關(guān)鍵字比較輪數(shù)C和記錄移動輪數(shù)M均達(dá)到最小值：C=n-1和M=0。
  所以，冒泡排序最好的時間復(fù)雜度為O(n)
• 若初始文件是反序的，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i輪關(guān)鍵字的比較(1≤i≤n-1)，且每輪比較都必須移動記錄三輪來達(dá)到交換記錄位置。
  在這種情況下，比較和移動輪數(shù)均達(dá)到最大值：C=[n(n-1) ]/2=O(n^2) , M=[3n(n-1)]/2=O(n^2)
  所以，冒泡排序的最壞時間復(fù)雜度為O(n^2)
• 綜上，冒泡排序總的平均時間復(fù)雜度為O(n^2)

---

C語言實(shí)現(xiàn)代碼

#include<stdio.h> #define N 10 int main(void) {int arr[N] = { 0,3,2,5,8,4,7,6,9,1 };//創(chuàng)建一個大小為N的數(shù)組，方便理解算法int i = 0;//控制走訪輪數(shù)int j = 0;//控制數(shù)組元素下標(biāo)int temp = 0;//申請一個臨時的空間（數(shù)組元素交換時需要一個臨時空間）for (i = 0; i < N - 1; i++)//最多走訪N-1輪{for (j = 0; j < N - 1- i; j++)//每一輪相鄰元素只需比較N-1-i次即可{if (arr[j] < arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}//for循環(huán)執(zhí)行完畢，排序完成，依次打印出排序完成后的數(shù)組元素for (i = 0; i < N; i++)//變量i清零賦予新的意義：控制打印個數(shù){printf("%d ", arr[i]);}return 0; }

---

加入用戶輸入程序

//常見代碼會讓用戶輸入他要排序的數(shù)據(jù)個數(shù)，但是有時候用戶也不知道自己有幾個數(shù) //所以我想實(shí)現(xiàn)的是用戶只輸入一次數(shù)據(jù)，程序自動計算個數(shù)，然后在進(jìn)行排序的一個過程 //但是調(diào)試之后你會發(fā)現(xiàn)下面的程序 有bug！有bug！有bug！#include<stdio.h>int main(void) {int arr[1000];//創(chuàng)建一個長度為1000的數(shù)組int length = 0;//存放用戶輸入數(shù)據(jù)的個數(shù)int i = 0;//控制用戶輸入數(shù)據(jù)個數(shù)int j = 0;int temp = 0;printf("請輸入您要排序的數(shù)列，數(shù)與數(shù)之間用空格隔開\n");for(i = 0; getchar() != '\n';i++){scanf("%d", &arr[i]);if (arr[i] >= 0 && arr[i] < 1000){length++;}}printf("您總共輸入了%d個數(shù)據(jù)，重新排序后的結(jié)果如下：\n",length);for (i = 0; i < length -1; i++)//i清零賦予新的意義：在這里控制走訪論數(shù){for (j = 0; j < length - 1 - i; j++){if (arr[j] < arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}//for循環(huán)執(zhí)行完畢，排序完成，依次打印出排序完成后的數(shù)組元素for (i = 0; i < length; i++)//變量i清零賦予新的意義：控制打印個數(shù){printf("%d ", arr[i]);}return 0; }

---

對于上述程序bug的解決方案

如果你認(rèn)真測試了這個程序，你會發(fā)現(xiàn)程序有bug，程序會吞入用戶輸入的第一個字符，那么這個bug該如何解決呢。

（我真的整整搞了一下午才發(fā)現(xiàn)，這對于剛?cè)腴T的我也太太太太難了吧，差點(diǎn)就自閉了）

解決方法一：讓用戶在輸入數(shù)據(jù)之前先輸入一個字符給getchar()

解決方案二：申請一個flag整型變量，在第一次獲取用戶數(shù)據(jù)時將getchar()短路掉

//方案二更好一點(diǎn)，下面是按照方案二更改后的正確代碼 int main(void) {int arr[1000] = { 0 };int length = 0;int i = 0;int j = 0;int temp = 0;int flag = 1;//防止getchar（）吞掉用戶輸入字符printf("請輸入您要排序的數(shù)列，數(shù)與數(shù)之間用空格隔開\n");for(i = 0; flag||getchar() != '\n';i++){if (i == 0) flag--;//在i==0的時候，把getchar()短路掉,防止吞入用戶輸入的第一個字符。scanf("%d", &arr[i]);if (arr[i] >= 0 && arr[i] < 1000){length++;}}printf("您總共輸入了%d個數(shù)據(jù)，重新排序后的結(jié)果如下：\n",length);for (i = 0; i < length - 1; i++){for (j = 0; j < length - 1 - i; j++){if (arr[j] < arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}for (i = 0; i < length; i++){printf("%d ", arr[i]);}return 0; }

---

對算法進(jìn)行封裝及調(diào)用

#include<stdio.h>int arr[1000] ={ 0 } ; int length =0;//對于“獲取用戶輸入函數(shù)功能”的封裝 void scanf_sort(int* arr) {int i = 0;int flag = 1;printf("請輸入您要排序的數(shù)列，數(shù)與數(shù)之間用空格隔開\n");for (i = 0; flag || getchar() != '\n'; i++){if (i == 0) flag--;scanf("%d", &arr[i]);if (arr[i] >= 0 && arr[i] < 1000){length++;}}printf("您總共輸入了%d個數(shù)據(jù)，重新排序后的結(jié)果如下：\n", length); }//對于“冒泡排序“算法的封裝 void bubble_sort(int* arr) {int i = 0;int j = 0;int temp = 0;for (i = 0; i < length - 1; i++){for (j = 0; j < length - 1 - i; j++){if (arr[j] < arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}} }//對于排序完成后“數(shù)組打印”功能函數(shù)的封裝 int print_sort(int* arr,int length) {int i = 0;for (i = 0; i < length; i++){printf("%d ", arr[i]);} }//函數(shù)調(diào)用 int main(void) {scanf_sort(arr);bubble_sort(arr);print_sort(arr,length);return 0; }

---

運(yùn)行結(jié)果

雖然這個小小的程序就實(shí)現(xiàn)了簡單的"計算用戶輸入數(shù)據(jù)的個數(shù)"和"排序"兩個功能，但是我真的搞了一天哇，我太菜了…自閉中…

---

算法優(yōu)化

3 2 0 1 4 5 6 7 8 9從大到小排序，經(jīng)過一輪排序后會變成2 0 1 3 4 5 6 7 8 9

可以發(fā)現(xiàn)原序列的后半部分是已經(jīng)排好順序了，所以在進(jìn)行第二輪比較中，沒必要和4 5 6 7 8 9再進(jìn)行多余的比較

用flag代表比較的輪次，k代表該每一輪的比較次數(shù)，該優(yōu)化過程就是在每一輪次中都更新輪次flag的值，不斷縮小冒泡排序原始輪次范圍N，從而達(dá)到排序的最大效率，避免不必要的比較。

#include<stdio.h> #define N 10int main() {int arr[N] = { 3,0,1,2,4,5,6,7,8,9 };int i = 0;int j = 0;int k = 0;int temp = 0;int count = 1;int flag = 10;while (flag > 0){k = flag;//用k記錄每一輪的比較次數(shù)flag = 0;//while循環(huán)結(jié)束條件for (j = 0; j < k - 1; j++)if (arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = j + 1;//記錄符合交換條件的最終位置}if (flag)count++;//記錄比較輪次}printf("比較輪次:%d\n", count);for (i = 0; i < N; i++){printf("%d ", arr[i]);}printf("\n");return 0; }

---

寫在后面

啊啊啊啊啊，終于寫完了，裂開了，人沒了，寫了整整一天，文中的那個bug我搞了整整一下午，這也太虐我這個小白了吧，太難了，還有最后一個算法優(yōu)化我沒有完全敲出來，借鑒其他博主的，改了一點(diǎn)點(diǎn)，還沒搞懂代碼一步步的邏輯，明日再看。應(yīng)該還有其他的優(yōu)化方案吧，后面學(xué)算法和數(shù)據(jù)結(jié)構(gòu)的時候再繼續(xù)搞。

好累好累好累，給孩子點(diǎn)個贊吧。 好累好累好累，給孩子點(diǎn)個贊吧。 好累好累好累，給孩子點(diǎn)個贊吧。

窮且益堅，當(dāng)bug找到的那一刻，還有算法函數(shù)封裝完成的那一刻，我太激動了，這種感覺，這種感覺真的太爽了。

休息去了…

哦對，如果上邊有啥寫錯的地方，還請各位大佬在評論區(qū)給我訂正哈，謝謝。

總結(jié)

以上是生活随笔為你收集整理的C语言排序算法（一）：冒泡排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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