泉州网页网站制作,北京网站建设价格低,一个微信公众号可以做几个网站,个人网站写什么好给定你一个长度为 n
的整数数列。
请你对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行#xff0c;第一行包含整数 n
。
第二行包含 n
个整数#xff08;所有整数均在 1∼109
范围内#xff09;#xff0c;表示整个数列。
输…给定你一个长度为 n
的整数数列。
请你对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行第一行包含整数 n
。
第二行包含 n
个整数所有整数均在 1∼109
范围内表示整个数列。
输出格式
输出共一行包含 n
个整数表示排好序的数列。
数据范围
1≤n≤100000 输入样例
5
3 1 2 4 5输出样例
1 2 3 4 5代码
#include iostream
#include cstring
#include algorithm
using namespace std;const int N 100010;
int n;
int q[N];
int sz,w[N]; //merge_sort
void inser_sort() //直接插入排序 n^2 TLE
{for(int i1;in;i) //遍历每一个位置{if(q[i-1]q[i]) continue;int tq[i],ji;while(q[j-1]tj!0) //如果后面的数t大于前面的则后面的数t往前移,直到遍历到没有比t大的位置时停止{q[j]q[j-1];j--;}q[j]t;}
}
void binary_search_insert_sort() //折半插入排序 n^2 TLE
{for(int i1;in;i){if(q[i-1]q[i]) continue; int tq[i];int l0,ri-1; //二分查找while(lr) //找到lr的位置q[l]t{int mid(lr)/2; //下取整要得到的在l左边if(q[mid]t) rmid; else lmid1;}for(int ji-1;jl;j--) q[j1]q[j];q[l]t;}
}
void bubble_sort() //冒泡排序
{for(int i0;in-1;i) //排n-1次{bool has_swapfalse; //优化for (int jn-1; ji; j-- ) //从后往前找到i个小的数if(q[j]q[j-1]){swap(q[j],q[j-1]);has_swaptrue;}if(!has_swap) break; //如果没有交换说明已经有序}
}
void select_sort() //简单选择排序,每次选择出第i小的数到到第i位置
{for(int i0;in-1;i){int ki; //用k记录最小数的位置for(int ji1;jn;j) if(q[j]q[k])kj;swap(q[i],q[k]);}
}
void shell_sort() //希尔排序
{for(int dn/3;d;d d2?1:d/2) //d个一组,找d{for(int start0;startd;start) //对每一组进行遍历{for(int istartd;in;id) //划分每一组,进行组内直接插入排序,从前往后遍历{int tq[i],ji;while(j!startq[j-d]t){q[j]q[j-d];j-d;}q[j]t;}}}
}
void quick_sort(int l,int r) //快速排序
{if(lr) return;int il-1,jr1,xq[(lr)/2]; //选取分组中间的数作为基数while(ij){do i;while(q[i]x);do j--;while(q[j]x);if(ij) swap(q[i],q[j]);}quick_sort(l,j); //此时必须写j,否则[0,1]边界死循环 //写i要改成i-1,i xq[(lr1)/2]或者q[r]quick_sort(j1,r);
}
void down(int u)
{int tu;if(u*2szq[u*2]q[t]) tu*2;if(u*21szq[u*21]q[t]) tu*21;if(u!t){swap(q[u],q[t]);down(t);}
}
void heap_sort() //堆排序,下标一定要从1开始
{szn;for(int in/2;i;i--) down(i);for(int i0;in-1;i){swap(q[1],q[sz]);sz--;down(1;)}
}
void merge_sort(int l,int r) //二路归并排序
{if(lr) return;int mid(lr)/2;merge_sort(l,mid),merge_sort(mid1,r);int il,jmid1,k0;while(imidjr) //双指针算法{if(q[i]q[j]) w[k]q[i];else w[k]q[j];}while(imid) w[k]q[i]; //如果[mid1,r]区间都小于[i,mid],这时将[i,mid]区间拼接到后面while(jr) w[k]q[j]; //如果[l,mid]区间都小于[j,r]区间则将[j,r]拼接到后面for(il,j0;jk;i,j) q[i]w[j];
}
int main()
{scanf(%d, n);for(int i0;in;i){scanf(%d, q[i]);}// inser_sort();// binary_search_insert_sort();// bubble_sort();// select_sort();// shell_sort();// quick_sort(0,n-1);// heap_sort();merge_sort(0,n-1);for(int i0;in;i) printf(%d ,q[i]);return 0;
}
