排序算法圖解之Java冒泡排序及優(yōu)化
1.冒泡排序簡介
冒泡排序（Bubble Sorting）即：通過對待排序的序列從前往后，依次比較相鄰元素的值，若發(fā)現逆序則交換位置，使較大的元素逐漸移動到后部，就像水底的氣泡一樣逐漸從水面冒出來，這就是冒泡名稱的由來
2.圖解算法
以將序列{3, 9, -1, 10, -20}從小到大排序為例！
基本思想就是，在每一趟排序實現將最大的數移到序列的最后端！這主要通過比較相鄰兩個元素實現，當相鄰的兩個元素逆序的時候，我們就交換它們。
第1趟排序：
第1趟排序共比較了4次，將最大的數10冒泡到了序列的尾部。
第2趟排序：
由于第一趟排序已經將最大是數10給冒泡到了最末端，因此在本次排序中，不需要再比較最后一個元素，故共比較了3次，將子序列（前四個元素）中最大的數9（整個序列中倒數第二大的數）冒泡到了子序列的尾端（原序列的倒數第二個位置）。
第3趟排序：
在第三趟排序時，同理，倒數兩個元素位置已經確定，即第一、第二大的數已經排好位置，只需要再將倒數第三大的數確認即可。故比較2次，實現倒數第三大的數3的位置確定。
第4趟排序：
在第四趟排序時，只有第一、第二個元素的位置還不確定，只需要比較一次，若逆序，則交換即可。到此，排序算法完成，原序列已經排序成為一個遞增的序列！
小結
一共進行了數組大小-1次趟排序，即外層循環(huán)arr.length-1次；每趟排序進行了逐趟減小次數的比較，即內層循環(huán)arr.length-i-1次，i從0依次增加。
3.冒泡排序代碼實現
參考代碼如下，為了便于觀察結果，在循環(huán)中添加了相應的輸出語句：
import java.util.Arrays;
/**
* @author 興趣使然黃小黃
* @version 1.0
* 冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array = {3, 9, -1, 10, -20};
//排序前
System.out.println("排序前:" + Arrays.toString(array));
//冒泡排序
for (int i = 0; i < array.length - 1; i++) {
System.out.println("第" + (i+1) + "趟排序開始!");
for (int j = 0; j < array.length - i - 1; j++) {
//如果前面的數比后面的數大，則交換
if(array[j] > array[j+1]){
//交換
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
}
System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
System.out.println("================================================");
}
//輸出排序后的結果
System.out.println("排序后:" + Arrays.toString(array));
}
}
實現結果：
4.冒泡排序算法的優(yōu)化
舉個例子，將待排序的序列改為：{5，1，2，3，4}，用以上算法來處理，觀察一下結果：
可以發(fā)現，當第一趟排序結束的時候，序列已經排序完成： 即將5冒泡到了最后，序列實現了從小到大排序。但是原冒泡排序算法，還是義無反顧的進行了數組大小-1趟排序（我可真是大冤種?。?/strong>
因此，我們需要嘗試對算法進行優(yōu)化！
發(fā)現：在冒泡排序的過程中，各個元素都在不斷的接近自己的位置，如果下一趟比較中沒有進行過任何交換，則說明序列已經有序， 則排序算法已經可以返回結果。因此，考慮在排序算法過程中添加一個標志flag判斷元素是否進行過交換，以減少不必要的冤種行為！
優(yōu)化代碼如下：
import java.util.Arrays;
/**
* @author 興趣使然黃小黃
* @version 1.0
* 冒泡排序優(yōu)化
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array = {5, 1, 2, 3, 4};
//排序前
System.out.println("排序前:" + Arrays.toString(array));
boolean flag = false; //用于標記是否進行了交換，true則說明進行了交換，false表示無
//冒泡排序
for (int i = 0; i < array.length - 1; i++) {
System.out.println("第" + (i+1) + "趟排序開始!");
for (int j = 0; j < array.length - i - 1; j++) {
//如果前面的數比后面的數大，則交換
if(array[j] > array[j+1]){
//交換
flag = true; //標記進行了交換
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
}
System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
System.out.println("================================================");
if (!flag){
//如果沒有進行交換則直接退出，說明排序已經完成
break;
}else {
//回退
flag = false;
}
}
//輸出排序后的結果
System.out.println("排序后:" + Arrays.toString(array));
}
}
四趟排序，優(yōu)化成了只需要兩趟排序！又是一個不可多得的小技巧！在算法程序題中，flag的設置是一種常用的編程思想，常常用于回溯算法中，小伙伴們要學會舉一反三~
到此這篇關于排序算法圖解之Java冒泡排序及優(yōu)化的文章就介紹到這了,更多相關Java冒泡排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了SpringMVC的詳細架構，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
MyBatis 是一款優(yōu)秀的持久層框架，它支持定制化 SQL、存儲過程以及高級映射。本文重點給大家介紹Mybatis的環(huán)境搭建和使用實例代碼，需要的朋友參考下吧2017-12-12
這篇文章主要介紹了詳解如何在低版本的Spring中快速實現類似自動配置的功能，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-05-05
解決BufferedReader.readLine()遇見的坑
這篇文章主要介紹了解決BufferedReader.readLine()遇見的坑，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
淺談springmvc的DispatcherServlet分析
本篇文章主要介紹了淺談springmvc的DispatcherServlet分析，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
本篇文章是對java事件注冊進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了java &與&&的區(qū)別的相關資料,并附簡單實例，幫助大家學習理解這部分知識，需要的朋友可以參考下2016-10-10
本文主要介紹了SpringBoot中數據傳輸對象(DTO)的實現,包括了手動創(chuàng)建DTO、使用ModelMapper和Lombok創(chuàng)建DTO的示例,具有一定的參考價值,感興趣的可以了解一下2024-07-07
這篇文章主要為大家詳細介紹了java實現百度云文字識別的接口代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-11-11
下面小編就為大家分享一篇Lucene實現索引和查詢的實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12