假如我们要从小到大排序，下面几种简单的算法可以处理规模不大的数据，我写成函数形式。

一、插入排序

　　思想就是：从左到右对每个数，每次在它前面找到一个合适的位置把它插进去。

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

 

　　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。　　

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

 

　　

二、选择排序

　　思想是：每次找未排序的部分（i到n）最小的，和第i个交换。

void SelectSort(int a[],int n){    int i,j,Min,t;    for(i=1;i

 

　　比较次数　$C=n(n-1)/2$

　　移动次数  $M_{max}=3(n-1),M_{min}=0$

　　改进：树形选择排序（锦标赛排序）

　　　　是稳定排序。

　　　　时间复杂度$O(nlog_2n)$

　　　　辅助空间较多。

三、冒泡排序

　　思想：每次从左到右将每对相邻的且逆序的数交换，可以使未排序的最大的数放到未排序数的最后。

void BubbleSort(int a[],int n){
    //a数组下标1~n    int i,j,temp;    bool sorted;    for(i=1; i
     
      a[j+1])            {                temp=a[j];                a[j]=a[j+1];                a[j+1]=temp;                sorted=false;            }        }    }}
     

 

　　

调用：

cin>>n;for(int i=1; i<=n; i++)    cin>>a[i];BubbleSort(a,n);