冒牌排序
基本思想
定義：冒泡排序的英文是bubblesort，它是一種基礎的交換排序
原理：每次比較兩個相鄰的元素，將較大的元素交換至右端 (升序排序)
思路：相鄰的元素兩兩比較，當一個元素大于右側相鄰元素時，交換它們的位置；當一個元素小于或等于右側相鄰元素時，位置不變
案例分析：
1、初始的無序數列 {5,8,6,3,9,2,1,7}，希望對其升序排序
2、按照思路分析：
在經過第一輪交換后，最大的數 9 冒泡到了最右邊
到此為止，所有元素都是有序的了，這就是冒泡排序的整體思路，
3、冒泡排序是一種穩定排序，值相等的元素并不會打亂原本的順序，由于該排序演算法的每一輪都要遍歷所有元素，總共遍歷（元素數量-1）輪，所以平均時間復雜度是O(n2)，
代碼實作
第 1 版代碼
public static void bubbleSort(int[] arr){
if (arr == null || arr.length == 0) return;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 -i; j++) {
int tmp = 0;
//升序排序>,降序排序<
if (arr[j] > arr[j + 1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
使用雙回圈進行排序，外部回圈控制所有的回合，內部回圈實作每一輪的冒泡處理，先進行元素比較，再進行元素交換，
第 2 版代碼
仍以無序數列 {5,8,6,3,9,2,1,7}為例，我們發現在第 6 輪的時候，數列已經是有序了，但冒泡排序仍然進行了第7輪，可以做一個小優化，在外層回圈設定一個哨兵標記isSorted，默認有序，內層回圈如果發生交換，則仍為無序
public static void bubbleSort(int[] arr){
if (arr == null || arr.length == 0) return;
for (int i = 0; i < arr.length - 1; i++) {
//是否已經有序的標記，默認有序
boolean isSorted = true;
for (int j = 0; j < arr.length - 1 -i; j++) {
int tmp = 0;
//升序排序>,降序排序<
if (arr[j] > arr[j + 1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
//發生元素交換，序列仍是無序狀態
isSorted = false;
}
}
if (isSorted){
break;
}
}
}
以isSorted作為標記，如果在本輪排序中，元素有交換，則說明數列無序；如果沒有元素交換，則說明數列已然有序，然后直接跳出大回圈，
第 3 版代碼
以新的無序數列 {3,4,2,1,6,7,8,9}為例，發現前半部分是無序的，而后半部分[6 ,7 ,8 ,9]是有序區間
如果以上面的第2版代碼執行，會發現只有前半部分的比較是有意義的，而后半部分的有序區間的比較是無意義的
怎么避免這種情況？那么可以在每一輪的排序后，記錄下來最后一次元素交換的位置，該位置即為無序數列的邊界，再往后就是有序區
public static void bubbleSort(int[] arr){
if (arr == null || arr.length == 0) return;
//記錄記錄下來最后一次元素交換的位置
int lastExchangeIndex = 0;
//無序數列的邊界，每次比較只需要比到這里為止
int sortBorder = arr.length-1;
for (int i = 0; i < arr.length - 1; i++) {
//是否已經有序的標記，默認有序
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
int tmp = 0;
//升序排序>,降序排序<
if (arr[j] > arr[j + 1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
//發生元素交換，序列仍是無序狀態
isSorted = false;
//更新為最后一次交換元素的位置
lastExchangeIndex = j;
}
}
//更新無序數列的邊界
sortBorder = lastExchangeIndex;
if (isSorted){
break;
}
}
}
在第3版代碼中，sortBorder就是無序數列的邊界，在每一輪排序程序中，處于sortBorder之后的元素就不需要再進行比較了，肯定是有序的
演算法升級
分析
冒泡演算法的每一輪都是從左到右來比較元素，進行單向的位置交換的，是單向的
以新的無序數列 {2,3,4,5,6,7,8,1}為例，按照冒泡排序的演算法，排序程序如下：
事實上，前面的[2，3，4，5，6，7，8]已經是有序了，只有元素1的位置不正確，卻要進行7輪交換，可以將演算法從單向交換改為雙向交換，排序程序就像鐘擺一樣，第1輪從左到右，第2輪從右到左，第3輪再從左到右……，這就是雞尾酒排序.
雞尾酒排序
圖解雞尾酒排序：
經過2輪交換（雖然實際上已經有序，但是流程并沒有結束），進入第3輪交換從左到右進行，1和2比較，位置不變；2和3比較，位置不變；3和4比較，位置不變……6和7比較，位置不變，
沒有元素位置進行交換，證明已經有序，排序結束，
public static void cockTailSort(int[] arr){
if (arr == null || arr.length == 0) return;
// 記錄右側最后一次交換的位置
int lastRightExchangeIndex = 0;
// 記錄左側最后一次交換的位置
int lastLeftExchangeIndex = 0;
// 無序數列的右邊界，每次比較只需要比到這里為止
int rightSortBorder = arr.length - 1;
// 無序數列的左邊界，每次比較只需要比到這里為止
int leftSortBorder = 0;
//i設定為1，代表從第1輪開始
for (int i = 1; i < arr.length; i++) {
boolean isSorted = true;
//奇數，從左到右
if (i % 2 != 0) {
for (int j = leftSortBorder; j < rightSortBorder; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//發生元素交換，序列仍是無序狀態
isSorted = false;
//更新為右側最后一次交換元素的位置
lastRightExchangeIndex = j;
}
}
} else {
//偶數，從右到左
for (int j = rightSortBorder; j > leftSortBorder; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
//發生元素交換，序列仍是無序狀態
isSorted = false;
//更新為左側最后一次交換元素的位置
lastLeftExchangeIndex = j;
}
}
}
//更新無序數列的左邊界
leftSortBorder = lastLeftExchangeIndex;
//更新無序數列的右邊界
rightSortBorder = lastRightExchangeIndex;
if (isSorted) {
break;
}
}
}
優缺點：雞尾酒排序的優點是能夠在特定條件下，減少排序的回合數；而缺點也很明顯，就是代碼量幾乎增加了1倍，
應用場景：無序數列中大部分元素已經有序
參考圖書：《漫畫演算法—小灰的演算法之旅》
歡迎關注我的掘金
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5975.html
標籤：其他