词条信息

admin
admin
超级管理员
词条创建者 发短消息   

相关词条

热门词条

更多>>
什么是端口?到底是做什么的呢?
端口一般指两种,一种是硬件比如路由器或者交换机的插网线的端口,一种是软件的逻辑的概念,比如http的80端口!...
7种进阶方法让你快速测试端口连通性
Ping是Windows、Linux和Unix系统下的一个检查网络连通性的命令工具,对于大部分互联网用户来说很...
电脑开机,总需要按F1,是什么原因造成的?
一.主板掉电这个说法是行业内的叫法了,一般是主板的CMOS电池没电了导致的。也是最常见的一种提示你按F1的提示...
社保降费对个人有什么影响?
下调城镇职工基本养老保险单位缴费比例是政府给企业发的一个大红包,特别是对于企业来说是一个利好,但是对个人来说有...
车辆“出险”对下年保费的影响,到底有多大?
【出险对交强险的影响】【出险对商业险的影响】车辆“出险”对下年保费的影响,到底有多大?这里有必要先提下车险第三...

精选图集

更多>>
简易百科旧版 >>所属分类 >> 程序开发    算法   

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

标签: 程序开发 算法

顶[0] 发表评论(0) 编辑词条

直奔主题,世界上“最漂亮”的排序算法。


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;
  • 当有n个元素时,完美排序由一个常数计算,加上三次递归,每次递归数据量为(2/3)*n;

即,其时间复杂度递归式为:

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

使用《搞定所有时间复杂度计算》中的递归式计算方法,最终得到,完美排序的时间复杂度是O(n^2.7),比O(n^2)的排序都要慢。


完美排序的排序证明,不在文章中展开。从代码直观能感受到,通过swap和三次递归,趋势上,小的元素会往前端走,大的元素会往后端走,直至完成排序。


画外音:快速排序的过程是partition+两次递归,也是小的元素往前端走,大的元素往后端走,直至完成排序。


希望这一分钟,大家有收获。

 

 

附件列表


按字母顺序浏览:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

→我们致力于为广大网民解决所遇到的各种电脑技术问题
 如果您认为本词条还有待完善,请 编辑词条

上一篇人工智能项目成功的8个秘密
下一篇电商搜索算法技术的演进

0
1. 本站部分内容来自互联网,如有任何版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
2. 本站内容仅供参考,如果您需要解决具体问题,建议您咨询相关领域专业人士。
3. 如果您没有找到需要的百科词条,您可以到百科问答提问或创建词条,等待高手解答。

关于本词条的提问

查看全部/我要提问>>