好程序員Java學習路線分享冒泡排序及優化

? 好程序員Java學習路線分享冒泡排序及優化，冒泡排序是一定典型的交換排序，如排序規則是升序，有如下數列：

? A[0] A[1] A[2] A[3] ...... A[n]

? 將A[0]和A[1]比較，如果A[0]>A[1] ，則交換兩個元素的位置，否則不變， 再繼續比較A[1]和A[2]，直到A[n-1]和A[n]。即比較相鄰的兩個元素，如果前一個大，就交換（否則不交換），再繼續比較后面的元素，每一輪比較之后，最大的元素會移動到最后（完成一輪冒泡）；再開始第二輪冒泡，本次會選出第二大的元素。重復冒泡的過程，直到沒有相鄰的元素需要交換，則排序完成，像碳酸飲料中的氣泡，故而稱為冒泡排序。

???

簡化過程，設置一個簡單的數組，在編程中，元素的索引從0開始：

[5, 3, 1, 4, 2]

????int[] nums = {5, 3, 1, 4, 2};

????//要比較n次，n是數組中數字的個數

????for (int i = 0; i < nums.length; i++) {

????????//比較j和j+1位置的元素，每比較完一次，最大的元素會移動到末尾

????????for (int j = 0; j < nums.length - 1; j++) {

????????????if (nums[j] > nums[j + 1]) {

????????????????int temp = nums[j + 1];

????????????????nums[j + 1] = nums[j];

????????????????nums[j] = temp;

????????????}

????????}

????}

第一輪比較，經過這一輪比較，最大的元素在末尾

[<font color="red">5, 3</font>, 1, 4, 2] 比較第0和1個元素 ,交換 [<font color="red">3, 5</font>, 1, 4, 2]<br/>

[3,<font color="red"> 5, 1</font>, 4, 2] 比較第1和2個元素 ,交換 [3, <font color="red">1, 5</font>, 4, 2]<br/>

[3, 1, <font color="red">5, 4</font>, 2] 比較第2和3個元素 ,交換 [3,1, <font color="red"> 4, 5</font>, 2]<br/>

[3, 1, 4, <font color="red">5, 2</font>] 比較第3和4個元素 ,交換 [3, 1, 4, <font color="red">2, 5</font>] 最大的元素在末尾<br/>

第二輪比較，經過這輪比較，最大的兩個元素在末尾

[<font color="red">3, 1</font>, 4, 2, 5] 比較第0和1個元素 ,交換 [<font color="red">1, 3</font>, 4, 2, 5]<br/>

[1, <font color="red">3, 4</font>, 2, 5] 比較第1和2個元素 ,不動 [1, <font color="red">3, 4</font>, 2, 5]<br/>

[1, 3, <font color="red">4, 2</font>, 5] 比較第2和3個元素 ,交換 [1, 3, <font color="red">2, 4</font>, 5]<br/>

[1, 3, 2, <font color="red">4, 5</font>] 比較第3和4個元素 ,不動 [1, 3, 2, <font color="red">4, 5</font>] ?這次比較是多余的，因為第1輪過后，最大的元素在末尾<br/>

第三輪比較，經過這輪比較，最大的三個元素在末尾

[<font color="red">1, 3</font>, 2, 4, 5] 比較第0和1個元素 ,不動 [<font color="red">1, 3</font>, 2, 4, 5]<br/>

[1, <font color="red">3, 2</font>, 4, 5] 比較第1和2個元素 ,交換 [1, <font color="red">2, 3</font>, 4, 5]<br/>

[1, 2,<font color="red"> 3, 4</font>, 5] 比較第2和3個元素 ,不動 [1, 2, <font color="red">3, 4</font>, 5] ?這次比較多余的<br/>

[1, 2, 3, <font color="red">4, 5</font>] 比較第3和4個元素 ,不動 [1, 2, 3, <font color="red">4, 5</font>] ?這次比較是多余的<br/>

第四輪比較，經過這輪比較，最大的四個元素在末尾

[<font color="red">1, 2</font>, 3, 4, 5] 比較第0和1個元素 ,不動 [<font color="red">1, 2</font>, 3, 4, 5]<br/>

[1, <font color="red">2, 3</font>, 4, 5] 比較第1和2個元素 ,不動 [1, <font color="red">2, 3</font>, 4, 5] ?這次比較是多余的<br/>

[1, 2,<font color="red"> 3, 4</font>, 5] 比較第2和3個元素 ,不動 [1, 2, <font color="red">3, 4</font>, 5] ?這次比較是多余的<br/>

[1, 2, 3, <font color="red">4, 5</font>] 比較第3和4個元素 ,不動 [1, 2, 3, <font color="red">4, 5</font>] ?這次比較是多余的<br/>

第五輪比較，經過這輪比較，排序完成

[<font color="red">1, 2</font>, 3, 4, 5] 比較第0和1個元素 ,不動 [<font color="red">1, 2</font>, 3, 4, 5] ?這次比較是多余的<br/>

