[排序篇] 冒泡排序

一、概念

二、冒泡排序

2.1?冒泡降序(從大到小排序)

2.2?冒泡升序(從小到大排序)

三、冒泡排序應用?

總結?

一、概念

冒泡排序核心思想：每次比較兩個相鄰的元素，如果它們不符合排序規則（升序或降序）則把它們交換過來。

二、冒泡排序

2.1?冒泡降序(從大到小排序)

冒泡降序：每次比較相鄰的兩個數，如果后面的數比前面的數大，則交換這兩個數的位置。?

假設將 12 18 76 35 99?這 5 個數進行從大到小的排序（即，越小的越靠后）。

如上圖所示，從左往右逐列看，5 個數總共需要遍歷 4 次（即 n - 1 次）；而每列從上往下逐行看，每遍歷一次總共需要排序 n - i 次（i 代表遍歷的次數）。

1. 首先看第一列：?

1.1 第一行：比較第 1 位和第 2 位的大小，發現 12 比 18 要小，因為是降序，所以需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 12 76 35 99；

1.2 第二行：比較第 2 位和第 3 位的大小，發現 12 比 76 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 76 12 35 99；

1.3 第三行：比較第 3 位和第 4 位的大小，發現 12 比 35 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 76 35 12 99；

1.4 第三行：比較第 4 位和第 5 位的大小，發現 12 比 99 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 76 35 99 12；?

遍歷第一次并經過 4 次排序后，5 個數中最小的一個?12 已經歸位到隊列的最后一位了（即第 5 位）。

2. 再看第二列：?

2.1 第一行：比較第 1 位和第 2 位的大小，發現 18 比 76 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 76 18 35 99 12；

2.2 第二行：比較第 2 位和第 3 位的大小，發現 18 比 35 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 76 35 18 99 12；

2.3 第三行：比較第 3 位和第 4 位的大小，發現 18 比 99 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 76 35 99 18 12；

遍歷第二次并經過 3 次排序后，5 個數中倒數第二小的一個?18 已經歸位到隊列的倒數第二位了（即第 4 位）。?

3. 再看第三列：?

2.1 第一行：比較第 1 位和第 2 位的大小，發現 76 比 35 要大，則不需要交換這兩個數的位置。并且這 5 個數的順序仍然是 76 35 99 18 12；

2.2 第二行：比較第 2 位和第 3 位的大小，發現 35 比 99 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 76 99 35 18 12；

遍歷第三次并經過 2 次排序后，5 個數中倒數第三小的一個?35 已經歸位到隊列的倒數第三位了（即第 3 位）。??

3. 最后看第四列：?

2.1 第一行：比較第 1 位和第 2 位的大小，發現 76 比 99 要小，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 99 76 35 18 12；

遍歷第四次并經過 1 次排序后，5 個數中倒數第四小的一個?76 已經歸位到隊列的倒數第四位了（即第 2 位）。?

最后總結一下：如果有 n 個數進行排序，只需將 n-1 個數歸位，也就是說要進行 n-1 次操作。而 “每一次” 都需要從第 1 位開始進行相鄰兩個數的比較，將較小的一個數放在后面，比較完畢后向后移一位繼續比較下面兩個相鄰數的大小，重復此步驟，直到最后一個尚未歸位的數，已經歸位的數則無需再進行比較。

冒泡降序例程1(推薦)：?

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //輸入一個數n，表示接下來有n個數for (int i = 0; i < n; i++) //循環讀入n個數到數組arr中scanf("%d", &arr[i]);//冒泡降序的核心代碼for (int i = 1; i <= n - 1; i++) { //n個數排序，只需進行 n-1 次(i從1開始，因此i需要包含 n-1)for (int j = 0; j < n - i; j++) { //i從1開始，則j從第1位(數組0下標)開始與后面一個數比較，直到最后一個尚未歸位的數(已歸位的數無需再比較，因此只需排序 n-i 次)if (arr[j] < arr[j+1]) { //相鄰兩個數比較大小并交換tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡降序例程2：?

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //輸入一個數n，表示接下來有n個數for (int i = 0; i < n; i++) //循環讀入n個數到數組arr中scanf("%d", &arr[i]);//冒泡降序的核心代碼for (int i = 0; i < n - 1; i++) { //n個數排序，只需進行 n-1 次(i從0開始，因此i不能包含 n-1)for (int j = 1; j < n - i; j++) { //i從0開始，則j從第2位(即數組1下標)開始與前面一個數比較，直到最后一個尚未歸位的數(已歸位的數無需再比較，因此只需排序 n-i 次)if (arr[j-1] < arr[j]) { //相鄰兩個數比較大小并交換tmp = arr[j-1];arr[j-1] = arr[j];arr[j] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡降序例程3：??

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //輸入一個數n，表示接下來有n個數for (int i = 0; i < n; i++) //循環讀入n個數到數組arr中scanf("%d", &arr[i]);//冒泡降序的核心代碼for (int i = 0; i < n - 1; i++) { //n個數排序，只需進行 n-1 次 (i從0開始，因此i不能包含 n-1)for (int j = 0; j < n - i - 1; j++) { //從第1位(數組0下標)開始與后面一個數比較，直到最后一個尚未歸位的數(已歸位的數無需再比較，然而i和j都是從0開始，因此只需排序 n-i-1 次)if (arr[j] < arr[j+1]) { //相鄰兩個數比較大小并交換tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

