【每日阅读】2020年6月12日-快排中的partition函数

链接

https://blog.csdn.net/gaopu12345/article/details/50849360

文章截图

简评

这其实是我当初学习快排时写下的一篇博客。

今天一个同事找我聊聊快排的partition函数怎么写,当时脑袋一懵,然后我俩慢慢聊着聊着,我回忆起了“挖坑填埋法”。这个算法很简单直观,就是一个基准数(数组第一个数),两个指针,一个从左往右找大于基准数的数,另一个指针从后往前找小于基准数的数。开始基准数位置(数组第一个位置)算是一个坑,从后往前找小于基准数的,找到了就放到坑里,此时新的坑就产生了(移到第一个坑里后空出来的坑),然后从前往后找大于基准数的数,如此循环,直到左右指针相遇,最后一个坑放基准数。此时partition算法就完成了。

而今天引用的博文里面的算法,是把数组最后一位数当作基准数,然后有一个指针专门指向比基准数大的,等着和比基准数小的数交换。把小于基准数的和前面大于基准数的数互换,最后结果就是左右两边分别是左边比基准数小,右边比基准数大。

挖坑法容易想到是因为“挖坑”这个形象的比喻,后一个我没想到怎么比喻方便记忆。。

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/1924

(0)
geekgaogeekgao博主
上一篇 2020年6月12日
下一篇 2020年6月14日

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

GitHub
分享本页
返回顶部

Warning: error_log(/usr/local/lighthouse/softwares/wordpress/wp-content/plugins/spider-analyser/#log/log-2913.txt): failed to open stream: No such file or directory in /usr/local/lighthouse/softwares/wordpress/wp-content/plugins/spider-analyser/spider.class.php on line 2900