首页 > 编程语言 > 详细

快速排序(quickSort)

时间:2017-08-19 11:45:12      阅读:264      评论:0      收藏:0      [点我收藏+]

快速排序是最经典和常用的排序算法了,已经有不计其数的博客0 0

首先介绍下快速排序的原理。快速排序的基础是基于这样的事实:在一个序列中,如果一个节点前面的所有元素都不大于它,后面的所有元素都不小于它,那么当整个序列达到有序状态时,这个节点的位置保持不变。符合这样条件的节点,称为轴点(pivot)。

于是可以想到,如果能找到这个轴点,那么该点就完成了排序,可以继续在前、后的两个子序列继续寻找轴点。然而,轴点很可能是不存在的,因此,需要我们来构造轴点,即选定一个点,通过调整该点的前后子序列,使之符合轴点的要求。

轴点构造算法如下,总体思想就是,取出一个点作为轴点,然后从起始和末尾元素进行比较,发现不符合的元素,即把它调整到另一侧。当两者相汇时,即均已调整完成,算法即可结束。

 1 int partition(int* A, int lo, int hi)
 2 {
 3     swap(A[lo], A[lo + rand() % (hi - lo + 1)]);//随机选取一个元素
 4     int pivot = A[lo];//作为轴点
 5     while (lo < hi)
 6     {
 7         while (lo < hi)
 8         {
 9             if (pivot < A[hi])
10                 hi--;
11             else
12             {
13                 A[lo++] = A[hi]; break;//遇到相同元素直接转到另一侧
14             }
15         }
16         while (lo < hi)
17         {
18             if (pivot > A[lo])
19                 lo++;
20             else
21             {
22                 A[hi--] = A[lo]; break;//同上
23             }
24         }
25     }
26     A[lo] = pivot;//位置已经调整好,把保存的轴点放回
27     return lo;
28 }

需要注意的一点是,如果判断条件为<=时,如果有很多相同元素,会导致前后子序列划分非常不均衡,递归深度为O(n),总体运行时间高达O(n^2)。因此尽可能让前后序列长度相差较小,碰到相同元素即跳过并从另一边继续。

 

有了轴点构造,快速排序算法就非常容易了。每次轴点构造确定了mi的位置,只需要在前后子序列递归进行这一过程即可。

1 void quickSort(int* A, int lo, int hi)
2 {
3     if (hi - lo < 2) return;//递归基
4     int mi = partition(A, lo, hi - 1);
5     quickSort(A, lo, mi);//递归进行
6     quickSort(A, mi + 1, hi);
7 }

对于快速排序的复杂度,在最坏情况下可能会高达O(n^2),不过在平均效率上,为O(nlogn)。因此,快速排序并不一定真的非常快速0 0

 

另外,轴点构造算法在中位数和选取问题中也有应用,后面会写一篇top-K问题,会详细介绍轴点构造的应用。

快速排序(quickSort)

原文:http://www.cnblogs.com/lustar/p/7395978.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!