2.2?冒泡升序(從小到大排序)

冒泡升序：每次比較相鄰的兩個數，如果后面的數比前面的數小，則交換這兩個數的位置。?

假設將 99 35 18 76 12 這 5 個數進行從小到大的排序（即，越大的越靠后）。

1. 首先看第一列：?

1.1 第一行：比較第 1 位和第 2 位的大小，發現 99 比 35 要大，因為是升序，所以需要交換這兩個數的位置。交換之后這 5 個數的順序是 35 99 18 76 12；

1.2 第二行：比較第 2 位和第 3 位的大小，發現 99 比 18 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 35 18 99 76 12；

1.3 第三行：比較第 3 位和第 4 位的大小，發現 99 比 76 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 35 18 76 99 12；

1.4 第三行：比較第 4 位和第 5 位的大小，發現 99 比 12 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 35 18 76 12 99；

遍歷第一次并經過 4 次排序后，5 個數中最大的一個?99 已經歸位到隊列的最后一位了（即第 5 位）。

2. 再看第二列：?

2.1 第一行：比較第 1 位和第 2 位的大小，發現 35 比 18 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 35 76 12 99；

2.2 第二行：比較第 2 位和第 3 位的大小，發現 35 比 76 要小，則不需要交換這兩個數的位置。并且這 5 個數的順序仍然是 18 35 76 12 99；

2.3 第三行：比較第 3 位和第 4 位的大小，發現 76 比 12 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 35?12 76 99；

遍歷第二次并經過 3 次排序后，5 個數中第二大的一個?76 已經歸位到隊列的倒數第二位了（即第 4 位）。?

3. 再看第三列：?

2.1 第一行：比較第 1 位和第 2 位的大小，發現 18 比 35 要小，則不需要交換這兩個數的位置。并且這 5 個數的順序仍然是 18 35?12 76 99；

2.2 第二行：比較第 2 位和第 3 位的大小，發現 35 比 12 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 18 12 35?76 99；

遍歷第三次并經過 2 次排序后，5 個數中第三大的一個?35 已經歸位到隊列的倒數第三位了（即第 3 位）。??

3. 最后看第四列：?

2.1 第一行：比較第 1 位和第 2 位的大小，發現 18 比 12 要大，因此需要交換這兩個數的位置。交換之后這 5 個數的順序是 12 18 35?76 99；

遍歷第四次并經過 1 次排序后，5 個數中第四大的一個?18 已經歸位到隊列的倒數第四位了（即第 2 位）。?

最后總結一下：如果有 n 個數進行排序，只需將 n-1 個數歸位，也就是說要進行 n-1 次操作。而 “每一次” 都需要從第 1 位開始進行相鄰兩個數的比較，將較大的一個數放在后面，比較完畢后向后移一位繼續比較下面兩個相鄰數的大小，重復此步驟，直到最后一個尚未歸位的數，已經歸位的數則無需再進行比較。

