2022年2022年快速排序算法及源代码 2.pdf

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

1、快速排序算法及源代码（C语言) 2009年 11 月 01 日 星期日 11:40 快速排序（Quicksort ）是对冒泡排序的一种改进。由C. A. R. Hoare在 1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行， 以此达到整个数据变成有序序列。假设要排序的数组是A1 AN，首先任意选取一个数据（通常选用第一个数据）作为关键数据， 然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法

2、是：1）、设置两个变量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 页，共 5 页 - - - - - - - - - 后： 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

5、65 分别对前后两部分进行快速排序 27 结束结束 49 65 76 49 结束结束图 6 快速排序全过程1）、设有 N （假设 N=10 ）个数，存放在S数组中；2）、在 S1。N中任取一个元素作为比较基准，例如取T=S1 ，起目的就是在定出 T 应在排序结果中的位置K，这个 K的位置在： S1。K-1=SK=SK+1.N，即在 SK 以前的数都小于 SK ，在 SK 以后的数都大于 SK ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - -

6、 - - - 3）、利用分治思想（即大化小的策略）可进一步对S1。K-1 和 SK+1。N两组数据再进行快速排序直到分组对象只有一个数据为止。如具体数据如下，那么第一躺快速排序的过程是：数组下标：1 2 3 4 5 6 7 8 9 10 45 36 18 53 72 30 48 93 15 36 I J （1） 36 36 18 53 72 30 48 93 15 45 （2） 36 36 18 45 72 30 48 93 15 53 （3） 36 36 18 15 72 30 48 93 45 53 （4） 36 36 18 15 45 30 48 93 72 53 （5） 36 36 1

7、8 15 30 45 48 93 72 53 通过一躺排序将 45 放到应该放的位置K， 这里 K=6， 那么再对 S1。 。5 和 S6。10 分别进行快速排序。这是完整的代码，经本人测试通过。#include #define LENGTH 100 /*数组最大存放量 */ void qsort(long int shuju,short int shangbiao,short int xiabiao); void main() short int i,n; long int shujuLENGTH; printf(How many numbers?n); /*要输入多少个数 */ 名师资料总

8、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - scanf(%d,&n); getchar(); /*干掉个多事的回车符 */ printf(input the numbers:n); for(i=0;in;i+) scanf(%d,&shujui); qsort(shuju,0,n-1); /*调用递归排序 */ printf(result:n); for(i=0;in;i+) printf(%d ,shujui); putchar(n

9、); getchar(); getchar(); /*暂停看结果 */ void qsort(long int shuju,short int shangbiao,short int xiabiao) short int i=shangbiao,j=xiabiao; /*i和 j 用来确定还需要判断排序的范围上下标 */ short int shu=i; /*记录基准点 */ long int zhongjie; if(shangbiaoxiabiao)/*判断递归的终点如果只剩一个数了, 不需要再排了 */ while(ishu;j-) /*对基准数右边扫描 */ if(shujujshuj

10、ushu) /*如果右边的数有比基准数小的*/ zhongjie=shujuj; shujuj=shujushu; /*进行交换 */ shujushu=zhongjie; shu=j; /*确定交换后的基准数 */ break; /*跳出循环 */ i+; /*往右推 */ for(;ishujushu)/*如果左边有比基准数大的 */ zhongjie=shujui; shujui=shujushu; /*交换*/ shujushu=zhongjie; shu=i; /*交换后的基准点 */ break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

11、 - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - j-; /*往左推*/ /*执行完后 , 比基准点小的都在左边 , 比基准点大的都在右边了 */ qsort(shuju,shangbiao,shu-1); /*对左边比基准点小的再次进行排序（递归调用） */ qsort(shuju,shu+1,xiabiao); /*对右边比基准点大的再次执行上面的排序方法（递归调用） */ /*直到只剩下要排序一个数为止, 此时整个数组已经排序好了*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -