第六周--冒泡排序

题目描述

读入N个整数，利用冒泡排序法对这些数排序，输出排序后的N个数，两个数之间用空格间隔。

这里排序指的是升序。

输入格式

两行，第一行一个正整数N，表示待排序的数的个数。

第二行为N个整数。

输出格式

一行，排序后的N个数。

输入输出样例

5
4 2 4 5 1

1 2 4 4 5

冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止
设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且在此位置之后的所有记录都是有序的
设bound位置是无序区的最后一个记录，则每次冒泡排序的范围是1-bound，在一次排序后，从exchange之后一定是有序的，所以是bound=exchange

#include<bits/stdc++.h>
using namespace std;
template<class T>
void bubblesort(T r[],int n)
{
T tmp;
int exchange,bound;
exchange=n;
while(exchange)
{
bound=exchange;
exchange=0;
for(int j=1;j<bound;j++)
if(r[j]>r[j+1])
{
tmp=r[j];
r[j]=r[j+1];
r[j+1]=tmp;
exchange=j;
}
}
}
int main()
{
int n,a[100001];
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
bubblesort(a,n);
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}