《快速排序与简单排序性能比较》由会员分享，可在线阅读，更多相关《快速排序与简单排序性能比较（6页珍藏版）》请在金锄头文库上搜索。
1、实验四：快速排序与简单排序性能比较学生姓名：班级：12学号：完成时间：2015.06.26本人郑重声明：本实验的程序代码编写与调试、实验报 告的撰写均由本人独立完成，如被发现抄袭或与其他同学作业雷同，同意取消该实验成绩！声明人：2015.06.26【实验内容】比较快速排序与简单选择排序算法的性能。学生须自行 实现简单选择排序算法，并在不同输入情况下，给出两种排 序算法的比较次数和移动次数。【编程思路】首先，主函数中要求输入数组长度n，然后申请三个长 度为n的动态数组，然后输入数组元素，分别赋给三个数组。 数组p用于快速排序输出比较次数，数组pa用于快速排序 输出交换次数，数组pb用于简单选择排
2、序输出比较和交换 次数。在简单排序过程中，用变量SwapTime记录交换次数, 用变量CompareTime记录比较次数，每次进行比较或交换,相应变量自增。在快速排序过程中，由于用到递归算法，SwapTime和CompareTime均定义为静态变量。【程序代码】1主函数(作业部分)void main()int n;cou t“输入数列的项数：n;int * p二new intn,* pa二new intn,* pb二new intn;cou t 输入要排序的数列：endl;for(int j=O;jpj;paj=pj;pbj=pj;cout快速排序比较的次数:quickSort2(p,0,n-
3、l)endl;cou t 快速排序交换的次数：quickSor tl(pa,O,nT)endl; Easysor t( pb,n);dele te p;dele te pa;dele te pb;p二NULL;pa二NULL;pb二NULL;2快速排序函数(老师提供)int quickSort1(int *p, int low, int high)/返回交换的次数int i, j, t;static int SwapTime = 0;/交换的次数if (low high) /*要排序的元素起止下标，保证小的放在左边，大的放在 右边。这里以下标为low的元素为基准点*/i = low; j =
4、high;t = * (p+low); /*暂存基准点的数*/while (ij) /*循环扫描*/while (it) /*在右边的只要比基准点大仍放在右边 */j-； /*前移一个位置*/if (ij)*(p+i)二*(p+j)； /*上面的循环退出：即出现比基准点小的数, 替换基准点的数*/i+； /*后移一个位置，并以此为基准点*/ SwapTime+;while (ij & *(p+i)二t) /*在左边的只要小于等于基准点仍放在 左边*/ i+；if (ij)*(p+j)二*(p+i)； /*上面的循环退出：即出现比基准点大的数, 放到右边*/j-； /*前移一个位置*/SwapT
5、ime+；* (p+i) = t； /*一遍扫描完后，放到适当位置*/quickSor tl(p,low,i-l); /*对基准点左边的数再执行快速排序*/ quickSortl(p,i+l,high); /*对基准点右边的数再执行快速排序*/return SwapTime; int quickSort2(int *p, int low, int high) /返回比较的次数int i, j, t;static int CompareTime = 0;/比较的次数if(low high) /*要排序的元素起止下标，保证小的放在左边，大的放在 右边。这里以下标为low的元素为基准点*/i = l
6、ow;j = high;t = * (p+low); /*暂存基准点的数*/for (int k =i; k j; k+)CompareTime+;while(i j) /*循环扫描*/while (it) /*在右边的只要比基准点大仍放在右边 */j-; /*前移一个位置*/ /CompareTime+;if (ij)*(p+i)二*(p+j); /*上面的循环退出：即出现比基准点小的数, 替换基准点的数*/i+; /*后移一个位置，并以此为基准点*/while (ij & *(p+i)二t) /*在左边的只要小于等于基准点仍放在 左边*/i+; /*后移一个位置*/CompareTime+
7、;if (ij)*(p+j)二*(p+i); /*上面的循环退出：即出现比基准点大的数, 放到右边*/j-; /*前移一个位置*/* (p+i) = t; /*一遍扫描完后，放到适当位置*/quickSor t2(p,low,i-l); /*对基准点左边的数再执行快速排序*/ quickSort2(p,i+l,high); /*对基准点右边的数再执行快速排序*/return CompareTime;3简单选择排序函数(老师提供)void Easysort(int *p, int n )int SwapTime = 0;/交换的次数int CompareTime = 0;int t 二 p0;f
8、or (int i 二 0; i n1 ; i+)int k;k = i;for (int j = i + 1; j n ;CompareTime+;if (pj pk) k = j; if (i!=k)SwapTime+;t 二 pi; pi = pk; pk = t;printf(“简单排序比较的次数：%d pri ntf (n);printf(简单排序交换的次数：%d pri ntf (n);j+),CompareTime);,SwapTime);【运行结果】 C:User550nyD0cument5Visual Studio 2010PrQjectsWT4DebugWT4.exe输人要排序的数列，64852 12 79 11 3 10 1
