動畫:什麼是雞尾酒排序和地精排序?

收藏待读

動畫:什麼是雞尾酒排序和地精排序?

奇葩排序第二彈:)

從冒泡排序開始

先來看回顧一下冒泡排序的思想和原理。

冒泡排序的思想

冒泡排序的每一個元素都可以像小氣泡一樣,根據自身大小,一點一點向著數組的一側移動。

冒泡排序算法的原理

  • 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。

  • 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。

  • 針對所有的元素重複以上的步驟,除了最後一個。

  • 持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。

一般情況下,可以通過下面的動畫理解冒泡排序。

動畫:什麼是雞尾酒排序和地精排序? 冒泡排序

現在我們來看一組特殊數據如果使用冒泡排序會怎麼樣。

將無序數列:2,3,4,5,6,7,8,1,使用冒泡排序使其從小到大排序。

動畫:什麼是雞尾酒排序和地精排序? 無序數列

進行逐步分析:

  1. 第一輪操作( 8 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第一輪操作( 8 和 1 交換 )
  2. 第二輪操作( 7 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第二輪操作( 7 和 1 交換 )
  3. 第三輪操作( 6 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第三輪操作( 6 和 1 交換 )
  4. 第四輪操作( 5 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第四輪操作( 5 和 1 交換 )
  5. 第五輪操作( 4 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第五輪操作( 4 和 1 交換 )
  6. 第六輪操作( 3 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第六輪操作( 3 和 1 交換 )
  7. 第七輪操作( 2 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第七輪操作( 2 和 1 交換 )

仔細觀察上面的這組無序數列,實際上只有 1 的位置不在該在的位置,而 2 ,3 ,4 ,5 ,6 ,7 ,8 都已經有序了,結果使用冒泡排序,需要 折騰 7 次 才能將 1 歸位。

雞尾酒排序

動畫:什麼是雞尾酒排序和地精排序? 雞尾酒排序

雞尾酒排序,也就是定向冒泡排序,雞尾酒攪拌排序,攪拌排序(也可以視作選擇排序的一種變形),漣漪排序,來回排序或快樂小時排序,是冒泡排序的一種變形。

此算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。

排序過程:

  • 先對數組從左到右進行冒泡排序(升序),則最大的元素去到最右端
  • 再對數組從右到左進行冒泡排序(降序),則最小的元素去到最左端
  • 以此類推,依次改變冒泡的方向,並不斷縮小未排序元素的範圍,直到最後一個元素結束

Show Me The Animation

  1. 第一輪操作( 8 和 1 交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第一輪操作( 8 和 1 交換 )
  2. 第二輪操作 ( 從序列右邊開始遍歷 )
    動畫:什麼是雞尾酒排序和地精排序? 第二輪操作 ( 從序列右邊開始遍歷 )
  3. 第三輪操作 ( 從左向右比較和交換 )
    動畫:什麼是雞尾酒排序和地精排序? 第三輪操作 ( 從左向右比較和交換 )
    在這一輪操作中,沒有元素位置交換,證明已經有序,排序結束。

對比 冒泡排序 ,雞尾酒排序只需要 3 輪操作就可以完成排序。

地精排序

Gnome 排序(地精排序),起初由 Hamid Sarbazi-Azad 於 2000 年提出,並被稱為 stupid 排序,後來被 Dick Grune 描述並命名為 「地精排序」 。

地精排序和插入排序類似,除了移動一個元素到最終的位置,是通過交換一系列的元素實現,就像冒泡排序一樣。概念上十分簡單,不需要嵌套循環。時間複雜度為O(n2),但是如果初始數列基本有序,時間複雜度將降為O(n)。實際上 Gnome 算法可以和插入排序算法一樣快。平均運行時間為O(n^2)。

將無序數列:6,2,4,1,5,使用地精排序使其從小到大排序。

通過設計標識 i = 0 ,然後從頭開始判斷,什麼時候 ( i < 4 ) 不成立,什麼時候排序結束。

這裡的核心點就是 如何控制 i 的值

第一輪操作「i = 0」

動畫:什麼是雞尾酒排序和地精排序?

先讓 i 自增 1 ,達到值為 1 才開始比較 :

交換前 [ 6 2 4 1 ] 『 i = 0

交換後 [ 6 2 4 1 ] 『 i = 1

第二輪操作「i = 1」

動畫:什麼是雞尾酒排序和地精排序?

比較 6 和 2 ,發生交換, 只要發生交換 i 就減 1

交換前 [ 6 2 4 1 ]『 i = 1 』

交換後 [ 2 6 4 1 ]『 i = 0 』

第三輪操作「i = 0」

動畫:什麼是雞尾酒排序和地精排序?

i 變成 0 了,啥也不幹,自增變成 1 再說。

交換前 [ 2 6 4 1 ]『 i = 0 』

交換後 [ 2 6 4 1 ]『 i = 1 』

第四輪操作「i = 1」

動畫:什麼是雞尾酒排序和地精排序?

比較 2 和 6 ,不交換, 只要不要換就自增 1

交換前 [ 2 6 4 1 ]『 i = 1 』

交換後 [ 2 6 4 1 ]『 i = 2 』

第五輪操作「i = 2」

動畫:什麼是雞尾酒排序和地精排序?

比較 6 和 4 ,發生交換, 只要發生交換 i 就減 1

交換前 [ 2 6 4 1 ]『 i = 2 』

交換後 [ 2 4 6 1 ]『 i = 1 』

第六輪操作「i = 1」

動畫:什麼是雞尾酒排序和地精排序?

比較 2 和 4 ,不交換, 只要不要換就自增 1

交換前 [ 2 6 4 1 ]『 i = 1 』

交換後 [ 2 4 6 1 ]『 i = 2 』

第七輪操作「i = 2」

動畫:什麼是雞尾酒排序和地精排序?

比較 4 和 6 ,不交換, 只要不要換就自增 1

交換前 [ 2 4 6 1 ]『 i = 2 』

交換後 [ 2 4 6 1 ]『 i = 3 』

第八輪操作「i = 3」

動畫:什麼是雞尾酒排序和地精排序?

比較 6 和 1 ,發生交換, 只要發生交換 i 就減 1

交換前 [ 2 4 6 1 ]『 i = 3 』

交換後 [ 2 4 1 6 ]『 i = 2 』

第九輪操作「i = 2」

動畫:什麼是雞尾酒排序和地精排序?

比較 4 和 1 ,發生交換, 只要發生交換 i 就減 1

交換前 [ 2 4 1 6 ]『 i = 2 』

交換後 [ 2 1 4 6 ]『 i = 1 』

第十輪操作「i = 1」

動畫:什麼是雞尾酒排序和地精排序?

比較 2 和 1 ,發生交換, 只要發生交換 i 就減 1

交換前 [ 2 1 4 6 ]『 i = 1 』

交換後 [ 1 2 4 6 ]『 i = 0 』

第十一輪操作「i = 0」

動畫:什麼是雞尾酒排序和地精排序?

啥也不幹,先讓 i 自增1,達到值為 1 才開始真正的比較。

『 i = 1 』時,比較 1 和 2 ,不交換,只要不交換就自增 1 。

『 i = 2 』時,比較 2 和 4 ,不交換,只要不交換就自增 1 。

『 i = 3 』時,比較 4 和 6 ,不交換,只要不交換就自增 1 。

『 i = 4 』時,表達式 ( i < n ) 不成立,排序結束。

順序輸出為 [ 1 2 4 6 ]。

地精排序算法代碼

 1template 
 2void gnome_sort_1(T data[], int n, bool comparator(T, T)){
 3    int i = 1;
 4    while (i  0 && comparator(data[i], data[i-1])){
 6           swap(data[i], data[i-1]);
 7           i--;
 8       }else{
 9           i++;
10       }
11    }
12}

這種地精排序算法還有很多優化的空間,這裡小吳就不展開來講了。

End

雞尾酒排序和地精排序雖然被程序員小吳歸為奇葩排序一類,但是它們還是有一定的使用場景的。

  • 在「大部分元素有序」的情況下,使用雞尾酒排序可以減少排序的回合數。
  • 地精排序最著名的特點是代碼只有一層循環,在「大部分元素有序」的情況下,可以減少排序回合數。

今日問題

除了雞尾酒排序和地精排序以外,你還知道哪些排序適合用於「大部分元素有序」的序列進行排序?

原文 : 博客園精華區

相關閱讀

免责声明:本文内容来源于博客園-原創精華區,已注明原文出处和链接,文章观点不代表立场,如若侵犯到您的权益,或涉不实谣言,敬请向我们提出检举。