快排的一种简易写法

   虽然简易二字,因人而异。不过,写一个快排确实并不需要过20行,超过几分钟时间的代码。面试的时候,面试官确实会经常问起快排什么的。但是,大家上的入门课基本是使用严蔚敏老奶奶的教材,上面对于快排的讲解我是不敢恭维的。至少上面关于快排的写法,我是写过好几次之后都是没掌握好的。后面,应该是看K&R的c语言程序设计时候,发现一种更简便的partion方法,但是当时我也没怎么掌握。这一切直到,寒假认真阅读算法导论的时候。

   不用算法牛人,算法学得好或者对快排理解深刻的,不用把这篇文章看完了,相信你们都能在10分钟之内写一个正确的快排了。
   废话少说,还是来讲讲如何保证10分钟之内写一个正确的快排,而且以后都能10分钟之内写出来,而不是此刻看了我说的这些胡言之后。
   
   快排的主函数大家都会,现在我给个简易点的样子:
void QuickSort(int* pnA, int nLen)
{
   if (nLen > 1)
   {
         int nP = Partion(pnA, nLen);
         QuickSort(pnA, nP);//排序第nP+1个元素前面的nP个元素
         QuickSort(pnA + nP + 1, nLen - nP - 1);//排序第nP+1个元素后面的元素
   }
}

那么现在就剩下Partion函数了。
我记得严蔚敏书上的写法中Partion 函数里面是有几个循环的。而且即使大概写出来了,也很难处理正确边界。
现在,我要说的就是算法导论上,作为教材内容出现的Partion函数。还是看代码吧。
int Partion(int* pnA, int nLen)
{
   //这里选择最后一个元素作为轴元素
   int i, j;
   for (i = j = 0; i < nLen - 1; ++i)
   {
      if (pnA[i] < pnA[nLen - 1])
      {
            swap(pnA[i], pnA[j];//交换2个数的函数,大家都能写吧,stl中也有
            ++j;
      }
   }
   swap(pnA[j], pnA[nLen - 1]);
   return j;
}

   为了公平起见,上面的代码我都是在blog上面直接敲的,写这10多行代码是绝对用不了10分钟的。主递归函数大家都会写,Partion函数里面只有一个for循环,所以只要明确了for循环的意思,快排的速写就迎刃而解了。其实,按照算导的说法,这个for一直在划分区间。区间[0,j-1]是小于最后一个元素的区间,[j,nLen - 2]是大于等于最后一个元素的区间,所以最后将第nLen-1个元素与第j个元素交换即可,Partion应该返回的值也应该是j
   我不知道大家理解上面那句黑体字的话没,如果理解了,随便写个快排是没问题了。至少,可能的下次面试时候,可以潇洒地写个快排给面试官看看了,虽然这也许并不是什么值得庆幸的事情。


   算法导论里面的快速排序那章后面还有思考题,其中第一个思考题,提出的另外一种叫做Hoare划分的partion写法,意思就和严蔚敏书上的partion函数一致的。理解的关键是,轴元素一直处于被交换中。只要发现了这点,写一两次后,这种partion方法也能掌握好了,不过写起来是循环嵌循环了,没那么舒服。

posted on 2012-03-03 23:26 yx 阅读(2663) 评论(9)  编辑 收藏 引用 所属分类: 排序

评论

# re: 快排的一种简易写法 2012-03-04 14:35 xtao

你好,我看到了你的算法,但是认为有问题,
其中这段
for (i = j = 0; i < nLen - 1; ++i)
{
if (pnA[i] < pnA[nLen - 1])
{
swap(pnA[i], pnA[nLen - 1];//交换2个数的函数,大家都能写吧,stl中也有
++j;
}
}

swap函数是否应该是这样的
swap(pnA[i],pnA[j]);  回复  更多评论   

# re: 快排的一种简易写法 2012-03-04 14:44 远行

这里确实写错了,不好意思,昨晚没发现@xtao
  回复  更多评论   

# re: 快排的一种简易写法 2012-03-04 18:55 sms

你的这个快速排序算法应该没有严蔚敏的快!  回复  更多评论   

# re: 快排的一种简易写法 2012-03-04 19:18 远行

应该差不多吧,基本操作都是交换元素,而且这种写法开始不会动轴元素@sms
  回复  更多评论   

# re: 快排的一种简易写法[未登录] 2012-03-05 13:34 Chipset

你的速度不行,数据结构书上的更垃圾。  回复  更多评论   

# re: 快排的一种简易写法 2012-03-05 15:41 远行

你可以给个更快的partion方法让大家学习下@Chipset  回复  更多评论   

# re: 快排的一种简易写法[未登录] 2012-03-05 17:17 Chipset

需要用到直接插入排序,堆排序和三点取中找支点,然后分割,有点麻烦,到这里去看怎么优化的:
http://www.cppblog.com/Chipset/archive/2011/08/16/153546.html
或者把STLPort代码下载下来去里面找,原理是一样的。
我主页上有常见的14种排序,如果单线程的话,快排是最快的,多线程需要重新设计,太麻烦,最容易实现并行的排序个人认为是归并排序。  回复  更多评论   

# re: 快排的一种简易写法 2012-03-05 19:15 远行

对于怎么并行排序确实没思考过,不过快排很明显的优化是随机选取轴元素,三数取中选轴元素算导也提到过,还有你说的堆排优化快排,应该是只在递归到小数据量时候使用堆排了,不过小数量时候一直听说使用插入速度更快,不过这些都是对快排的优化了,不是我写这篇文章的意思,我是觉得有些人不一定看过算导,也不一定看过STL源码,所以不一定知道很快的写出基本的快排,所以写下这个文章,也当作自己的学习记录,另外你的文章很不错,学习了@Chipset
  回复  更多评论   

# re: 快排的一种简易写法 2013-04-20 22:02 xt

http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html
这个效率比较高  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年9月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