对于数据的排序，有多种方法，对应这不同的时间复杂度（效率不同）。
一、冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort）是一种简单的排序算法。
算法思路：
1. 从第一对相邻数据开始到最后一组相邻数据比较，两两依次比较，最后一组数据结束时，数组 下标n对应的数即为最大数。
2.重复上述操作，直至下标为n-1 （下标为n的数已经是最大的，不需要重复操作）
3.最后重复操作直至不需要再比较任意一对数（即总共进行n次）
时间复杂度
图示（省略比较不交换的操作）：
冒泡排序代码：
#include<cstdio>
#include<iostream>
using namespace std;
int a[1001];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i;j++)
{
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
return 0;
}
二、插入排序（Insert sort）
插入排序很好理解，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法思路：
1.默认第一个元素为已排序序列
2.取出下一个元素，在已排序序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置（前移一位）
4.重复操作3，直到找到已排序的元素小于或者等于新元素的位置，并将新元素插入到该位置后
5.重复2~4操作，直至对最后一个元素插入操作结束。
时间复杂度：
关键操作：步骤3 从后向前扫描 以上图④为例
代码实现插入排序：
#include<cstdio>
#include<iostream>
using namespace std;
int a[1001];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
for(int j=i+1;j>=1;j--)
if(a[j]<a[j-1]) swap(a[j],a[j-1]);
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
return 0;
}三、归并排序（Merge sort）
归并排序（Merge sort）是一种采用分治法的排序方法，将已有的子序列合并，合并成一个有
序的新序列。时间复杂度：
算法思路（分支法）：
1.分：将原序列分成相应的子序列（二分方法）。时间复杂度为 ，相比上述两种排序方法的效率大大提高，因此更适合数据范围更大的情况。
// “分”的伪代码
void merge(int l,int r)
{
int mid=l+(r-l)/2; // 二分
if(l<r)
{
merge(l,mid);
merge(mid+1,r);
merge_sort(l,mid,r); // 并
}
} 2.并：将分的子序列合并成一个新的有序数列（合并的过程是线性的，时间复杂度为）
“并”的过程思路很简单，但与递归结合代码实现较难
将 [ l , r ] 与 [ mid+1 , r ] 的序列合并，采用线性方法，如图所示：
从两个序列的第一个数一次比较，取出较小的数放入新的有序数组，然后再将新数组赋值到原来的数组中。
void merge_sort(int l,int mid,int r) // 将[l,mid]与[mid+1,r]的序列合并
{
int i=l,j=mid+1,k=l;
while(i!=mid+1 && j!=r+1) // 采用线性的方法
{
if(a[i]>a[j])
{
b[k++]=a[j];
j++;
}
else
{
b[k++]=a[i];
i++;
}
}
while(i!=mid+1) b[k++]=a[i++]; // 将剩下未被完全取出的序列依次取出放入新数组
while(j!=r+1) b[k++]=a[j++];
for(int i=l;i<=r;i++) a[i]=b[i];
}一个关于归并排序的思考：
归并过程通过将两个序列合并成一个有序数列，需要通过比较两个序列首端的元素大小，并依次取出，这个过程是线性的，需要保证这两个序列也是有序的，但这两个序列会不会有序呢？为什么有序呢？
通过每次递归加上不断重复更新原数组，保证每次并的过程结果都会是有序的，所以当合并两个序列是，这两个序列也是有序的。