交换排序的设计与实现.doc

交换排序的设计与实现摘要：该程序主要部分有：（1）随机产生1000个整数（2）实现冒泡排序、双向冒泡排序和快速排序（3）比较各种交换排序的优劣关键字：随机数，冒泡排序，双向冒泡排序，快速排序，交换排序的优劣。 0. 引言：随着现在社会的不断发展，人们的各种社会信息量变的越来越多，数字也随之变的越来越杂乱无序，那么 我们就设计这个程序来进行数字的排序，让我们的信息变的有序方便。1. 需求分析：学校考试成绩排名 排序算法的比较 如何才是最适合你的排序算法 各种信息数字整理排序。2. 数据结构设计void BubbleSort(int a);-冒泡排序算法void DblPPSort(int L,int low,int high);-双向冒泡排序算法int Partition (int i,int j,int r);-第一趟快速排序void QuickSort (int low,int high,int r);-快速排序算法double random(double,double);-产生随机数int k=0;-记录计算次数int aMAX;-记录1000个随机数字3. 算法设计/产生随机数算法-double random(double start, double end) return start+(end-start)*rand()/(RAND_MAX + 1.0);/冒泡排序算法-void BubbleSort(int a)int i,j,t;i=MAX;dofor(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;k=k+3;i-;while(i1);/双向冒泡算法-void DblPPSort(int L,int low,int high) int i,t,fini = 0;while (low high) fini = 1;for (i = low; i Li+1) t = Li;Li = Li+1;Li+1 = t;fini = 0;k=k+3;if (fini) break;high-;for (i = high; i=low; i-)if (Li Li+1) t = Li;Li = Li+1;Li+1 = t;fini = 0;k=k+3;if (fini) break;low+;/一趟快速排序算法-int Partition(int i,int j,int r)int t,x;t=x=ri;while(ij)while(i=x)j-;k+;ri=rj;while(ij&ri=x)i+;k+;rj=ri;k+;ri=t;return i;/快速排序算法-void QuickSort(int low,int high,int r)if(lowhigh)int k_1;k_1=Partition(low,high,r);QuickSort(low,k_1-1,r);QuickSort(k_1+1,high,r);k=k+3;全代码：#include#include#includeusing namespace std;#define MAX 1000void BubbleSort(int a);void DblPPSort(int L,int low,int high);int Partition (int i,int j,int r);void QuickSort (int low,int high,int r);double random(double,double);int k=0;/主程序-int main()int aMAX;int i,s;/产生随机数-srand(unsigned(time(0);for(i=0;iMAX;i+)ai=int(random(0,10000);/选择排序方法-coutwhich do you change(1-冒泡排序，2-双向冒泡排序，3-快速排序算法)s;switch(s)/冒泡排序-case 1:BubbleSort(a);break;/双向冒泡排序算法-case 2:DblPPSort(a,0,MAX-1);break;/快速排序算法- case 3:QuickSort (0,MAX-1,a);break;default:printf(errorn);return 0;for(i=0;iMAX;i+)coutai ;coutendl;cout计算次数：kendl;return 1;/产生随机数算法-double random(double start, double end) return start+(end-start)*rand()/(RAND_MAX + 1.0);/冒泡排序算法-void BubbleSort(int a)int i,j,t;i=MAX;dofor(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;k=k+3;i-;while(i1);/双向冒泡算法-void DblPPSort(int L,int low,int high) int i,t,fini = 0;while (low high) fini = 1;for (i = low; i Li+1) t = Li;Li = Li+1;Li+1 = t;fini = 0;k=k+3;if (fini) break;high-;for (i = high; i=low; i-)if (Li Li+1) t = Li;Li = Li+1;Li+1 = t;fini = 0;k=k+3;if (fini) break;low+;/一趟快速排序算法-int Partition(int i,int j,int r)int t,x;t=x=ri;while(ij)while(i=x)j-;k+;ri=rj;while(ij&ri=x)i+;k+;rj=ri;k+;ri=t;return i;/快速排序算法-void QuickSort(int low,int high,int r)if(lowhigh)int k_1;k_1=Partition(low,high,r);QuickSort(low,k_1-1,r);QuickSort(k_1+1,high,r);k=k+3;4. 程序运行结果选择输入选择1的输出结果选择2的输出结果选择3的输出结果5. 有关技术的讨论1. 对于这次的设计使用的是C+语言。在设计之中运用了C+中的数组结构，选择结构，输入输出，数组在函数中的调用，几种循环语句的运用。2. 在做几个函数使ai在函数的的调用的时候老是出错，后来去查阅了C语言的书中，知道了函数名可以传递数组的头地址在函数中去 从而