2022年2022年快速排序算法 .pdf

《2022年2022年快速排序算法 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年快速排序算法 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编辑词条 快速排序算法目录基本思想算法过程Pascal 的qsort标程C语言的 Qsort 程序Jave 中的Qsort编辑本段基本思想快速排序对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。编辑本段算法过程设要排序的数组是A1 AN ，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1

2、）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即 X：=A1 ； 3）、从 J开始向前搜索，即由后开始向前搜索（J：=J-1 ），找到第一个小于 X的值，两者交换； 4）、从 I开始向后搜索，即由前开始向后搜索（I：=I+1 ），找到第一个大于 X的值，两者交换； 5）、重复第 3、4步，直到 I=J ；例如：待排序的数组A的值分别是：（初始关键数据X：=49 ） A1 A2 A3 A4 A5 A6 A7： 49 38 65 97 76 13 27进行第一次交换后： 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开

3、始找)进行第二次交换后： 27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找X的值， 6549, 两者交换，此时I：=3 )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 进行第三次交换后： 27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找进行第四次交换后： 27 38 13 49 76 97 65( 按照算法的第四步从前面开始找大于X的值， 9749, 两

4、者交换，此时 J：=4 )此时再执行第三步的时候就发现I=J ，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于 49的数全部在 49 的后面，所以小于49 的数全部在 49的前面。快速排序就是递归调用此过程 在以 49 为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：初始状态 49 38 65 97 76 13 27进行一次快速排序之后划分为 27 38 13 49 76 97 65分别

5、对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序 76 97 65 经第三步和第四步交换后变成 65 76 97 完成排序编辑本段Pascal 的qsort 标程 free Pascal 自带的 qsort 标程 : program quicksort; const $ifndef MACOS max = 100000; $else max = 1000; Actually it works with 100000 also, but thatmight lead problems occacionally. $endif type tlist

6、 = array1.max of longint; var data : tlist; procedure qsort(var a : tlist); procedure sort(l,r: longint); var名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - i,j,x,y: longint; begin i:=l; j:=r; x:=a(l+r) div 2; repeat while a x do inc(i); wh

7、ile xj) then begin y:=a; a:=aj; aj:=y; inc(i); j:=j-1; end; until ij; if lj then sort(l,j); if ir then sort(i,r); end; begin sort(1,max); end; var i : longint; begin write(Creating ,Max, random numbers between 1 and500000); randomize; for i:=1 to max do data:=random(500000); writeln;名师资料总结 - - -精品资料

8、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - writeln(Sorting.); qsort(data); writeln; for i:=1 to max do begin write(data:7); if (i mod 10)=0 then writeln; end; end.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -