索引
链接
https://blog.csdn.net/gaopu12345/article/details/50849360
文章截图
简评
这其实是我当初学习快排时写下的一篇博客。
今天一个同事找我聊聊快排的partition函数怎么写，当时脑袋一懵，然后我俩慢慢聊着聊着，我回忆起了“挖坑填埋法”。这个算法很简单直观，就是一个基准数（数组第一个数），两个指针，一个从左往右找大于基准数的数，另一个指针从后往前找小于基准数的数。开始基准数位置（数组第一个位置）算是一个坑，从后往前找小于基准数的，找到了就放到坑里，此时新的坑就产生了（移到第一个坑里后空出来的坑），然后从前往后找大于基准数的数，如此循环，直到左右指针相遇，最后一个坑放基准数。此时partition算法就完成了。
而今天引用的博文里面的算法，是把数组最后一位数当作基准数，然后有一个指针专门指向比基准数大的，等着和比基准数小的数交换。把小于基准数的和前面大于基准数的数互换，最后结果就是左右两边分别是左边比基准数小，右边比基准数大。
挖坑法容易想到是因为“挖坑”这个形象的比喻，后一个我没想到怎么比喻方便记忆。。
原创文章，作者：geekgao，如若转载，请注明出处：https://www.geekgao.cn/archives/1924
微信 
支付宝 