[1, <font color="red">2, 3</font>, 4, 5] 比較第1和2個元素 ,不動 [1, <font color="red">2, 3</font>, 4, 5] ?這次比較是多余的<br/>

[1, 2, <font color="red">3, 4</font>, 5] 比較第2和3個元素 ,不動 [1, 2, <font color="red">3, 4</font>, 5] ?這次比較是多余的<br/>

[1, 2, 3, <font color="red">4, 5</font>] 比較第3和4個元素 ,不動 [1, 2, 3, <font color="red">4, 5</font>] ?這次比較是多余的<br/>

可以看到冒泡排序每次都從頭比較，比較到末尾，但實際

第一輪比較后，最后1個數是最大的，下一輪不需要參與比較

第二輪比較后，最后2個數是最大的，下一輪不需要參與比較

第三輪比較后，最后3個數是最大的...

所以第n輪比較的時候，可以排除掉末尾已經排序好的元素，即末尾n-1個元素

int[] nums = {5, 3, 1, 4, 2};

????????//要比較n次，n是數組中數字的個數

????????for (int i = 0; i < nums.length; i++) {

????????????//比較j和j+1位置的元素，每比較完一次，最大的元素會移動到末尾

????????????//最后i個元素不參與本次比較

????????????for (int j = 0; j < nums.length - 1 - i; j++) {

????????????????if (nums[j] > nums[j + 1]) {

????????????????????int temp = nums[j + 1];

????????????????????nums[j + 1] = nums[j];

????????????????????nums[j] = temp;

????????????????}

????????????}

????????}

運行結果：

第一輪比較，經過這一輪比較，最大的元素在末尾

[<font color="red">5, 3</font>, 1, 4, 2] 比較第0和1個元素 ,交換 [<font color="red">3, 5</font>, 1, 4, 2]<br/>

[3,<font color="red"> 5, 1</font>, 4, 2] 比較第1和2個元素 ,交換 [3, <font color="red">1, 5</font>, 4, 2]<br/>

[3, 1, <font color="red">5, 4</font>, 2] 比較第2和3個元素 ,交換 [3,1, <font color="red"> 4, 5</font>, 2]<br/>

[3, 1, 4, <font color="red">5, 2</font>] 比較第3和4個元素 ,交換 [3, 1, 4, <font color="red">2, 5</font>] 最大的元素在末尾<br/>

第二輪比較，經過這輪比較，最大的兩個元素在末尾

[<font color="red">3, 1</font>, 4, 2, 5] 比較第0和1個元素 ,交換 [<font color="red">1, 3</font>, 4, 2, 5]<br/>

[1, <font color="red">3, 4</font>, 2, 5] 比較第1和2個元素 ,不動 [1, <font color="red">3, 4</font>, 2, 5]<br/>

[1, 3, <font color="red">4, 2</font>, 5] 比較第2和3個元素 ,交換 [1, 3, <font color="red">2, 4</font>, 5]<br/>

第三輪比較，經過這輪比較，最大的三個元素在末尾

[<font color="red">1, 3</font>, 2, 4, 5] 比較第0和1個元素 ,不動 [<font color="red">1, 3</font>, 2, 4, 5]<br/>

[1, <font color="red">3, 2</font>, 4, 5] 比較第1和2個元素 ,交換 [1, <font color="red">2, 3</font>, 4, 5]<br/>

第四輪比較，經過這輪比較，最大的四個元素在末尾

[<font color="red">1, 2</font>, 3, 4, 5] 比較第0和1個元素 ,不動 [<font color="red">1, 2</font>, 3, 4, 5]<br/>

上面的算法，可以減少重復比較的次數，比較的次數是固定的。但如果本來數組中的元素就相對有序，則會出現如下狀況：

初始數組是：[3, 1, 2, 4, 5]

第一輪

[<font color="red">3, 1</font>, 2, 4, 5]比較第0和1個元素,交換[<font color="red">1, 3</font>, 2, 4, 5]<br/>

[1,<font color="red"> 3, 2</font>, 4, 5]比較第1和2個元素,交換[1, <font color="red">2, 3</font>, 4, 5]<br/>

[1, <font color="red">2, 3</font>, 4, 5]比較第2和3個元素,不動[1, 2, <font color="red">3, 4</font>, 5]<br/>

[1, 2, <font color="red">3, 4</font>, 5]比較第3和4個元素,不動[1, 2, 3, <font color="red">4, 5</font>]<br/>

第二輪

[<font color="red">1, 2</font>, 3, 4, 5]比較第0和1個元素,不動[<font color="red">1, 2</font>, 3, 4, 5]<br/>

[1, <font color="red">2, 3</font>, 4, 5]比較第1和2個元素,不動[1, <font color="red">2, 3</font>, 4, 5]<br/>

[1, 2, <font color="red">3, 4</font>, 5]比較第2和3個元素,不動[1, 2, <font color="red">3, 4</font>, 5]<br/>

第三輪

[<font color="red">1, 2</font>, 3, 4, 5]比較第0和1個元素,不動[<font color="red">1, 2</font>, 3, 4, 5]<br/>

