ヒルソート+クイックソート+スタックソート
21792 ワード
/*
10
11 43 97 34 28 92 0 2 343 543
*/
#include
using namespace std;
void Shell(int a[],int b,int t){// , ,
int tem;
for(int i=b;i<t;i++){
if(a[i]<a[i-b]){
tem=a[i];
int j=i-b;
while(a[j]>tem&&j>=0){
a[j+b]=a[j];
j-=b;
}
a[j+b]=tem;
}
}
}
void Shellsort(int a[],int b[],int t){
for(int i=10;i>=0;i--){
Shell(a,b[i],t);
}
}
int Qsort(int a[],int low,int high){
int tem=a[low];
while(low<high){
while(a[high]>=tem&& high>low) high--;
a[low]=a[high];
while(a[low]<=tem && high>low) low++;
a[high]=a[low];
}
a[low]=tem;
return low;
}
void Quicksort(int a[],int low,int high) {
if(low<high){
int mid=Qsort(a,low,high);
Quicksort(a,low,mid-1);
Quicksort(a,mid+1,high);
}
}
void Heapadjust(int a[],int min,int max){//
int root=min;
int id=min;
int tem=a[min];
for(int i=min*2;i<=max;i*=2){
if(i<max && a[i]<a[i+1]) i++;
if(tem>=a[i]) break;
a[i/2]=a[i];
id=i;
}
a[id]=tem;
}
void Heapsort(int a[],int t){//a[o] ,
for(int i=t/2;i>=1;i--)
Heapadjust(a,i,t);
int last=t;//
while(last>=1){
cout<<a[1]<<endl;
int tem=a[last];
a[last]=a[1];
a[1]=tem;
last--;
Heapadjust(a,1,last);
}
}
void Output(int a[],int t){
for(int i=0;i<t;i++){
cout<<a[i]<<endl;
}
}
int main()
{
int a[10000];
int t;//
int b[15]={1,3,5,7,11,13,19,23,29};
cout<<" , n, n
";
cin>>t;
for(int i=0;i<t;i++){
cin>>a[i];
}
Shellsort(a,b,t);
Output(a,t);
cout<<"
, n, n
";
cin>>t;
for(int i=0;i<t;i++){
cin>>a[i];
}
Quicksort(a,0,t-1);
Output(a,t);
cout<<"
, n, n
";
cin>>t;
for(int i=1;i<=t;i++){
cin>>a[i];
}
Heapsort(a,t);
return 0;
}