实验一排序算法的设计与实现剖析.docx

文档介绍：学生实验报告
学院：软件与通信工程学院课程名称：算法分析与设计
专业班级：
软件144班
姓名：刘洋学号：0144119
学生实验报告
学生姓名
刘洋
学号0144119
同组人
实验项目
排序算法的设542第一趟循环72657888542第一次交换67257888542第二趟循环67257888542第二次交换72657888542反转交换67257888542
这就是依靠轴值，将数组分成两部分的实例（特殊情况下，可能为一部分，其中42是轴值）。对分成的两部分数组，分别尽心类似的操作，便可得符合要求的结果。
快速排序的函数模块；voidqsort(int*array,intl,intr){if(r<=l)return;
intpivotIndex=l+rand()%(r-l+1);//随机选定轴值swap1(array,pivotIndex,r);//将选定的轴值放到每段数组的最后intk=partition(array,l-1,r,array[r]);//依靠轴值，将数组分//
成两部分
swap1(array,k,r);//qsort(array,l,k-1);//将轴值放到正确的位置上递归调用，对数组左右两部分进行排序
qsort(array,k+1,r);}
/*将大于轴值的放右边，小于轴值的放左边intpartition(int*array,intl,intr,constintpivot){算法实现*/
do{while(array[++l]<pivot);while((r!=0)&&(array[--r]>pivot));
swap1(array,l,r);}while(l<r);swap1(array,l,r);returnl;}实验源码：
#include<iostream>#include<ctime>usingnamespacestd;产生n个随机数，存储到数组int*crtArray(int&size){intn;cout<<"n=";cin>>n;设置随机种子srand(time(NULL));int*intArray=newint[n];size=n;cout<<"原始序列："<<endl;for(inti=0;i<n;i++){intArray[i]=rand()%10;if(intArray[i]==0){i--;continue;}cout<<intArray[i]<<"";}cout<<endl;returnintArray;}交换数组中的两个值voidswap1(int*array,int&a,int&b){inttemp=array[a];array[a]=array[b];array[b]=temp;}对指定的数组部分进行分割
intpartition(int*array,intl,intr,constintpivot){do{while(array[++l]<pivot);while((r!=0)&&(array[--r]>=pivot));swap1(array,l,r);}while(l<r);swap1(array,l,r);returnl;}快速排序的实现部分voidqsort(int*array,intl,intr){if(r<=l