[1,<font color="red">2, 3</font>, 4, 5]比較第1和2個元素,不動[1, <font color="red">2, 3</font>, 4, 5]<br/>

第四輪

[<font color="red">1, 2</font>, 3, 4, 5]比較第0和1個元素,不動[1, 2, <font color="red">3, 4</font>, 5]<br/>

實際上數組中的元素，開始的時候只有數字3的位置需要移動，其它元素相對都是有序的。當3移動完成后，其它的元素不需要一定。所以在第二輪發現沒有任何元素交換之后，就表示排序已經完成，第三輪和第四輪是多余的。

對于冒泡排序的優化，如果某一輪比較中沒有發生任何交換，則代表排序已經完成，不需要再進行排序了：

????????int[] nums = {3, 1, 2, 4, 5};

????????boolean flag;//是否交換的標志

????????//要比較n次，n是數組中數字的個數

????????for (int i = 0; i < nums.length; i++) {

????????????// 每次遍歷標志位都要先置為false，才能判斷后面的元素是否發生了交換

????????????flag = false;

????????????//比較j和j+1位置的元素，每比較完一次，最大的元素會移動到末尾

????????????//最后i個元素不參與本次比較

????????????for (int j = 0; j < nums.length - 1 - i; j++) {

????????????????if (nums[j] > nums[j + 1]) {

????????????????????int temp = nums[j + 1];

????????????????????nums[j + 1] = nums[j];

????????????????????nums[j] = temp;

????????????????????flag = true; ???//表示本輪發生了交換

????????????????}

????????????}

????????????// 如果為false，代表本輪沒有交換，元素已經有序

????????????if(!flag) break;

????????}

????}

初始數組是：[3, 1, 2, 4, 5]

第一輪

[<font color="red">3, 1</font>, 2, 4, 5]比較第0和1個元素,交換[<font color="red">1, 3</font>, 2, 4, 5]<br/>

[1,<font color="red"> 3, 2</font>, 4, 5]比較第1和2個元素,交換[1, <font color="red">2, 3</font>, 4, 5]<br/>

[1, <font color="red">2, 3</font>, 4, 5]比較第2和3個元素,不動[1, 2, <font color="red">3, 4</font>, 5]<br/>

[1, 2, <font color="red">3, 4</font>, 5]比較第3和4個元素,不動[1, 2, 3, <font color="red">4, 5</font>]<br/>

第二輪

[<font color="red">1, 2</font>, 3, 4, 5]比較第0和1個元素,不動[<font color="red">1, 2</font>, 3, 4, 5]<br/>

[1, <font color="red">2, 3</font>, 4, 5]比較第1和2個元素,不動[1, <font color="red">2, 3</font>, 4, 5]<br/>

[1, 2, <font color="red">3, 4</font>, 5]比較第2和3個元素,不動[1, 2, <font color="red">3, 4</font>, 5]<br/>

在上面的排序中，3是最后一個移動的元素。3之后的元素都是有序的。所以只要比較3之前的元素即可。最后一次發生交換的元素，它后面的元素都是有序的，不需要再參與比較

int[] nums = {3, 1, 2, 4, 5};

????????boolean flag;//是否交換的標志

????????int lastExchangeIndex =0;//最后一次交換的位置

????????int sortBorder = nums.length - 1;

????????//要比較n次，n是數組中數字的個數

????????for (int i = 0; i < nums.length; i++) {

????????????// 每次遍歷標志位都要先置為false，才能判斷后面的元素是否發生了交換

????????????flag = false;

????????????//比較j和j+1位置的元素，每比較完一次，最大的元素會移動到末尾

????????????//最后i個元素不參與本次比較

????????????for (int j = 0; j < sortBorder ; j++) {

????????????????if (nums[j] > nums[j + 1]) {

????????????????????int temp = nums[j + 1];

????????????????????nums[j + 1] = nums[j];

????????????????????nums[j] = temp;

????????????????????flag = true; ???//表示本輪發生了交換

????????????????????lastExchangeIndex =j;//記錄最后一次發生交換的位置

????????????????}

????????????}

????????????// 如果為false，代表本輪沒有交換，元素已經有序

????????????sortBorder = lastExchangeIndex;

????????????if(!flag) break;

????????}

運行結果：

第一輪

[<font color="red">3, 1</font>, 2, 4, 5]比較第0和1個元素,交換[<font color="red">1, 3</font>, 2, 4, 5]<br/>

[1,<font color="red"> 3, 2</font>, 4, 5]比較第1和2個元素,交換[1, <font color="red">2, 3</font>, 4, 5]<br/>

[1, <font color="red">2, 3</font>, 4, 5]比較第2和3個元素,不動[1, 2, <font color="red">3, 4</font>, 5]<br/>

[1, 2, <font color="red">3, 4</font>, 5]比較第3和4個元素,不動[1, 2, 3, <font color="red">4, 5</font>]<br/>

第二輪

[<font color="red">1, 2</font>, 3, 4, 5]比較第0和1個元素,不動[<font color="red">1, 2</font>, 3, 4, 5]