希尔排序和快速排序

实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组数据：单增、单减、乱码等，对它们进行比较分析。#includeiostreamusingnamespacestd;voidShellSort(intr[],intn){inttemp;intd,i,j;d=n/2;while(d0){for(i=d;in;i++){temp=r[i];j=i-d;while(j=0&&tempr[j]){r[j+d]=r[j];j=j-d;}r[j+d]=temp;}d=d/2;}}voidQuickSort(intr[],intfirst,intend){inti,j;i=first;j=end;//初始化inttemp;if(firstend){temp=r[i];while(ij){while(ij&&r[i]=r[j])j--;//右侧扫描r[i]=r[j];//将较小记录交换到前面while(ij&&r[i]=r[j])i++;//左侧扫描r[j]=r[i];//将较大记录交换到后面}r[i]=temp;QuickSort(r,first,i-1);//递归地对左侧子序列进行快速排序QuickSort(r,i+1,end);//递归地对右侧子序列进行快速排序}}voidprint(intr[],intn){for(inti=0;in;i++){coutr[i];}return;}intmain(){intIncrease1[10]={0,1,2,3,4,5,6,7,8,9};intIncrease2[10]={0,1,2,3,4,5,6,7,8,9};intDecline1[10]={9,8,7,6,5,4,3,2,1,0};intDecline2[10]={9,8,7,6,5,4,3,2,1,0};intOutOfOrder1[10]={6,5,1,4,2,3,7,0,9,8};intOutOfOrder2[10]={6,5,1,4,2,3,7,0,9,8};cout应用希尔排序对“单增”进行排序endl;ShellSort(Increase1,10);print(Increase1,10);coutendl;cout应用快速排序对“单增”进行排序endl;QuickSort(Increase2,0,9);print(Increase2,10);coutendl;cout应用希尔排序对“单减”进行排序endl;ShellSort(Decline1,10);print(Decline1,10);coutendl;cout应用快速排序对“单减”进行排序endl;QuickSort(Decline2,0,9);print(Decline2,10);coutendl;cout应用希尔排序对“乱序”进行排序endl;ShellSort(OutOfOrder1,10);print(OutOfOrder1,10);coutendl;cout应用快速排序对“乱序”进行排序endl;QuickSort(OutOfOrder2,0,9);print(OutOfOrder2,10);coutendl;return0;}总结：希尔排序为插入排序中的一种，其时间复杂度在最坏的情况下为O(n^2),在最好的情况下为O(n)；而快速排序为交换排序中的一种，其时间复杂度在最坏的情况下为O(n^2)，在最好的情况下为O(nlog2n)；同时，两者都具有不稳定性。