給定你一個(gè)長(zhǎng)度為 n
的整數(shù)數(shù)列。
請(qǐng)你對(duì)這個(gè)數(shù)列按照從小到大進(jìn)行排序。
并將排好序的數(shù)列按順序輸出。
輸入格式
輸入共兩行，第一行包含整數(shù) n
。
第二行包含 n
個(gè)整數(shù)（所有整數(shù)均在 1～109
范圍內(nèi)），表示整個(gè)數(shù)列。
輸出格式
輸出共一行，包含 n
個(gè)整數(shù)，表示排好序的數(shù)列。
數(shù)據(jù)范圍
1≤n≤100000文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-639970.html
輸入樣例：
5
3 1 2 4 5
輸出樣例：
1 2 3 4 5
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-639970.html
?代碼
#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 i=1;i<n;i++) //遍歷每一個(gè)位置
{
if(q[i-1]<=q[i]) continue;
int t=q[i],j=i;
while(q[j-1]>t&&j!=0) //如果后面的數(shù)t大于前面的，則后面的數(shù)t往前移,直到遍歷到?jīng)]有比t大的位置時(shí)停止
{
q[j]=q[j-1];
j--;
}
q[j]=t;
}
}
void binary_search_insert_sort() //折半插入排序 n^2 TLE
{
for(int i=1;i<n;i++)
{
if(q[i-1]<=q[i]) continue;
int t=q[i];
int l=0,r=i-1; //二分查找
while(l<r) //找到l=r的位置，q[l]>=t
{
int mid=(l+r)/2; //下取整，要得到的在l左邊
if(q[mid]>t) r=mid;
else l=mid+1;
}
for(int j=i-1;j>=l;j--) q[j+1]=q[j];
q[l]=t;
}
}
void bubble_sort() //冒泡排序
{
for(int i=0;i<n-1;i++) //排n-1次
{
bool has_swap=false; //優(yōu)化
for (int j=n-1; j>i; j-- ) //從后往前，找到i個(gè)小的數(shù)
if(q[j]<q[j-1])
{
swap(q[j],q[j-1]);
has_swap=true;
}
if(!has_swap) break; //如果沒(méi)有交換，說(shuō)明已經(jīng)有序
}
}
void select_sort() //簡(jiǎn)單選擇排序,每次選擇出第i小的數(shù)到到第i位置
{
for(int i=0;i<n-1;i++)
{
int k=i; //用k記錄最小數(shù)的位置
for(int j=i+1;j<n;j++)
if(q[j]<q[k])
k=j;
swap(q[i],q[k]);
}
}
void shell_sort() //希爾排序
{
for(int d=n/3;d;d= d==2?1:d/2) //d個(gè)一組,找d
{
for(int start=0;start<d;start++) //對(duì)每一組進(jìn)行遍歷
{
for(int i=start+d;i<n;i+=d) //劃分每一組,進(jìn)行組內(nèi)直接插入排序,從前往后遍歷
{
int t=q[i],j=i;
while(j!=start&&q[j-d]>t)
{
q[j]=q[j-d];
j-=d;
}
q[j]=t;
}
}
}
}
void quick_sort(int l,int r) //快速排序
{
if(l>=r) return;
int i=l-1,j=r+1,x=q[(l+r)/2]; //選取分組中間的數(shù)作為基數(shù)
while(i<j)
{
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
quick_sort(l,j); //此時(shí)必須寫(xiě)j,否則[0,1]邊界死循環(huán) //寫(xiě)i要改成i-1,i x=q[(l+r+1)/2]或者q[r]
quick_sort(j+1,r);
}
void down(int u)
{
int t=u;
if(u*2<=sz&&q[u*2]>q[t]) t=u*2;
if(u*2+1<=sz&&q[u*2+1]>q[t]) t=u*2+1;
if(u!=t)
{
swap(q[u],q[t]);
down(t);
}
}
void heap_sort() //堆排序,下標(biāo)一定要從1開(kāi)始
{
sz=n;
for(int i=n/2;i;i--) down(i);
for(int i=0;i<n-1;i++)
{
swap(q[1],q[sz]);
sz--;
down(1;)
}
}
void merge_sort(int l,int r) //二路歸并排序
{
if(l>=r) return;
int mid=(l+r)/2;
merge_sort(l,mid),merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r) //雙指針?biāo)惴? {
if(q[i]<=q[j]) w[k++]=q[i++];
else w[k++]=q[j++];
}
while(i<=mid) w[k++]=q[i++]; //如果[mid+1,r]區(qū)間都小于[i,mid],這時(shí)將[i,mid]區(qū)間拼接到后面
while(j<=r) w[k++]=q[j++]; //如果[l,mid]區(qū)間都小于[j,r]區(qū)間，則將[j,r]拼接到后面
for(i=l,j=0;j<k;i++,j++) q[i]=w[j];
}
int main()
{
scanf("%d", &n);
for(int i=0;i<n;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 i=0;i<n;i++) printf("%d ",q[i]);
return 0;
}到了這里，關(guān)于排序（快速排序，歸并排序，插入排序，選擇排序，冒泡排序，希爾排序，堆排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
