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

成都創(chuàng)新互聯公司專注于康保網站建設服務及定制，我們擁有豐富的企業(yè)做網站經驗。 熱誠為您提供康保營銷型網站建設，康保網站制作、康保網頁設計、康保網站官網定制、小程序定制開發(fā)服務，打造康保網絡公司原創(chuàng)品牌,更為您提供康保網站排名全網營銷落地服務。

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

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

???

簡化過程，設置一個簡單的數組，在編程中，元素的索引從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移動完成后，其它的元素不需要一定。所以在第二輪發(fā)現沒有任何元素交換之后，就表示排序已經完成，第三輪和第四輪是多余的。

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

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

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

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

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

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

????????????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; ???//表示本輪發(fā)生了交換

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

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

????????????// 如果為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之前的元素即可。最后一次發(fā)生交換的元素，它后面的元素都是有序的，不需要再參與比較

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，才能判斷后面的元素是否發(fā)生了交換

????????????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; ???//表示本輪發(fā)生了交換

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

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

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

????????????// 如果為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]

本文標題：好程序員Java學習路線分享冒泡排序及優(yōu)化
網站網址：http://aaarwkj.com/article32/ggphpc.html

成都網站建設公司_創(chuàng)新互聯，為您提供微信公眾號、網站內鏈、企業(yè)建站、標簽優(yōu)化、、虛擬主機

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