Java排序算法之冒泡排序的原理及優(yōu)化
冒泡排序原理
冒泡排序的思想很簡單:遍歷數(shù)組,比較相鄰的兩個元素,順序錯誤就把它們交換,直到整個數(shù)組排序完成。因為每經(jīng)過一趟排序,越小的元素會經(jīng)交換而慢慢“浮”到數(shù)列的頂端,因此叫做冒泡排序。
假設(shè)我們現(xiàn)在要對數(shù)組:arr= {3,9,-1,10,-2,5,21} 進行排序,結(jié)合上面的動圖,經(jīng)過第一趟排序后最大的元素會被排到最后。
第一趟排序
public int[] OneStepBubbleSort(int arr[]){ int temp = 0; for (int i = 0; i < arr.length - 1; i++){ if (arr[i] > arr[i + 1]){ temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.print("第1趟排序完成:"); System.out.println(Arrays.toString(arr)); return arr; }
測試:
public static void main(String[] args) { int[] arr = {3, 9, -1, 10, -2, 5, 21}; SortTest sortTest = new SortTest(); sortTest.OneStepBubbleSort(arr); }
結(jié)果:
那么第二趟排序后第二大的元素10會被排到倒數(shù)第二的位置。
第二趟排序
public int[] TwoStepBubbleSort(int arr[]){ int temp = 0; for (int i = 0; i < arr.length - 1 - 1; i++){ if (arr[i] > arr[i + 1]){ temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.print("第2趟排序完成:"); System.out.println(Arrays.toString(arr)); return arr; }
測試:
public static void main(String[] args) { int[] arr = {3, 9, -1, 10, -2, 5, 21}; SortTest sortTest = new SortTest(); sortTest.OneStepBubbleSort(arr); sortTest.TwoStepBubbleSort(arr); }
結(jié)果:
第三趟排序
public int[] ThreeStepBubbleSort(int arr[]){ int temp = 0; for (int i = 0; i < arr.length - 1 - 2; i++){ if (arr[i] > arr[i + 1]){ temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.print("第3趟排序完成:"); System.out.println(Arrays.toString(arr)); return arr; }
測試:
public static void main(String[] args) { int[] arr = {3, 9, -1, 10, -2, 5, 21}; SortTest sortTest = new SortTest(); sortTest.OneStepBubbleSort(arr); sortTest.TwoStepBubbleSort(arr); sortTest.ThreeStepBubbleSort(arr); }
結(jié)果:
如此類推,每一趟排序中不同的地方在于循環(huán)的終止條件:arr.length - 1 和 arr.length - 1 - 1 和 arr.length - 1 - 2 等等,那么只需要在此循環(huán)外面再包一層循環(huán)即可。最終代碼為:
冒泡排序算法代碼
public int[] BubbleSort(int arr[]){ int temp = 0; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - i - 1 ; j++) { if (arr[j] > arr[j + 1]){ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.print("第" + (i + 1) + "趟排序完成:"); System.out.println(Arrays.toString(arr)); } return arr; }
測試:
public static void main(String[] args) { int[] arr = {3, 9, -1, 10, -2, 5, 21}; SortTest sortTest = new SortTest(); System.out.println(); sortTest.BubbleSort(arr); }
結(jié)果:
改進冒泡排序
從上面冒泡排序的結(jié)果可以看出,總共進行了6趟排序,但從第4躺開始數(shù)組就已經(jīng)排序完畢了,后面的兩趟排序相當于在做無用的比較。
為了解決此問題,我們可以進行優(yōu)化,思想是:如果發(fā)現(xiàn)在某一趟排序中沒有發(fā)生過一次交換,那么可以提前結(jié)束冒泡排序。實現(xiàn)方法是設(shè)置一個flag變量來記錄是否發(fā)生過交換:
public int[] BubbleSort(int arr[]){ int temp = 0; boolean flag = false; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - i - 1 ; j++) { if (arr[j] > arr[j + 1]){ flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } // 判斷flag if (!flag){ // 如果flag是false,則退出 break; }else { // flag為true,說明發(fā)生過交換,那么在進行下一趟前需要把flag重新置為false flag = false; } System.out.print("第" + (i + 1) + "趟排序完成:"); System.out.println(Arrays.toString(arr)); } return arr; }
測試:
public static void main(String[] args) { int[] arr = {3, 9, -1, 10, -2, 5, 21}; SortTest sortTest = new SortTest(); System.out.println(); sortTest.BubbleSort(arr); }
結(jié)果:
到此這篇關(guān)于Java排序算法之冒泡排序的原理及優(yōu)化的文章就介紹到這了,更多相關(guān)Java冒泡排序的原理及優(yōu)化內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java中forward轉(zhuǎn)發(fā)與redirect重定向的區(qū)別
轉(zhuǎn)發(fā)和重定向都是常用的頁面跳轉(zhuǎn)方式,但在實現(xiàn)上有一些區(qū)別,本文主要介紹了Java中forward轉(zhuǎn)發(fā)與redirect重定向的區(qū)別,具有一定的參考價值,感興趣的可以了解一下2023-11-11SpringBoot接口請求入?yún)⒑统鰠⒃鰪姷奈宸N方法
這篇文章主要介紹了SpringBoot接口請求入?yún)⒑统鰠⒃鰪姷奈宸N方法,使用`@JsonSerialize`和`@JsonDeserialize`注解,全局配置Jackson的`ObjectMapper`,使用`@ControllerAdvice`配合`@InitBinder`,自定義HttpMessageConverter和使用AOP進行切面編程,需要的朋友可以參考下2024-07-07