一、什么是冒泡排序
冒泡排序的英文是bubble sort，它是一種基礎的交換排序，說到冒泡是不是就想起了快樂肥宅水呢？汽水中有許多小小的水泡嘩啦嘩啦的浮到上面來，這是因為組成小氣泡的二訊訓碳比水輕，所以小氣泡可以一點一點地向上浮動，
而冒泡排序之所以叫冒泡排序，正是因為這種排序演算法的每一個元素都可以像小氣泡一樣，根據自身的大小，一點一點的向著陣列的一側移動，
二、圖解冒泡排序
我們先看一個例子，有七個數字組成一個無序數列{5，6，3，4，1，7}，對他進行冒泡排序，
按照冒泡排序的思想：把相鄰的兩個數字兩兩比較，當一個數字大于右側相鄰的數字時，交換他們的位置，當一個數字和他右側的數字小于或等于的時候，不交換，
這樣，作為數列中的最大的數字7就交換到了最右側，這時第一輪冒泡結束，（有效區域只有最后一個）
根據第一輪的交換細節，第二輪到第六輪的狀態為下圖，
到此為止，所有的數字都是有序的了，冒泡排序是一種穩定排序，由于該排序演算法的每一輪都要遍歷所有的數字，一共要遍歷n-1，所以時間復雜度為O(n^2)，
那么我們如何區分排序演算法是否穩定呢？
如果我們交換的時候，遇到兩個相同的數字，如果兩個相同的數字在排序之后相對位置沒有交換，那么就是穩定的排序，反之則是不穩定的排序，
三、代碼實作
public static void bubbleSort(int arr[]){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j <arr.length-i-1 ; j++) {
int tmp=0;
if(arr[j]>arr[j+1]){
tmp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tmp;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5,6,3,2,4,1,7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}四、代碼的優化
1、整體的思路
從上面的例子不難看出，我們可以對原來的冒泡排序進行優化，我們仍然用上面呢個數列{5，6，3，4，1，7}為例子，從上面的圖解可以看出在第五輪排序后，整個數列已經是有序的，但是排序演算法還是執行了第六輪排序，
優化的思路是：如果能判斷出數列已經是有序的了，并且做出標記，那么就不會執行多余的排序，
所以我們可以用布爾變數isSorted作為標記，如果在本輪排序中有元素進行交換，則說明數列無序；如果在本輪排序中，沒有元素進行交換，我們則認為此時數列已經為有序的，不需要再去進行下一輪的排序，
2、代碼示例
public static void bubbleSort(int arr[]){
for (int i = 0; i < arr.length-1; i++) {
//有序標記，每一輪的初始值都是true
boolean isSorted=true;
for (int j = 0; j < arr.length-i-1; j++) {
int tmp=0;
if (arr[j]>arr[j+1]){
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
//因為有元素進行交換，所以不是有序的，標記變為false
isSorted=false;
}
}
if (isSorted){
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5,6,3,2,4,1,7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/356981.html
標籤：java