快速排序:是冒泡排序的改进。
基本思想:通过一趟排序把整个序列分为两部分,一部分的所有数比另一部分的所有数都小,再递归的处理这两部分,直到排好序。
实例:
上面是一趟排序后的结果,275,087,154,061,426,170都要小于503. 相同897,653,908,512,612,677,765,703都大于503;接到对275,087,154,061,426,170;897,653,908,512,612,677,765,703两部分进行相同的操作。
具体实现:
1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与A[I]交换;
4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与A[J]交换;
5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)
代码实现:
void QuickSort(SeqList R,int low,int high)
{ //对R[low..high]快速排序
int pivotpos; //划分后的基准记录的位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(R,low,high); //对R[low..high]做划分
QuickSort(R,low,pivotpos-1); //对左区间递归排序
QuickSort(R,pivotpos+1,high); //对右区间递归排序
}
}
分享到:
相关推荐
肖 洲 -《数据结构的在程序设计中的应用》 谢 婧 -《规模化问题的解题策略》 徐 串 -《论程序的调试技巧》 徐 静 -《图论模型的建立与转化》 杨江明 -《论数学策略在信息学问题中的应用》 杨 培 -《非最优化...
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由...
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 本书深入浅出,...
该书是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(The Art Of Computer Programming)相媲美。 《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、...
该书是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(The Art Of Computer Programming)相媲美。 《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、...
原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由Thomas H....
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由...
《PowerPoint 2007宝典》全面并且深入浅出地介绍了PowerPoint最有用的高级技能,还提供了很多实用的小技巧,教您快速成为制作和演示文稿方面的专家。PowerPoint是最普及的和非常受欢迎的制作演示文稿的工具,而...
《PowerPoint 2007宝典》全面并且深入浅出地介绍了PowerPoint最有用的高级技能,还提供了很多实用的小技巧,教您快速成为制作和演示文稿方面的专家。PowerPoint是最普及的和非常受欢迎的制作演示文稿的工具,而...
《计算机基础操作》课程标准 一、教学对象: 适用于全院各专业学生。 二、课程性质: 本课程为全院各专业学生的必修课。本课程旨在培养学生具有文字录入、OFFICE操 作及网络应用能力。通过本课程内容的学习,为学院...
A、高级语言编译程序 B、生物病毒 C、操作系统 D、计算机程序 4.把高级语言的源程序变为目标程序要经过 ___D__ 。 A、编译 B、编辑 C、汇编 D、解释 5.声音与视频信息在计算机内是以 ___D___ 表示的。 A、模拟信息 B...