09-排序1 排序 （25 分）发布时间：2022/5/31 12:57:18
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
数据6：105个顺序整数；
数据7：105个逆序整数；
数据8：105个基本有序的整数；
数据9：105个随机正整数，每个数字不超过1000。
输入格式: 输入第一行给出正整数N（≤），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。
输出格式: 在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
输入样例: 11
4 981 10 -17 0 -20 29 50 8 43 -5
输出样例: -20 -17 -5 0 4 8 10 29 43 50 981
#include
const int maxn = 100010;
void Bubble_sort(long* a,int n);
void Insertion_sort(long* a,int n);
void Select_sort(long *a,int n);
void Shell_sort(long* a,int n);
void Shell_sedgewick(long* a,int n);
//快排，归并，堆排序
int main(){
int n;
scanf("%d",&n);
long a[maxn];
for(int i = 0; i ){
scanf("%ld",&a);
}
//Bubble_sort(a,n);
//Insertion_sort(a,n);
//Select_sort(a,n);
//Shell_sort(a,n);
Shell_sedgewick(a,n);
for(int i = 0; i ){
if(i == 0) printf("%ld",a);
else printf(" %ld",a);
}
return 0;
}
//冒泡排序
void Bubble_sort(long *a,int n){
bool flag;
long temp;
for(int i = n-1; i > 0; i--){
flag = false;
for(int j = 0; j ){
if(a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = true;
}
}
if(flag == false) break;
}
}
//插入排序
void Insertion_sort(long* a,int n){
int i,j;
long temp;
for(i = 1; i ){
temp = a;
for(j = i; j > 0 && a[j - 1] > temp; j--) a[j] = a[j - 1];
a[j] = temp;
}
}
//选择排序
void Select_sort(long* a,int n){
int i,j,k;
long temp;
for( i = 0; i ){
temp = a;
for(j = i + 1; j ){
if(a[j] temp){
temp = a[j];
k = j;
}
}
a[k] = a;
a = temp;
}
}
//希尔-自增排序
void Shell_sort(long*a ,int n){
int i,j,d;
long temp;
for(d = n/2; d > 0; d /= 2){
for(i = d; i ){
temp = a;
for(j = i; j >= d && a[j - d] > temp; j -= d)
a[j] = a[j - d];
a[j] = temp;
}
}
}
//希尔-数组排序
void Shell_sedgewick(long* a,int n){
int i,j,d,si;
int sedgewick[] = {929,505,209,109,41,19,5,1,0};
long temp;
for(si = 0; sedgewick[si] >= n; si++);
for(; sedgewick[si] > 0; si++){
d = sedgewick[si];
for(i = d; i ){
temp = a;
for(j = i; j >= d && a[j - d] > temp; j -= d) a[j] = a[j - d];
a[j] = temp;
}
}
}
void Heap_sort(long* a,int n){
long temp;
int i;
for(i = (n-2)/2; i >= 0; i--){
percdown(a,n,i);
}
for(i = n - 1; i > 0; i--){
temp = a[0];
a[0] = a;
a = temp;
percdown(a,i,0);
}
}
void percdown(long* a,int n,int i){
long x = a;
int child;
for(; i * 2 + 1 1; i = child){
child = 2 * i + 1;
if(child 1 && a[child + 1] > a[child]) child++;
if(a[child] break;
else a = a[child];
}
a = x;
}
void Merge_sort(long*a ,int n){
long* tmp = (long*)malloc(n*sizeof(long));
msort(a,tmp,0,n-1);
free(tmp);
}
void msort(long*a,long* tmp,int start,int end){
int middle;
if(start end){
middle = (start+end)/2;
msort(a,tmp,start,middle);
msort(a,tmp,middle+1,end);
merge(a,tmp,start,end,middle);
}
}
void merge(long* a,long* tmp,int start,int end,int middle){
int l,s,r;
l = start;
s = start;
r = middle + 1;
while(l end){
if(a[l] ];
else tmp[s++] = a[r++];
}
while(l ];
while(r ];
for(;start )
a[start] = tmp[start];
}
转载于:https://www.cnblogs.com/wanghao-boke/p/9997610.html
 |