冒泡升序例程1(推薦)：?

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //輸入一個數n，表示接下來有n個數for (int i = 0; i < n; i++) //循環讀入n個數到數組arr中scanf("%d", &arr[i]);//冒泡降序的核心代碼for (int i = 1; i <= n - 1; i++)) { //n個數排序，只需進行 n-1 次(i從1開始，因此i需要包含 n-1)for (int j = 0; j < n - i; j++) { //i從1開始，則j從第1位(數組0下標)開始與后面一個數比較，直到最后一個尚未歸位的數(已歸位的數無需再比較，因此只需排序 n-i 次)if (arr[j] > arr[j+1]) { //相鄰兩個數比較大小并交換tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡升序例程2：??

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //輸入一個數n，表示接下來有n個數for (int i = 0; i < n; i++) //循環讀入n個數到數組arr中scanf("%d", &arr[i]);//冒泡降序的核心代碼for (int i = 0; i < n - 1; i++) { //n個數排序，只需進行 n-1 次(i從0開始，因此i不能包含 n-1)for (int j = 1; j < n - i; j++) { //i從0開始，則j從第2位(即數組1下標)開始與前面一個數比較，直到最后一個尚未歸位的數(已歸位的數無需再比較，因此只需排序 n-i 次)if (arr[j-1] > arr[j]) { //相鄰兩個數比較大小并交換tmp = arr[j-1];arr[j-1] = arr[j];arr[j] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

冒泡升序例程3：?

#include <stdio.h>void main()
{int arr[5];int n;int tmp;scanf("%d", &n); //輸入一個數n，表示接下來有n個數for (int i = 0; i < n; i++) //循環讀入n個數到數組arr中scanf("%d", &arr[i]);//冒泡降序的核心代碼for (int i = 0; i < n - 1; i++) { //n個數排序，只需進行 n-1 次 (i從0開始，因此i不能包含 n-1)for (int j = 0; j < n - i - 1; j++) { //從第1位(數組0下標)開始與后面一個數比較，直到最后一個尚未歸位的數(已歸位的數無需再比較，然而i和j都是從0開始，因此只需排序 n-i-1 次)if (arr[j] > arr[j+1]) { //相鄰兩個數比較大小并交換tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");
}

三、冒泡排序應用?

假設一個班有 5 個學生，需要將這 5 個學生期末考試的分數，從高到低排序，并且輸出對應的學生姓名和性別。大家可以思考一下，該如何實現？

根據 2.1 冒泡降序原理，在此，我們只需要聲明一個結構體，其成員包含學生的姓名、性別和分數（假設滿分為 100，并分數只有整數）。下面是實際的例子。

#include <stdio.h>struct student {char name[24];char sex[8];int score;
};void main()
{struct student stu[5];struct student tmp;int n;scanf("%d", &n); //輸入班級總人數for (int i = 0; i < n; i++) //循環讀入學生總數到數組stu中scanf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].score);//開始對學生進行分數排序for (int i = 1; i <= n - 1; i++) {for (int j = 0; j < n - i; j++) {if (stu[j].score < stu[j+1].score) { //比較相鄰的兩個數，分數高的排前面tmp = stu[j];stu[j] = stu[j+1];stu[j+1] = tmp;}}}//輸出結果for (int i = 0; i < n; i++)printf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].score);printf("\n");
}

可以輸入以下數據進行驗證：

5

李文男?80
韓飛男?50
曉曉女?86
胡峰男?78
陳肖女?66

運行結果是：?

曉曉女?86

李文男?80
胡峰男?78
陳肖女?66
韓飛男?50

總結?

1.?冒泡降序：每次比較相鄰的兩個數，如果后面的數比前面的數大，則交換這兩個數的位置；

2.?冒泡升序：每次比較相鄰的兩個數，如果后面的數比前面的數小，則交換這兩個數的位置；

3. 從例程代碼來看，可知冒泡排序有很多種方法，但是萬變不離其宗，都是圍繞 “如果有 n 個數進行排序，則需遍歷?n-1 次，而?“每一次”?需要排序 n-i 次，并且都是從第 1 位開始進行相鄰兩個數的比較，將較小或較大的一個數放在后面，如此重復，直到最后一個尚未歸位的數” 展開。

4.?“冒泡降序” 與 “冒泡升序” 例程代碼的唯一差異是：相鄰的兩個數較小或較大的放在后面。例如，if (arr[j] <?arr[j+1]) 或?if (arr[j] > arr[j+1])；

5.?冒泡排序的核心部分是雙重嵌套循環。不難看出冒泡排序的時間復雜度是 O( $N^{2}$ )。這是一個非常高的時間復雜度。正如 Donald E. Knuth 所說：“冒泡排序除了它迷人的名字和導致了某些有趣的理論問題這一事實之外，似乎沒有什么值得推薦的。”