比较用快速排序算法和Sherwood快速排序算法进行比较的次数
问题说明输入数据集{ 8、18、2、16、6、4、40、3、5、7、1、9、22、11、13、10、20 }
a .显示输出快速排序的比较次数、Sherwood的比较次数以及排序结果。 注：第一个要素选择最后一个要素。
b .显示奇数项(下标从0开始，)按降序排列，偶数项按升序排列的结果。
代码实现针对主题a显示输出快速排序中的比较次数、Sherwood中的比较次数以及排序结果。 注：第一个要素选择最后一个要素。 代码如下。
//A .显示快速排序中的比较次数、Sherwood中的比较次数以及排序结果。 注：第一个要素选择最后一个要素。 # include iostream # include stdlib.h # include stdio.h # includecstdlib # include time.husingnamespacestd； intpartition(int*arr，int s，int e )； 语音快速排序(int * arr，int s，int e )； voidshuffle_quicksort(int*arr，int s，int e )； intshuffle_partition(int*arr，int a，int b )； 打乱int fle用全局变量fle进行比较的次数int main () { int i； int n=17； inta [ ]={ 8，18，2，16，6，4，40，3，5，7，1，9，22，11，13，10，20 }； //快速排序快速排序(a，0，n-1 )； 快速排序cout '数组时，显示' endl； for(I=0； i n； I ) couta[i] '； coutendl； cout '快速排序洗牌次数： ' fleendl； fle=0； //全局变量清零//shuffle快速排序shuffle_quicksort(a，0，n-1 )； 快速排序cout '数组shuffle时，显示' endl； for(I=0； i n； I ) couta[i] '； coutendl； 计数' shuffle快速排序洗牌次数： ' fleendl； 返回0； }intpartition(int*arr，int l，int r ) ) intx，I，j； x=arr[r]； //基准值i=l； //左指针j=r； //右指针while(ij ) ) while ) Ijarr[I]=x ) /左指针扫描直到找到大于参考值I； fle； if(Ij ) arr[j--]=arr[i]； wile(Ijarr[j]=x ) /右指针小于基准值j----； fle； if(Ij ) arr[i ]=arr[j]； //基准值归位arr[j]=x； 返回j； //voidquicksort(int*arr，int l，int r ) { int tmp； if(lr ) tmp=partition(ARR，l，r )； //递归处理左右排列quicksort(ARR、l、tmp-1 )； //在左半部分对快速排序(arr，tmp 1，r )进行排序； //排序右半部}//随机intshuffle_partition(int*ARR，int l，int r ) {srand ) unsigned (time ) null ) }； /*种子，这里是time，必须包含头文件time.h*/intI=rand(%(r-L1 ) l )。 //先洗牌，然后按顺序s
wap(arr[i],arr[l]); return partition(arr,l,r); }// shuffle快速排序 void shuffle_quicksort(int *arr,int l,int r){ int tmp; if(l<r) { tmp = shuffle_Partition(arr,l,r); shuffle_quicksort(arr,l,tmp-1); shuffle_quicksort(arr,tmp+1,r); }} A题程序输出结果如下： 对于题目B：显示奇数项（下标从0开始，）降序排列，偶数项按升序排列的排列结果。代码如下：
//显示奇数项（下标从0开始，）降序排列，偶数项按升序排列的排列结果 #include <iostream>using namespace std;int Ascend_partition(int *arr,int s,int e);int Decend_partition(int *arr,int s,int e);void Ascend_quicksort(int *arr,int s,int e);void Decend_quicksort(int *arr,int s,int e);int main(){ int i; int n=17; int a[] = { 8,18,2,16,6,4,40,3,5,7,1,9,22,11,13,10,20};int even[50];// 偶索引元素数组(下标从0开始）int odd[50];//奇索引元素数组 int k = 0,l = 0;for(i = 0,k = 0,l = 0;i<n;i++){if (i % 2 == 0) even[k++] = a[i];/*偶索引元素数组*/elseodd[l++] = a[i];/*奇索引元素数组*/} cout<<"偶索引（奇数项）元素数组为：";for (int j = 0;j < (n+1)/2; j++){cout<<even[j]<<" ";} cout<<endl;cout<<"奇索引（偶数项）元素数组为：" ; for (int j = 0;j < n/2; j++){cout<<odd[j]<<" ";} cout<<endl;cout<<"偶索引（奇数项）元素降序排序数组为：";Decend_quicksort(a,0,(n+1)/2);for (int j = 0;j < (n+1)/2; j++){cout<<even[j]<<" ";} cout<<endl;cout<<"奇索引（偶数项）元素升序排序数组为：" ; Ascend_quicksort(a,0,n/2);for (int j = 0;j < n/2; j++){cout<<odd[j]<<" ";} cout<<endl; Ascend_quicksort(a,0,n-1); cout<<"对整个数组升序快速排序后为："<<endl; for(i=0;i < n;i++) cout<<a[i]<<" "; cout<<endl; Decend_quicksort(a,0,n-1); cout<<"对整个数组降序快速排序后为："<<endl; for(i=0;i < n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }//升序排序 int Ascend_partition(int *arr,int l,int r){ int x,i,j; x = arr[r];//基准值 i =l;//左指针 j = r;//右指针 while(i<j) { while( i < j && arr[i] <=x )//左指针遍历，直到找到一个大于基准值的 i++; if(i < j) arr[j--] = arr[i]; while( i < j && arr[j] >= x)//右指针先遍历，直到找到一个小于基准值的 j--; if(i < j) arr[i++] = arr[j]; } //基准值归位 arr[j] = x; return j;}//升序快速排序 void Ascend_quicksort(int *arr,int l,int r){ int tmp; if(l<r) { tmp = Ascend_partition(arr,l,r); //递归处理左右数组 Ascend_quicksort(arr,l,tmp-1);//对左半段排序 Ascend_quicksort(arr,tmp+1,r);//对右半段排序 }}//降序排序 int Decend_partition(int *arr,int l,int r){ int x,i,j; x = arr[r];//基准值 i =l;//左指针 j = r;//右指针 while(i<j) { while( i < j && arr[i] >=x )//左指针遍历，直到找到一个小于基准值的 i++; if(i < j) arr[j--] = arr[i]; while( i < j && arr[j] <= x)//右指针先遍历，直到找到一个大于基准值的 j--; if(i < j) arr[i++] = arr[j]; } //基准值归位 arr[j] = x; return j;}//降序快速排序 void Decend_quicksort(int *arr,int l,int r){ int tmp; if(l<r) { tmp = Decend_partition(arr,l,r); //递归处理左右数组 Decend_quicksort(arr,l,tmp-1);//对左半段排序 Decend_quicksort(arr,tmp+1,r);//对右半段排序 }} B题程序输出结果如下：
以上是最近学的算法与程序设计课的老师布置习题，就写了下。写的不好的地方欢迎小伙伴们指出，互相交流鸭~