目錄
- 一、視頻講解冒泡排序
- 二、冒泡排序的思想
- 思想:
- 三、冒泡排序的影片演示及思路分析
- 影片演示：
- 思路分析：
- 思路總結 ：
- 四、冒泡排序的代碼+代碼優化+代碼詳解
- 代碼--————多個for回圈分別控制排序：
- 結果：
- 優化代碼（版本1）--————兩個for回圈嵌套控制排序：
- 優化分析：
- 代碼：
- 結果：
- 優化代碼（版本2）--————兩個for回圈嵌套+標志控制排序：
- 優化分析：
- 代碼：
- 結果：
- 代碼詳解（優化版本2）
- 代碼--————多個for回圈分別控制排序：
冒泡排序是排序演算法中最易理解的一種排序方法，
今天就讓我們以非常容易理解的視頻+圖文+影片的形式來學習
我們的入門排序演算法：冒泡排序
點擊這里看【時間、空間復雜度的詳解】
點擊這里快速選取適合你的演算法入門書籍
一、視頻講解冒泡排序
點擊這里即可去B站觀看~
二、冒泡排序的思想
思想:
從前到后（即從下標較小的元素開始）依次比較相鄰元素的值，若發現逆序則交換位置，使值較大的元素逐漸從前移向后部，
eg:
待排序的數：7,3,22,15,8
根據冒泡排序的思想：
- 首先我們應該比較7和3是否是逆序的：
若逆序則交換這2個數的位置，因為7>3，它們的位置是逆序的故交換位置
交換后：7,3, 22,15,8 ? 3,7,22,15,8 - 比較7和22是否是逆序的：
若逆序則交換這2個數的位置，因為7<22，它們的位置是順序的，故不用交換位置
順序仍為：3,7,22, 15,8 ? 3,7,22, 15,8 - 以此類推，思路分析會進行詳細分析，
三、冒泡排序的影片演示及思路分析
影片演示：
點這里去可視化網站
思路分析：
- 第一輪排序：22的位置被固定
- 7和3比較，若逆序則交換位置，因為7>3兩數是逆序的，所以交換位置：
7,3, 22,15,8 ? 3,7, 22,15,8 - 7和22比較，若逆序則交換位置，因為7<22兩數是順序的，所以不交換位置：
3, 7, 22, 15,8 ? 3, 7, 22, 15,8 - 22和15比較，若逆序則交換位置，因為22>15兩數是逆序的，所以交換位置：
3,7, 22,15, 8 ? 3,7, 15,22, 8 - 22和8比較，若逆序則交換位置，因為22>8兩數是逆序的，所以交換位置：
3,7, 15, 22,8 ? 3,7, 15, 8,22
第一輪排序后的結果：【22的位置被固定】3,7, 15, 8,22
- 第二輪排序：15的位置被固定
- 3和7比較若逆序則交換位置，因為3<7兩數是順序的，所以不交換位置：
3,7, 15, 8,22 ? 3,7, 15, 8,22 - 7和15比較若逆序則交換位置，因為7<15兩數是順序的，所以不交換位置：
3, 7, 15, 8,22 ? 3, 7, 15, 8,22 - 15和8比較若逆序則交換位置，因為15>8兩數是逆序的，所以交換位置：
3, 7, 15, 8, 22 ? 3, 7, 8, 15, 22
第二輪排序后的結果：【15的位置被固定】3, 7, 8, 15, 22
- 第三輪排序：8的位置被固定
- 3和7比較若逆序則交換位置，因為3<7兩數是順序的，所以不交換位置：
3,7, 8, 15,22 ? 3,7, 8, 15,22 - 7和8比較若逆序則交換位置，因為7<8兩數是順序的，所以不交換位置：
3, 7, 8, 15,22 ? 3, 7, 8, 15,22
第三輪排序后的結果：【8的位置被固定】：3, 7, 8,15, 22
- 第四輪排序：7的位置被固定
- 3和7比較若逆序則交換位置，因為3<7兩數是順序的，所以不交換位置：
3,7, 8,15,22 ? 3,7, 8,15,22
第四輪排序后的結果：【7的位置被固定】：3, 7, 8,15, 22
排序到此結束
思路總結 ：
-
以上面的5個數為例，我們看到5個數進行排序需要進行4輪大的排序
那么n個數排序時，需要進行 （n-1） 輪大的排序， -
（1）上面五個數的第 一輪排序需進行4次（5個數參與排序，陣列下標0-4）
（2）上面五個數的第二輪排序需進行3次（4個數參與排序，陣列下標0-3）
（3）上面五個數的第三輪排序需進行2次（3個數參與排序，陣列下標0-2）
（4）上面五個數的第四輪排序需進行 1次（2個數參與排序，陣列下標0-1）
四、冒泡排序的代碼+代碼優化+代碼詳解
代碼--————多個for回圈分別控制排序：
package Sort;
import java.util.Arrays;
public class BubbleSort {
// 原始陣列：7,3,22,15,8陣列長度為5
public static void bubbleSort(int arr[]) {// 用此方法給陣列進行排序
int i = 0, temp = 0;// temp變數用來保存arr[i]和arr[i+1]中的大數
// 第一趟排序
for (i = 0; i < arr.length-1-0; i++) {//i<5 下標是0-4
//（需arr.length-1-0，因為如果只是arr.length那么當i=4時，arr[i+1]=5，不滿足i<5的條件,陣列會越界）
if (arr[i] > arr[i + 1]) {// 如果兩個數是逆序的，就交換位置
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
System.out.println("第一次排序"+Arrays.toString(arr));
}
// 第二趟排序
for (i = 0; i < arr.length-1-1; i++) {//i<4 下標是0-3, 22的位置已經確定
//（需arr.length-1-1，因為如果只是arr.length-1那么當i=3時，arr[i+1]=4，不滿足i<4的條件陣列會越界）
if (arr[i] > arr[i + 1]) {// 如果兩個數是逆序的，就交換位置
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
System.out.println("第二次排序"+Arrays.toString(arr));
}
// 第三趟排序
for (i = 0; i < arr.length-1-1-1; i++) {//i<3 下標是0-2 22、15的位置已經確定
//（需arr.length-1-1-1，因為如果只是arr.length-1-1那么當i=2時，arr[i+1]=3，不滿足i<3的條件陣列會越界）
if (arr[i] > arr[i + 1]) {// 如果兩個數是逆序的，就交換位置
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
System.out.println("第三次排序"+Arrays.toString(arr));
}
// 第四趟排序
for (i = 0; i < arr.length-1-1-1-1; i++) {//i<2 下標是0-1 22、15、8的位置已經確定
//（需arr.length-1-1-1-1，因為如果只是arr.length-1-1-1那么當i=1時，arr[i+1]=2，不滿足i<2的條件陣列會越界）
if (arr[i] > arr[i + 1]) {// 如果兩個數是逆序的，就交換位置
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
System.out.println("第四次排序"+Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[] = { 7, 3, 22, 15, 8 };
bubbleSort(arr);
}
}
結果：
優化代碼（版本1）--————兩個for回圈嵌套控制排序：
優化分析：
第一輪排序：i<arr.length-1-0
第二輪排序：i<arr.length-1-1
第三輪排序：i<arr.length-1-1-1
第四輪排序：i<arr.length-1-1-1-1
所以可以用一個for回圈嵌套在我們剛剛的for回圈上
這個變數j的范圍是0-3即j < arr.length - 1
arr.length=5,j<arr.length，j的范圍[0-4]
j<arr.length-1，j的范圍[0-3]
代碼：
package Sort;
import java.util.Arrays;
public class BubbleSort {
// 原始陣列：7,3,22,15,8陣列長度為5
public static void bubbleSort(int arr[]) {// 用此方法給陣列進行排序
int i = 0, temp = 0;// temp變數用來保存大數
int j = 0;
for (j = 0; j < arr.length - 1; j++) {
for (i = 0; i < arr.length - 1 - j; i++) {// i<5 下標是0-4
if (arr[i] > arr[i + 1]) {// 如果兩個數是逆序的，就交換位置
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
System.out.println("第" + (j + 1) + "次排序" + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[] = { 7, 3, 22, 15, 8 };
bubbleSort(arr);
}
}
結果：
優化代碼（版本2）--————兩個for回圈嵌套+標志控制排序：
優化分析：
當第二輪排序完成后，陣列已經是有序的，
但是沒有一個標志去告訴for回圈，陣列已經有序，該退出for回圈了，
所以針對這個問題，我們定義一個boolean flag = false;來判斷是否結束for回圈
如果flag == false，說明陣列已經有序，可以退出for回圈了
如果flag == true，我們需要讓flag=false；以便下次陣列有序時，可以退出for回圈，
代碼：
package Sort;
import java.util.Arrays;
public class BubbleSort {
// 原始陣列：7,3,22,15,8陣列長度為5
public static void bubbleSort(int arr[]) {// 用此方法給陣列進行排序
int i = 0, temp = 0;// temp變數用來保存大數
int j = 0;
boolean flag = false;
for (j = 0; j < arr.length - 1; j++) {
for (i = 0; i < arr.length - 1 - j; i++) {// i<5 下標是0-4
if (arr[i] > arr[i + 1]) {// 如果兩個數是逆序的，就交換位置
flag = true;//flag為true說明兩數逆序，需要交換位置
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
if(flag==false) {//第二個for回圈每回圈一輪后進行比較，說明陣列已經是有序的了可以退出回圈了,整個for回圈結束
break;
}else {
flag=false;//如果不滿足flag==false的條件，就說明陣列的兩數之間發生了交換，
// flag的值為true，為了優化，需要將flag再置為false
}
System.out.println("第" + (j + 1) + "次排序" + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[] = { 7, 3, 22, 15, 8 };
bubbleSort(arr);
}
}
結果：
代碼詳解（優化版本2）
以7,3,22,15,8為例：
- 第一輪排序：22的位置被固定
- 7和3比較，若逆序則交換位置，因為7>3兩數是逆序的，所以交換位置：flag==true
7,3, 22,15,8 ? 3,7, 22,15,8 - 7和22比較，若逆序則交換位置，因為7<22兩數是順序的，所以不交換位置：flag==false（第一輪排序完成后才判斷flag的值）
3, 7, 22, 15,8 ? 3, 7, 22, 15,8 - 22和15比較，若逆序則交換位置，因為22>15兩數是逆序的，所以交換位置：flag==true
3,7, 22,15, 8 ? 3,7, 15,22, 8 - 22和8比較，若逆序則交換位置，因為22>8兩數是逆序的，所以交換位置：flag==true
3,7, 15, 22,8 ? 3,7, 15, 8,22
第一輪排序后flag==ture滿足
else {
flag=false;//如果不滿足flag==false的條件，就說明陣列的兩數之間發生了交換，
// flag的值為true，為了優化，需要將flag再置為false
}`
所以flag=false，再開始第二輪排序
【22的位置被固定】3,7, 15, 8,22
- 第二輪排序：15的位置被固定
- 3和7比較若逆序則交換位置，因為3<7兩數是順序的，所以不交換位置：flag==false（第二輪排序完成后才判斷flag的值）
3,7, 15, 8,22 ? 3,7, 15, 8,22 - 7和15比較若逆序則交換位置，因為7<15兩數是順序的，所以不交換位置：flag==false（第二輪排序完成后才判斷flag的值）
3, 7, 15, 8,22 ? 3, 7, 15, 8,22 - 15和8比較若逆序則交換位置，因為15>8兩數是逆序的，所以交換位置：flag==true
3, 7, 15, 8, 22 ? 3, 7, 8, 15, 22
第二輪排序后flag==ture滿足
else {
flag=false;//如果不滿足flag==false的條件，就說明陣列的兩數之間發生了交換，
// flag的值為true，為了優化，需要將flag再置為false
}`
所以flag=false，再開始第三輪排序
【15的位置被固定】3, 7, 8, 15, 22
- 第三輪排序
- 3和7比較若逆序則交換位置，因為3<7兩數是順序的，所以不交換位置：flag==false（第三輪排序完成后才判斷flag的值）
3,7, 8, 15,22 ? 3,7, 8, 15,22 - 7和8比較若逆序則交換位置，因為7<8兩數是順序的，所以不交換位置：flag==false（第三輪排序完成后才判斷flag的值）
3, 7, 8, 15,22 ? 3, 7, 8, 15,22
第三輪排序后flag==false滿足
if(flag==false) {//第二個for回圈每回圈一輪后進行比較，說明陣列已經是有序的了可以退出回圈了,整個for回圈結束
break;
}
所以退出第一個for回圈，結束陣列排序，輸出排序后的結果，
到此冒泡排序的講解就結束了~~
歡迎大家來 “小喬的編程內容分享站” 找小喬玩~
一起學習Java基礎+演算法~
還有更多資源等你來拿哦~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63639.html
標籤：其他
下一篇：自己實作一個動態陣列