希尔排序和快速排序

1、实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组数据：单增、单减、乱码等，对它们进行比较分析。#includeusing namespace std;void ShellSort(int r , int n)int temp;int d,i,j;d=n/2;while(d0)for(i=d;i=0&temprj)rj+d=rj;j=j-d;rj+d=temp;d=d/2;void QuickSort(int r , int first, int end)int i,j;i=first;j=end; /初始化

2、int temp;if(firstend)temp=ri;while (ij) while (ij & ri= rj) j-; /右侧扫描 ri=rj; /将较小记录交换到前面while (ij & ri= rj)i+; /左侧扫描rj=ri; /将较大记录交换到后面ri=temp;QuickSort(r, first, i-1); /递归地对左侧子序列进行快速排序 QuickSort(r, i+1, end); /递归地对右侧子序列进行快速排序void print(int r,int n)for(int i=0;in;i+)coutri;return;int main()int Increa

3、se110=0,1,2,3,4,5,6,7,8,9;int Increase210=0,1,2,3,4,5,6,7,8,9;int Decline110=9,8,7,6,5,4,3,2,1,0;int Decline210=9,8,7,6,5,4,3,2,1,0;int OutOfOrder110=6,5,1,4,2,3,7,0,9,8;int OutOfOrder210=6,5,1,4,2,3,7,0,9,8;cout应用希尔排序对“单增”进行排序endl;ShellSort(Increase1,10);print(Increase1,10);coutendl;cout应用快速排序对“单增”

4、进行排序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;return 0;总结：希尔排序为插入排序中的一种，其时间复杂度在最坏的情况下为O(n2),在最好的情况下为O