首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >惊叹!世界上最漂亮的排序算法!

惊叹!世界上最漂亮的排序算法!

作者头像
架构师之路
发布2021-10-18 15:25:13
5030
发布2021-10-18 15:25:13
举报
文章被收录于专栏:架构师之路架构师之路

直奔主题,世界上“最漂亮”的排序算法,只有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行的完美排序,学到了吗?

画外音:今后面试手写排序不再是问题。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-09-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 架构师之路 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档