假如我们要从小到大排序，下面几种简单的算法可以处理规模不大的数据，我写成函数形式。
一、插入排序
思想就是：从左到右对每个数，每次在它前面找到一个合适的位置把它插进去。
代码语言：javascript复制void InsertSort(int a[],int n){
int i,j,key;
for(i=2;i<=n;i ){
key=a[i];
for(j=i-1;j&&key<a[j];j--)a[j 1]=a[j];
a[j 1]=key;
}
}C是比较次数，M是移动次数，则
最好情况$C_{min}=n-1$，$M_{min}=0$;
最坏情况$C_{max}=(n 2)*(n-1)/2$,$M_{max}=frac{(n 4)(n-1)}{2}$
随机情况$C_{avg}=(C_{min} C_{max})/2 approx n^2/4$,$M_{avg}approx n^2/4$
折半插入排序，找插入位置时可以二分。
表插入排序：基于链表存储。
希尔排序：
1）按增量d分组。
2）每组用直接插入排序。
3）然后减小d(有一个增量序列，比如..15，7，3，1)，回到1），最后一次d为1。
代码语言：javascript复制int dlta[5]={15,7,3,1};
void ShellSort(int a[],int n){
int i,j,k,key;
for(k=0;k<4;k ){
int dk=dlta[k];
for(i=1 dk;i<=n;i ){
key=a[i];
for(j=i-dk;j&&key<a[j];j-=dk)a[j dk]=a[j];
a[j dk]=key;
}
}
}二、选择排序
思想是：每次找未排序的部分（i到n）最小的，和第i个交换。
代码语言：javascript复制void SelectSort(int a[],int n){
int i,j,Min,t;
for(i=1;i<n;i ){
Min=i;
for(j=i 1;j<=n;j )
if(a[j]<a[Min]) Min=j;
t=a[i];
a[i]=a[Min];
a[Min]=t;
}
}比较次数 $C=n(n-1)/2$
移动次数 $M_{max}=3(n-1),M_{min}=0$
改进：树形选择排序（锦标赛排序）
是稳定排序。
时间复杂度$O(nlog_2n)$
辅助空间较多。
三、冒泡排序
思想：每次从左到右将每对相邻的且逆序的数交换，可以使未排序的最大的数放到未排序数的最后。
代码语言：javascript复制void BubbleSort(int a[],int n)
{//a数组下标1~n
int i,j,temp;
bool sorted;
for(i=1; i<n && !sorted; i )
{
sorted=true;
for(j=1; j<=n-i; j )
{
if(a[j]>a[j 1])
{
temp=a[j];
a[j]=a[j 1];
a[j 1]=temp;
sorted=false;
}
}
}
}调用：
代码语言：javascript复制cin>>n;
for(int i=1; i<=n; i )
cin>>a[i];
BubbleSort(a,n);
