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