這篇文章講的是 :雞尾酒排序
雞尾酒排序是冒泡排序的再更新版,冒泡排序可以參考我的部落格:https://blog.csdn.net/kai123wen/article/details/98031335
冒泡排序最終本來也很好了,但是既然是“冒泡”,就說明每次排序的方向是單向的,單向就會帶來一個問題:如數列 2 3 4 5 1,1 是最小的,但是1在最後,如果我們的冒泡的方向是從左向右,那麼要比較的次數會很多,大家可以試試,我的部落格中冒泡排序的三個版本對于這種的數列比較次數是一樣的,都是n(n-1)/2,n代表數列長度。
怎樣解決這個問題呢?顯然問題出在冒泡的“單向性”上。那麼要解決我們就來個雙向的:**由左到右比較後,再由右到左比較。**這樣在由右到左的比較中,程式就能将 1 轉移到數列開頭。
看代碼:
public void jiweijiuSort(int array[]) {
int count = 0;
int temp = 0;
boolean sorted = false;
for (int i = 0; i < array.length / 2; i++) {
sorted = false;
for (int j = i; j < array.length - i - 1; j++) {
count++;
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
sorted = true;
}
}
for (int j = array.length - i - 1; j > i; j--) {
count++;
if (array[j] < array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
sorted = true;
}
}
if (sorted == false) {
break;
}
}
System.out.println("執行次數:" + count);
}
代碼和冒泡排序的代碼類似,冒泡排序的代碼可以i參考我上面貼的部落格 但是雞尾酒排序代碼中有幾個重點:
- 這裡 i 是要小于 array.length / 2 的,其實這裡很簡單,雞尾酒排序内循環是正向比較一輪,再反向比較一輪,這樣外層循環一次,等于傳統的冒泡排序循環兩次
-
不禁要問,這裡 j 怎麼從 i 開始 了?答:因為現在是正向和反向比較,正向比較會使得數列結尾 i+1 個元素有序,而反向比較會使得數列開頭的 i + 1個元素有序,既然開頭 i + 1 個元素有序了,那麼就沒有必要再從0開始啦!
另一個内層循環是一樣的道理