- 软件开发
- 希尔排序+快速排序+堆排序
#include<iostream>
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
){
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个数据\n";
cin
>>t
;
for(int i
=0;i
<t
;i
++){
cin
>>a
[i
];
}
Shellsort(a
,b
,t
);
Output(a
,t
);
cout
<<"\n快速排序，请输入数据个数n，和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，和n个数据\n";
cin
>>t
;
for(int i
=1;i
<=t
;i
++){
cin
>>a
[i
];
}
Heapsort(a
,t
);
return 0;
}
