希爾排序和快速排序

1、實(shí)驗(yàn)內(nèi)容：對(duì)希爾排序、快速排序、歸并排序任意選擇兩種排序方法進(jìn)行比較。任意選擇希爾排序、快速排序、歸并排序中兩種排序方法，對(duì)任意給定一組數(shù)據(jù)：?jiǎn)卧觥螠p、亂碼等，對(duì)它們進(jìn)行比較分析。#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-; /右側(cè)掃描 ri=rj; /將較小記錄交換到前面while (ij & ri= rj)i+; /左側(cè)掃描rj=ri; /將較大記錄交換到后面ri=temp;QuickSort(r, first, i-1); /遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序 QuickSort(r, i+1, end); /遞歸地對(duì)右側(cè)子序列進(jìn)行快速排序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應(yīng)用希爾排序?qū)Α皢卧觥边M(jìn)行排序endl;ShellSort(Increase1,10);print(Increase1,10);coutendl;cout應(yīng)用快速排序?qū)Α皢卧觥?/p>

4、進(jìn)行排序endl;QuickSort(Increase2,0,9);print(Increase2,10);coutendl;cout應(yīng)用希爾排序?qū)Α皢螠p”進(jìn)行排序endl;ShellSort(Decline1,10);print(Decline1,10);coutendl;cout應(yīng)用快速排序?qū)Α皢螠p”進(jìn)行排序endl;QuickSort(Decline2,0,9);print(Decline2,10);coutendl;cout應(yīng)用希爾排序?qū)Α皝y序”進(jìn)行排序endl;ShellSort(OutOfOrder1,10);print(OutOfOrder1,10);coutendl;cout應(yīng)用快速排序?qū)Α皝y序”進(jìn)行排序endl;QuickSort(OutOfOrder2,0,9);print(OutOfOrder2,10);coutendl;return 0;總結(jié)：希爾排序?yàn)椴迦肱判蛑械囊环N，其時(shí)間復(fù)雜度在最壞的情況下為O(n2),在最好的情況下為O