开门见山，世界上“最美”的排序算法。voidstooge_sort(intarr[],inti,intj){if(arr[i]>arr[j])swap(arr[i],arr[j]);如果(i+1>=j)返回;intk=(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。第3步：递归arr的前2/3一半。第4步：递归arr的最后2/3一半。第5步：递归arr的前2/3一半。整理完毕。惊艳不惊艳！！！再读一遍，是不是印象深刻？voidstooge_sort(intarr[],inti,intj){if(arr[i]>arr[j])swap(arr[i],arr[j]);//比较if(i+1>=j)return;//是否结束intk=(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；当有n个元素时，完美排序是通过一个常数，加上3次递归，每次递归的数据量为(2/3)*n；即其时间复杂度递推公式为：T(1)=1；T(n)=3T(2/3n)+1；使用《搞定所有时间复杂度计算》中的递归计算方法，最终得到，完美排序的时间复杂度为O(n^2.7)，比O(n^2)的排序要慢。完美排序的排序证明文中不展开。从代码中可以直观的感受到，通过swap和三次递归，趋势是小的元素会往前端走，大的元素会往后端走，直到排序完成。画外音：快速排序的过程是分区+两次递归，小元素往前，大元素往后，直到排序完成。我希望这一分钟，每个人都有所收获。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
