快速排序算法QuickSort

  1. 云栖社区>
  2. 博客>
  3. 正文

快速排序算法QuickSort

嗯哼9925 2017-12-14 14:16:00 浏览460 评论0

摘要:  1.说明 快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。

 1.说明

快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。这边所介绍的第一个快速排序法版本,是在多数的教科书上所提及的版本,因为它最容易理解,也最符合轴心分割与左右进行排序的概念,适合对初学者进行讲解。

2.解法

这边所介绍的快速演算如下:

一趟快速排序的算法是:

  1. 设置两个变量start、end,排序开始的时候:start=1,end=N;
  2. 以第一个数组元素作为关键数据,赋值给pivot,即 pivot=arry[1];
  3. 从end开始向前搜索,即由后开始向前搜索(end--),找到第一个小于pivot的值arry[end],并与arry[start]交换,即swat(arry,start,end);
  4. 从start开始向后搜索,即由前开始向后搜索(start++),找到第一个大于pivot的arry[start],与arry[end]交换,即swat(arry,start,end);
  5. 重复第3、4步,直到 start==end,这个时候arry[start]=arry[end]=pivot,而pivot的位置就是其在整个数组中正确的位置;
  6. 通过递归,将问题规模不断分解。将pivot两边分成两个数组继续求新的pivot,最后解出问题。

3.代码实例

View Code

4.快速排序实例java版本(ps:2011-11-25)

思路和前面的一样,只是使用java来实现。

View Code

 java版本快速排序的改进(ps:2012-5-23)

上面的java版本快速排序写的有点凌乱,下面给出改进版本,本文中的java版本快排并没有想前面c++版本那样使用swap方法。

View Code

PS:2012-5-4对于数组中有相同数情况下的排序修改

如果使用上述方法进行快速排序,数组中有相同的数,那么排序过程中会出现死循环,这里需要修改Partition函数中的while循环的条件,将原来的arry[end]>pivot改为arry[end]>=pivot,arry[start]<pivot改为arry[start]<=pivot。

修改以后的Partition函数如下:

View Code

 

 



本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2011/06/15/2297000.html,如需转载请自行联系原作者


【云栖快讯】阿里巴巴小程序繁星计划,20亿补贴第一弹云应用免费申请,限量从速!  详情请点击

网友评论