1.冒泡排序

时间复杂度：O(n^2)，空间复杂度O(n)

题目描述：

对输入的n个数进行排序并输出。

输入：

输入的第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出：

可能有多组测试数据，对于每组数据，将排序后的n个整数输出，每个数后面都有一个空格。每组测试数据的结果占一行。

样例输入：

41 4 3 2

样例输出：

1 2 3 4

模板：

#include
     
      using namespace std;int main(){    int n;    int buf[100];//保存我们将要排序的数字    while (cin >> n)//Ctrl+Z结束输入（Dev C++适用）    {        for (int i = 0; i < n; i++)        {            cin >> buf[i];        }        for (int i = 0; i < n; i++) //冒泡排序主体        {            for (int j = 0; j < n - 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 < n; i++)            cout << buf[i] <<" ";        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 < n; i++)        {            cin >> buf[i];        }        sort(buf, buf + n);        for (int i = 0; i < n; i++)            cout << buf[i] <<" ";        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 < n; i++)        {            cin >> buf[i];        }        sort(buf, buf + n, cmp);        for (int i = 0; i < n; i++)            cout << buf[i] <<" ";        cout << endl;    }    return 0;}
      
     

使用内置函数sort的方法，简单易懂，且不易出错，对各种类型的排序写法也大同小异。所以，强烈推荐使用sort来完成排序。