自己做行程的网站,wordpress 帝国,新媒体 网站建设,宁波做网站优化哪家好给定N个#xff08;长整型范围内的#xff09;整数#xff0c;要求输出从小到大排序后的结果。 本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下#xff1a; 数据1#xff1a;只有1个元素#xff1b; 数据2#xff1a;11个不相同的整数… 给定N个长整型范围内的整数要求输出从小到大排序后的结果。 本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下 数据1只有1个元素 数据211个不相同的整数测试基本正确性 数据3103个随机整数 数据4104个随机整数 数据5105个随机整数 数据6105个顺序整数 数据7105个逆序整数 数据8105个基本有序的整数 数据9105个随机正整数每个数字不超过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 #includecstdio
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 n; i){scanf(%ld,a[i]);}//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 n; i){if(i 0) printf(%ld,a[i]);else printf( %ld,a[i]); }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 i; j){if(a[j] a[j1]){temp a[j];a[j] a[j1];a[j1] temp;flag true;}}if(flag false) break;}
}//插入排序
void Insertion_sort(long* a,int n){int i,j;long temp;for(i 1; i n; i){temp a[i];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 n; i){temp a[i];for(j i 1; j n; j){if(a[j] temp){temp a[j];k j;}}a[k] a[i];a[i] 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 n; i){temp a[i];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 n; i){temp a[i];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[i];a[i] temp;percdown(a,i,0);}
}
void percdown(long* a,int n,int i){long x a[i];int child;for(; i * 2 1 n - 1; i child){child 2 * i 1;if(child n - 1 a[child 1] a[child]) child;if(a[child] x) break;else a[i] a[child];}a[i] 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 (startend)/2;msort(a,tmp,start,middle);msort(a,tmp,middle1,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 middle r end){if(a[l] a[r]) tmp[s] a[l];else tmp[s] a[r];}while(l middle) tmp[s] a[l];while(r end) tmp[s] a[r];for(;start end; start)a[start] tmp[start];
} 转载于:https://www.cnblogs.com/wanghao-boke/p/9997610.html
