POJ-排序模板
标签：规则 bsp i++ 比较大小 mes color ctr 个数 超过
1.冒泡排序
时间复杂度：O(n^2)，空间复杂度O(n)
题目描述：
对输入的n个数进行排序并输出。
输入：
输入的第一行包括一个整数n(1
输出：
可能有多组测试数据，对于每组数据，将排序后的n个整数输出，每个数后面都有一个空格。每组测试数据的结果占一行。
样例输入：
样例输出：
模板：
#includeusing namespace std;
int main()
{
int n;
int buf[100];//保存我们将要排序的数字
while (cin >> n)//Ctrl+Z结束输入（Dev C++适用）
{
for (int i = 0; i )
{
cin >> buf[i];
}
for (int i = 0; i ) //冒泡排序主体
{
for (int j = 0; j 1 - i; j++)
{
if (buf[j] > buf[j + 1])
{
int tmp = buf[j];
buf[j] = buf[j + 1];
buf[j + 1] = tmp;
}
}
}
for (int i = 0; i )
cout " ";
cout endl;
}
return 0;
}
2.快速排序：
时间复杂度O(nlog2n)，空间复杂度O(log2n)~O(n) （退化为冒泡排序）
n=10000时，冒泡排序的时间复杂度超过百万数量级，即超过1s的时限，需要采用快速排序
#include
#include
using namespace std;
int main()
{
int n;
int buf[10000];//保存我们将要排序的数字
while (cin >> n)
{
for (int i = 0; i )
{
cin >> buf[i];
}
sort(buf, buf + n);
for (int i = 0; i )
cout " ";
cout endl;
}
return 0;
}
快排变体：改变大小规则
让数据从大到小逆序排列，需要对sort函数中的比较大小规则重新定义。
#include
#include
using namespace std;
bool cmp(int x, int y)
{
return x > y;
}
int main()
{
int n;
int buf[10000];//保存我们将要排序的数字
while (cin >> n)
{
for (int i = 0; i )
{
cin >> buf[i];
}
sort(buf, buf + n, cmp);
for (int i = 0; i )
cout " ";
cout endl;
}
return 0;
}
使用内置函数sort的方法，简单易懂，且不易出错，对各种类型的排序写法也大同小异。所以，强烈推荐使用sort来完成排序。
POJ-排序模板
标签：规则 bsp i++ 比较大小 mes color ctr 个数 超过
原文地址：https://www.cnblogs.com/yun-an/p/11025400.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
POJ-排序模板
文章链接：http://soscw.com/essay/24779.html
评论