驚歎！世界上最漂亮的排序算法！

直奔主題，世界上 “最漂亮” 的排序算法，只有 6 行。

void stooge_sort(int arr[], int i, int j){

_         if (arr[i]>arr[j]) swap(arr[i], arr[j]);_

_         if (i+1>=j) return;_

_         int k=(j-i+1)/3;_

_         stooge_sort(arr, i, j-k);_

_         stooge_sort(arr, i+k, j);_

_         stooge_sort(arr, i, j-k);_

}

《算法導論》習題中的 “完美排序”，由 Howard、Fine 等幾個教授提出，之所以稱爲 “完美排序”，是因爲其代碼實現，優雅、工整、漂亮。

代碼不是很好理解，一步步講解下思路。

首先，排序傳入的參數是待排序的數組 arr[i, j]；

第一步：比較 i 與 j 位置的元素，根據排序規則決定是否進行置換。

畫外音：本栗子，假設排序規則是從小到大。

置換完成後，判斷排序是否結束，當 i 和 j 相鄰時，排序結束。

第二步：將 arr[i, j] 三等分；

畫外音：總元素個數是 j-i+1。

第三步：遞歸 arr 的前 2/3 半區。

第四步：遞歸 arr 的後 2/3 半區。

第五步：遞歸 arr 的前 2/3 半區。

排序結束。

神奇不神奇！！！

再看一遍，印象深刻不？

void stooge_sort(int arr[], int i, int j){

_         if (arr[i]>arr[j]) swap(arr[i], arr[j]); // 比較_

_         if (i+1>=j) return; // 是否結束_

_         int k=(j-i+1)/3; // 三等分_

_         stooge_sort(arr, i, j-k); // 前 2/3 半區_

_         stooge_sort(arr, i+k, j); // 後 2/3 半區_

_         stooge_sort(arr, i, j-k); // 前 2/3 半區_

}

然並卵，除了代碼好看，完美排序毛用沒有，因爲它是一個挺慢的算法。

由代碼很容易看出來：

（1）當只有 1 個元素時，完美排序的時間也是 1；

（2）當有 n 個元素時，完美排序由一個常數計算，加上三次遞歸，每次遞歸數據量爲 (2/3)*n；

即，其時間複雜度遞歸式爲：

T(1) = 1;

T(n) = 3T(2/3n) + 1;

通過遞歸式計算方法，最終得到，完美排序的時間複雜度是 O(n^2.7)，比 O(n^2) 的排序都要慢。

完美排序的排序證明，不在文章中展開。從代碼直觀能感受到，通過 swap 和三次遞歸，趨勢上，小的元素會往前端走，大的元素會往後端走，直至完成排序。

畫外音：快速排序的過程是 partition + 兩次遞歸，也是小的元素往前端走，大的元素往後端走，直至完成排序。

希望這一分鐘，大家有收穫。

只有 6 行的完美排序，學到了嗎？

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/MpxmL9LkY00ug9xVdpN0cQ