希尔排序和快速排序.docx

实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。
任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组数据：单增、单减、乱码等，对它们进行比较分析。
#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=r[i];
j=i-d;
while(j>=0&&temp<r[j]){
r[j+d]=r[j];
j=j-d;
}
r[j+d]=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=r[i];
while (i<j) {

while (i<j && r[i]<= r[j])
j--; //右侧扫描
r[i]=r[j]; //将较小记录交换到前面
while (i<j && r[i]<= r[j])
i++; //左侧扫描
r[j]=r[i]; //将较大记录交换到后面
}
r[i]=temp;
QuickSort(r, first, i-1); //递归地对左侧子序列进行快速排序
QuickSort(r, i+1, end); //递归地对右侧子序列进行快速排序
}
}
void print(int r[],int n){
for(int i=0;i<n;i++){

cout<<r[i];
}
return;
}
int main(){
int Increase1[10]={0,1,2,3,4,5,6,7,8,9};
int Increase2[10]={0,1,2,3,4,5,6,7,8,9};
int Decline1[10]={9,8,7,6,5,4,3,2,1,0};
int Decline2[10]={9,8,7,6,5,4,3,2,1,0};
int OutOfOrder1[10]={6,5,1,4,2,3,7,0,9,8};
int OutOfOrder2[10]={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)