希爾排序和快速排序

1、精選優(yōu)質文檔-傾情為你奉上實驗內容：對希爾排序、快速排序、歸并排序任意選擇兩種排序方法進行比較。任意選擇希爾排序、快速排序、歸并排序中兩種排序方法，對任意給定一組數(shù)據(jù)：單增、單減、亂碼等，對它們進行比較分析。#include<iostream>using namespace std;void ShellSort(int r , int n)int temp;int d,i,j;d=n/2;while(d>0)for(i=d;i<n;i+)temp=ri;j=i-d;while(j>=0&&temp<rj)rj+d=rj;j=j-d;rj+d=

2、temp;d=d/2;void QuickSort(int r , int first, int end)int i,j;i=first;j=end; /初始化int temp;if(first<end)temp=ri;while (i<j) while (i<j && ri<= rj) j-; /右側掃描 ri=rj; /將較小記錄交換到前面while (i<j && ri<= rj)i+; /左側掃描rj=ri; /將較大記錄交換到后面ri=temp;QuickSort(r, first, i-1); /遞歸地對左側子序列

3、進行快速排序 QuickSort(r, i+1, end); /遞歸地對右側子序列進行快速排序void print(int r,int n)for(int i=0;i<n;i+)cout<<ri;return;int main()int Increase110=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,

4、9,8;int OutOfOrder210=6,5,1,4,2,3,7,0,9,8;cout<<"應用希爾排序對“單增”進行排序"<<endl;ShellSort(Increase1,10);print(Increase1,10);cout<<endl;cout<<"應用快速排序對“單增”進行排序"<<endl;QuickSort(Increase2,0,9);print(Increase2,10);cout<<endl;cout<<"應用希爾排序對“單減”進行

5、排序"<<endl;ShellSort(Decline1,10);print(Decline1,10);cout<<endl;cout<<"應用快速排序對“單減”進行排序"<<endl;QuickSort(Decline2,0,9);print(Decline2,10);cout<<endl;cout<<"應用希爾排序對“亂序”進行排序"<<endl;ShellSort(OutOfOrder1,10);print(OutOfOrder1,10);cout<<endl;cout<<"應用快速排序對“亂序”進行排序"<<endl;QuickSort(OutOfOrder2,0,9);print(OutOfOrder2,10);cout<<endl;return 0;總結：希爾排序為插入排序中的一種，其時間復雜度在最壞的情況下為O(n2)