冒泡排序是一種基礎(chǔ)的交互排序铝阐，每一個(gè)元素根據(jù)自身大小嵌器，一點(diǎn)點(diǎn)地向著數(shù)組一側(cè)移動(dòng)。比如有數(shù)字無(wú)序數(shù)列{4,3,2,1}，按照從小到大的順序排列闽寡。按照冒泡排序的思想， 我們要把相鄰的元素兩兩比較及刻， 當(dāng)一個(gè)元素大于右側(cè)相鄰元素時(shí)岂丘， 交換它們的位置； 當(dāng)一個(gè)元素小于或等于右側(cè)相鄰元素時(shí)销部， 位置不變摸航。
思路：
通過(guò)兩個(gè)元素相互比較制跟，當(dāng)元素大于右側(cè)元素時(shí)，交換位置酱虎，通過(guò)一次循環(huán)就可以將最大的值移動(dòng)到數(shù)組的最右端雨膨；這僅僅將最大的值移動(dòng)到數(shù)組最右端，還有其他的元素并未排序读串，所以我們還需要從頭開(kāi)始進(jìn)行比較聊记，將其他元素進(jìn)行排序，不考慮性能的情況下恢暖，還需要進(jìn)行數(shù)組長(zhǎng)度-1次的循環(huán)排监，也就是需要雙循環(huán)。那么內(nèi)循環(huán)用來(lái)進(jìn)行元素比較并交互位置杰捂，外循環(huán)則是需要進(jìn)行內(nèi)循環(huán)的次數(shù)舆床。
冒泡排序.gif
**** 算法
/**
* 此排序是一種穩(wěn)定排序，值相等的元素并不會(huì)打亂原本的順序琼娘。
* @param arr
*/
private static void sort_1(int[] arr){
int count = 0;
for (int i = 0; i < arr.length - 1 ; i++) {
for (int j = 0; j < arr.length - 1; j++) {
System.out.println("外層循環(huán)i:"+i+" 內(nèi)層循環(huán)j:"+j);
System.out.println("比較元素的位置: ["+j+"] vs ["+(j + 1)+"]");
int temp = 0;
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
count = count +1;
System.out.println("數(shù)組:"+ Arrays.toString(arr));
}
}
System.out.println("循環(huán)次數(shù):"+count);
}
控制臺(tái)：
數(shù)組:[4, 3, 2, 1]
外層循環(huán)i:0 內(nèi)層循環(huán)j:0
比較元素的位置: [0] vs [1]
數(shù)組:[3, 4, 2, 1]
外層循環(huán)i:0 內(nèi)層循環(huán)j:1
比較元素的位置: [1] vs [2]
數(shù)組:[3, 2, 4, 1]
外層循環(huán)i:0 內(nèi)層循環(huán)j:2
比較元素的位置: [2] vs [3]
數(shù)組:[3, 2, 1, 4]
外層循環(huán)i:1 內(nèi)層循環(huán)j:0
比較元素的位置: [0] vs [1]
數(shù)組:[2, 3, 1, 4]
外層循環(huán)i:1 內(nèi)層循環(huán)j:1
比較元素的位置: [1] vs [2]
數(shù)組:[2, 1, 3, 4]
外層循環(huán)i:1 內(nèi)層循環(huán)j:2
比較元素的位置: [2] vs [3]
數(shù)組:[2, 1, 3, 4]
外層循環(huán)i:2 內(nèi)層循環(huán)j:0
比較元素的位置: [0] vs [1]
數(shù)組:[1, 2, 3, 4]
外層循環(huán)i:2 內(nèi)層循環(huán)j:1
比較元素的位置: [1] vs [2]
數(shù)組:[1, 2, 3, 4]
外層循環(huán)i:2 內(nèi)層循環(huán)j:2
比較元素的位置: [2] vs [3]
數(shù)組:[1, 2, 3, 4]
循環(huán)次數(shù):9
**** 算法2
算法1時(shí)可以再優(yōu)化的峭弟，觀察算法1的日志，我們可以發(fā)現(xiàn)經(jīng)過(guò)第一輪的排序后脱拼，最大值4移動(dòng)到數(shù)組最右端瞒瘸；進(jìn)行第二輪的排序，因?yàn)?已經(jīng)是最大的值了熄浓，沒(méi)必要再跟其前面的值比較了情臭，所以這部分可以優(yōu)化，也就是每一輪排序后會(huì)出現(xiàn)一個(gè)有序區(qū)域赌蔑，有序區(qū)域的就不必比較了俯在。也就是內(nèi)層循環(huán)要去除有序區(qū)域，也就是j < arr.length - i - 1
private static void sort_1(int[] arr){
int count = 0;
for (int i = 0; i < arr.length - 1 ; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
System.out.println("外層循環(huán)i:"+i+" 內(nèi)層循環(huán)j:"+j);
System.out.println("比較元素的位置: ["+j+"] vs ["+(j + 1)+"]");
int temp = 0;
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
count = count +1;
System.out.println("數(shù)組:"+ Arrays.toString(arr));
}
}
System.out.println("循環(huán)次數(shù):"+count);
}
控制臺(tái)：
數(shù)組:[4, 3, 2, 1]
外層循環(huán)i:0 內(nèi)層循環(huán)j:0
比較元素的位置: [0] vs [1]
數(shù)組:[3, 4, 2, 1]
外層循環(huán)i:0 內(nèi)層循環(huán)j:1
比較元素的位置: [1] vs [2]
數(shù)組:[3, 2, 4, 1]
外層循環(huán)i:0 內(nèi)層循環(huán)j:2
比較元素的位置: [2] vs [3]
數(shù)組:[3, 2, 1, 4]
外層循環(huán)i:1 內(nèi)層循環(huán)j:0
比較元素的位置: [0] vs [1]
數(shù)組:[2, 3, 1, 4]
外層循環(huán)i:1 內(nèi)層循環(huán)j:1
比較元素的位置: [1] vs [2]
數(shù)組:[2, 1, 3, 4]
外層循環(huán)i:2 內(nèi)層循環(huán)j:0
比較元素的位置: [0] vs [1]
數(shù)組:[1, 2, 3, 4]
循環(huán)次數(shù):6
**** 算法3
/**
* 數(shù)組舉例：{7,1,2,3,4,5,6}
* 優(yōu)化策略：減少循環(huán)比較趟數(shù)
* 增加一個(gè)標(biāo)記(isSorted,默認(rèn)是true),每次發(fā)生交換娃惯，說(shuō)明目前數(shù)組還是無(wú)序的跷乐，isSorted置為false,
* 如果這趟循環(huán)沒(méi)有發(fā)生交換，說(shuō)明目前數(shù)組已經(jīng)是有序的了趾浅，那么剩下的幾趟排序都不需要執(zhí)行了愕提，提前結(jié)束。
* @param arr
*/
private static void sort_2(int[] arr){
for (int i = 0; i < arr.length - 1 ; i++) {
//數(shù)組有序標(biāo)記位皿哨，默認(rèn)為true,假設(shè)是有序的浅侨，發(fā)生交換就會(huì)標(biāo)記為無(wú)序
boolean isSorted = true;
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//因?yàn)橛性剡M(jìn)行交換，數(shù)組不是有序的证膨，標(biāo)記為false
isSorted = false;
}
}
if (isSorted) break;
}
}
**** 算法4
/**
* 優(yōu)化策略：減少每趟的循環(huán)次數(shù)
* 情景：每次循環(huán)后如输，右面的很多元素已經(jīng)是有序的，算法還是會(huì)循環(huán)比較有序的元素
* 優(yōu)化：定義無(wú)序數(shù)組的邊界，每次比較到邊界為止不见，不進(jìn)行后面的比較了澳化。
*/
private static void sort_3(int[] array){
// 最后一次交換的下標(biāo)
int lastSwapIndex = 0;
// 無(wú)序數(shù)組的邊界，每次比較比到這里為止
int arrBoundary = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
// 數(shù)組有序標(biāo)記位脖祈，默認(rèn)為true,假設(shè)是有序的肆捕，發(fā)生交換就會(huì)標(biāo)記為無(wú)序
boolean isSorted = true;
for (int j = 0; j < arrBoundary; j++) {
if (array[j] > array[j + 1]) {
int temp = 0;
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
// 因?yàn)橛性剡M(jìn)行交換，數(shù)組不是有序的盖高，標(biāo)記為false
isSorted = false;
// 最后一次交換元素的位置
lastSwapIndex = j;
}
}
// 把最后一次交換元素的位置賦值給無(wú)序數(shù)組的邊界
arrBoundary = lastSwapIndex;
// 說(shuō)明上面內(nèi)層for循環(huán)中慎陵，沒(méi)有交換任何元素，直接跳出外層循環(huán)
if (isSorted) {
break;
}
}
}
**** 算法5
/**
* 優(yōu)化策略：減少內(nèi)存開(kāi)銷(xiāo)
* 情景：每次循環(huán)都會(huì)創(chuàng)建temp這個(gè)變量
* 優(yōu)化：通過(guò)異或操作來(lái)交換兩個(gè)元素位置
*/
private static void sort_4(int[] array){
// 最后一次交換的下標(biāo)
int lastSwapIndex = 0;
// 無(wú)序數(shù)組的邊界喻奥，每次比較比到這里為止
int arrBoundary = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
// 數(shù)組有序標(biāo)記位席纽，默認(rèn)為true,假設(shè)是有序的，發(fā)生交換就會(huì)標(biāo)記為無(wú)序
boolean isSorted = true;
for (int j = 0; j < arrBoundary; j++) {
if (array[j] > array[j + 1]) {
array[j + 1] ^= array[j];
array[j] ^= array[j + 1];
array[j + 1] ^= array[j];
// 因?yàn)橛性剡M(jìn)行交換撞蚕，數(shù)組不是有序的润梯，標(biāo)記為false
isSorted = false;
// 最后一次交換元素的位置
lastSwapIndex = j;
}
}
// 把最后一次交換元素的位置賦值給無(wú)序數(shù)組的邊界
arrBoundary = lastSwapIndex;
// 說(shuō)明上面內(nèi)層for循環(huán)中，沒(méi)有交換任何元素甥厦，直接跳出外層循環(huán)
if (isSorted) {
break;
}
}
}
