《快速排序算法及源代码》由会员分享，可在线阅读，更多相关《快速排序算法及源代码（5页珍藏版）》请在金锄头文库上搜索。
1、快速排序算法及源代码（C语言）2009年 11月 01日 星期日 11:40快速排序（Quicksort ）是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小， 然后再按此方法对这 两部分数据分别进行快速排序， 整个排序过程可以递归进行， 以此达到整个数据 变成有序序列。假设要排序的数组是A1AN，首先任意选取一个数据（通常选用第一个 数据） 作为关键数据， 然后将所有比它的数都放到它前面， 所有比它大的数都放 到它后面，这个过程称为一躺快速排序。一躺快速
2、排序的算法是：1）、设置两个变量I、J,排序开始的时候I : =1, J: =N;2）以第一个数组元素作为关键数据，赋值给 X,即X: =A1;3） 、从J开始向前搜索，即由后开始向前搜索（J: =J-1 ），找到第一个小于X 的值，两者交换；4） 、从I开始向后搜索，即由前开始向后搜索（I : =1+1），找到第一个大于X 的值，两者交换；5）、重复第 3、 4 步，直到 I=J ；例如：待排序的数组A的值分别是：（初始关键数据 X: =49）A1A2A3A4A5A6A749386597761327进行第一次交换后:27386597761349（ 按照算法的第三步从后面开始找进行第二次交换后
3、:27384997761365（ 按照算法的第四步从前面开始找X的值，6549,两者交换，此时I : =3 ）进行第三次交换 后： 27 38 13 97 76 4965（ 按照算法的第五步将又一次执行算法的第三步从后开始找进行第四次交换后： 27 38 13 49 76 9765（按照算法的第四步从前面开始找大于 X的值，9749,两者交换，此时J : =4 ）此时再执行第三不的时候就发现 I=J ，从而结束一躺快速排序，那么经过一躺快 速排序之后的结果是:27381349769765，即所以大于 49的数全部在 49的后面，所以小于 49的数全部在 49的前面。快速排序就是递归调用此过程在
4、以 49为中点分割这个数据序列，分别对前 面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排 序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组 A的快速排序的全过程如图 6 所示:初始状态49386597761327进行一次快速排序之后划分为 27381349 769765分别对前后两部分进行快速排序 27结束结束 49 65 7649结束结束图 6 快速排序全过程1）、设有N （假设N=10）个数，存放在S数组中；2）、在S1。N中任取一个元素作为比较基准，例如取 T=S1，起目的就是 在定出T应在排序结果中的位置 K,这个K的位置在：S1 00K-1v=S
5、Kv=SK+1.N，即在SK以前的数都小于SK，在SK以后的数都 大于 SK ；3）、利用分治思想（即大化小的策略）可进一步对S1。K-1和SK+1。N两组数据再进行快速排序直到分组对象只有一个数据为止。如具体数据如下，那么第一躺快速排序的过程是： 数组下标：1234567891045361853723048931536（1）36361853723048931545（ 2）36361845723048931553（ 3）36361815723048934553（ 4）36361815453048937253（ 5）36361815304548937253通过一躺排序将45放到应该放的位置K，这
6、里K=6,那么再对S1 o 0 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）; /* 要输入多少个数 */scanf(%d,&n);getchar(); /* 干掉个多事的回车符 */ printf(input the n
7、umbers: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);getchar();getchar(); /* 暂停看结果 */void qsort(long int shuju,short int shangbiao,short int xiabiao)short int i=shangbiao,j=xiabiao; /*i和 j 用来确定还需要判断排序的范围上下标 */short
8、 int shu=i; /*记录基准点 */long int zhongjie;if(shangbiaoxiabiao)/* 判断递归的终点如果只剩一个数了 , 不需要再排了 */ while(ishu;j-) /*对基准数右边扫描 */if(shujujshujushu) /* 如果右边的数有比基准数小的 */ zhongjie=shujuj; shujuj=shujushu; /* 进行交换 */ shujushu=zhongjie;shu=j; /* 确定交换后的基准数 */ break; /* 跳出循环 */i+; /*往右推 */for(;ishujushu)/* 如果左边有比基准数大的 */ zhongjie=shujui; shujui=shujushu; /*交换 */shujushu=zhongjie;shu=i; /*交换后的基准点 */break;j-; /*往左推 */* 执行完后 , 比基准点小的都在左边 , 比基准点大的都在右边了 */ qsort(shuju,shangbiao,shu-1); /*对左边比基准点小的再次进行排序(递归调用) */qsort(shuju,shu+1,xiabiao); /* 对右边比基准点大的再次执行上面的 排序方法(递归调用) */ /* 直到只剩下要排序一个数为止 , 此时整个数组已经排序好了 */
