C语言快速排序算法

C语言快速排序算法

ID:40534257

大小:22.07 KB

页数:5页

时间:2019-08-04

C语言快速排序算法_第1页
C语言快速排序算法_第2页
C语言快速排序算法_第3页
C语言快速排序算法_第4页
C语言快速排序算法_第5页
资源描述:

《C语言快速排序算法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、C语言快速排序算法(一)概述  快速排序(QuickSort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2),但由于平均运行时间为O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在一般情况下是最实用的排序方法之一。  快速排序被认为是当前最优秀的内部排序方法。(二)实现  快速排序的实现基于分治法,具体分为三个步骤。假设待排序的序列为L[m..n]。  分解:序列L[m..n]被划分成两个可能为空的子序列L[m..pivot-1]和L[pivot+1.

2、.n],使L[m..pivot-1]的每个元素均小于或等于L[pivot],同时L[pivot+1..n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元(也称为枢轴、支点)。  解决:通过递归调用快速排序,对子序列L[m..pivot-1]和L[pivot+1..r]排序。  合并:由于两个子序列是就地排序的,所以对它们的合并不需要操作,整个序列L[m..n]已排好序。(三)性质  内部排序  快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。  比较排序  快速排序确定元素位置的

3、方法基于元素之间关键字大小的比较。  所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明,请参考有关算法的书籍,例如《算法导论》(第一版)第8章(第二版在第七章QuickSort)。  在理想情况下,能严格地达到O(nlgn)的下界。一般情况下,快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。  不稳定性  快速排序是一种不稳定的排序方法。简单地说,元素a1,a2的关键字有a1.key=a2.key,则不稳定的排序方法不能保证a1,a2在排序后维持原来的位置先后关系。  原地排序  在排序的

4、具体操作过程中,除去程序运行实现的空间消费(例如递归栈),快速排序算法只需消耗确定数量的空间(即S(1),常数级空间)。  这个性质的意义,在于在内存空间受到限制的系统(例如MCU)中,快速排序也能够很好地工作。(四)时空复杂度  快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。  而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中

5、,快速排序的平均时间复杂度为O(nlogn)。  快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。  但需要注意递归栈上需要花费最少logn最多n的空间。(五)随机化算法  快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能

6、性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”  随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。(六)减少递归栈使用的优化  快速排序的实现需要消耗递归栈的空间,而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时,对系统栈的频繁存取会影响到排序的效

7、率。  一种常见的办法是设置一个阈值,在每次递归求解中,如果元素总数不足这个阈值,则放弃快速排序,调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取,节省了时间的消费。  一般的经验表明,阈值取一个较小的值,排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案:阈值T=10,排序算法用选择排序。  阈值不要太大,否则省下的存取系统栈的时间,将会被简单排序算法较多的时间花费所抵消。  另一个可以参考的方法,是自行建栈模拟递归过程。但实际经验表明,收效明显不如设置阈值。(七)C例程  以下是C语

8、言权威《TheCProgrammingLanguage》中的例程,在这个例程中,对于数组v的left到right号元素以递增顺序排序。  //Qsort.cbyTydus.  #include  intarr[]={

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。