下文只涉及到内排序的内容，外排序的内容后续再更新。

内排序

插入排序
直接插入排序

直接插入排序是插入排序算法中的一种，采用的方法是：在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。

void InsertSort(RecType R[], int n) //对R[0..n-1]按递增有序进行直接插入排序
{
    int i, j;
    RecType tmp;
    for (i = 1; i < n; i++)
    {
        if (R[i].key < R[i - 1].key) //反序时
        {
            tmp = R[i];
            j = i - 1;
            do //找R[i]的插入位置
            {
                R[j + 1] = R[j]; //将关键字大于R[i].key的记录后移
                j--;
            } while (j >= 0 && R[j].key > tmp.key);
            R[j + 1] = tmp; //在j+1处插入R[i]
        }
    }
}

直接插入排序算法的平均时间复杂度为：O(n2) 是稳定的排序算法。

若元素初始状态接近正序，选用直接插入排序比较好。

希尔排序

n个元素分为d组（d=n/2）相距d个位置的元素分到一组。组内一般采用直接插入排序算法。（组间必须有序，组内可以无序）

d越小时越接近有序，当d=1时基本有序。

void ShellSort(RecType R[], int n) //希尔排序算法
{
    int i, j, d;
    RecType tmp;
    d = n / 2; //增量置初值
    while (d > 0)
    {
        for (i = d; i < n; i++) //对所有组采用直接插入排序
        {
            tmp = R[i]; //对相隔d个位置一组采用直接插入排序
            j = i - d;
            while (j >= 0 && tmp.key < R[j].key)
            {
                R[j + d] = R[j];
                j = j - d;
            }
            R[j + d] = tmp;
        }
        d = d / 2; //减小增量
    }
}

希尔排序算法的平均时间复杂度为：O(n1.3) 是不稳定的排序算法。

交换排序
冒泡排序

起泡排序，别名“冒泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。通过一趟趟的比较，一个个的“最小值”被找到并移动到相应位置，直到检测到表中数据已经有序，或者比较次数等同于表中含有记录的个数，排序结束，这就是起泡排序。

void BubbleSort(RecType R[],int n)
{
    int i,j;
    for (i = 0;i < n - 1;i++) 
    {
        for (j = n - 1;j > i;j--)   //比较,找出本趟最小关键字的记录
            if (R[j].key < R[j-1].key)   //如果元素是反序
            {
                swap(R[j],R[j-1]); //交换两元素
            }
        
    }
}

改进的冒泡排序算法

void BubbleSort1(RecType R[], int n)
{
    int i, j;
    bool exchange;
    for (i = 0; i < n - 1; i++)
    {
        exchange = false;                //一趟前exchange置为假
        for (j = n - 1; j > i; j--)      //归位R[i],循环n-i-1次
            if (R[j].key < R[j - 1].key) //相邻两个元素反序时
            {
                swap(R[j], R[j - 1]); //交换两元素
                exchange = true;      //一旦有交换，exchange置为真
            }
        if (!exchange) //本趟没有发生交换，中途结束算法
            return;
    }
}

冒泡排序算法的平均时间复杂度为：O(n2) 是稳定的排序算法。

快速排序
int partition(RecType R[],int s,int t)  //一趟划分
{
    int i=s,j=t;
    RecType tmp=R[i];           //以R[i]为基准
    while (i<j)                 //从两端交替向中间扫描,直至i=j为止
    {   while (j>i && R[j].key>=tmp.key)
            j--;                //从右向左扫描,找一个小于tmp.key的R[j]
        R[i]=R[j];              //找到这样的R[j],放入R[i]处
        while (i<j && R[i].key<=tmp.key)
            i++;                //从左向右扫描,找一个大于tmp.key的R[i]
        R[j]=R[i];              //找到这样的R[i],放入R[j]处
    }
    R[i]=tmp;
    return i;
}
​
void QuickSort(RecType R[],int s,int t) //对R[s..t]的元素进行快速排序
{   int i;
    RecType tmp;
    if (s<t)                    //区间内至少存在两个元素的情况
    {   count++;
        i=partition(R,s,t);
        DispList(R,10);         //调试用
        QuickSort(R,s,i-1);     //对左区间递归排序
        QuickSort(R,i+1,t);     //对右区间递归排序
    }
}

快速排序算法的平均时间复杂度为：O(nlog2n) 是不稳定的排序算法。

快速排序算法的平均空间复杂度为：O(log2n)

初始数据若有序，则不适合采用快速排序。

选择排序
简单选择排序
void SelectSort(RecType R[],int n)
{
    int i,j,k;
    for (i=0;i<n-1;i++)         //做第i趟排序
    {
        k=i;
        for (j=i+1;j<n;j++)     //在当前无序区R[i..n-1]中选key最小的R[k]
            if (R[j].key<R[k].key)
                k=j;            //k记下目前找到的最小关键字所在的位置
            if (k!=i)               //交换R[i]和R[k]           
                swap(R[i],R[k]);            
    }
}

简单选择排序算法的平均时间复杂度为：O(n2) 是不稳定的排序算法。

对于含有n个元素简单选择排序关键字的比较次数与记录的初始排序次序无关，总是n(n-1)/2。

堆排序
void sift(RecType R[],int low,int high)   
{
    int i=low,j=2*i;                        //R[j]是R[i]的左孩子
    RecType temp=R[i];
    while (j<=high) 
    {
        if (j<high && R[j].key<R[j+1].key)  //若右孩子较大,把j指向右孩子
            j++;                            //变为2i+1
        if (temp.key<R[j].key) 
        {
            R[i]=R[j];                      //将R[j]调整到双亲结点位置上
            i=j;                            //修改i和j值,以便继续向下筛选
            j=2*i;
        }
        else break;                         //否则，筛选结束
    }
    R[i]=temp;                              //被筛选结点的值放入最终位置
}
​
void HeapSort(RecType R[],int n)
{
    int i;
    for (i=n/2;i>=1;i--)    //循环建立初始堆,调用sift算法 n/2 次
        sift(R,i,n); 
    for (i=n;i>=2;i--)      //进行n-1趟完成推排序,每一趟堆排序的元素个数减1
    {   swap(R[1],R[i]);    //将最后一个元素与根R[1]交换
        sift(R,1,i-1);      //对R[1..i-1]进行筛选,得到i-1个节点的堆     
    }
}

堆排序算法的平均时间复杂度为：O(nlog2n) 是不稳定的排序算法。

堆排序的执行时间不受初始数据状态影响。

归并排序
自底向上的二路排序算法
void Merge(RecType R[],int low,int mid,int high) 
{
    RecType *R1;
    int i=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标
    R1=(RecType *)malloc((high-low+1)*sizeof(RecType));  //动态分配空间
    while (i<=mid && j<=high)       //在第1段和第2段均未扫描完时循环
        if (R[i].key<=R[j].key)     //将第1段中的记录放入R1中
        {
            R1[k]=R[i];
            i++;k++; 
        }
        else                            //将第2段中的记录放入R1中
        {
            R1[k]=R[j];
            j++;k++; 
        }
    while (i<=mid)                      //将第1段余下部分复制到R1
    { 
        R1[k]=R[i];
        i++;k++; 
    }
    while (j<=high)                 //将第2段余下部分复制到R1
    {
        R1[k]=R[j];
        j++;k++;  
    }
    for (k=0,i=low;i<=high;k++,i++) //将R1复制到R中
        R[i]=R1[k];
} 
​
void MergePass(RecType R[],int length,int n)    //对整个排序序列进行一趟归并
{
    int i;
    for (i=0;i+2*length-1<n;i=i+2*length)   //归并length长的两相邻子表
        Merge(R,i,i+length-1,i+2*length-1);
    if (i+length-1<n-1)                     //余下两个子表,后者长度小于length
        Merge(R,i,i+length-1,n-1);          //归并这两个子表
}
​
void MergeSort(RecType R[],int n)           //自底向上的二路归并算法
{
    int length;
    for (length=1;length<n;length=2*length)//进行log2n趟归并
        MergePass(R,length,n);
}

归并排序算法的平均时间复杂度为：O(nlog2n) 是稳定的排序算法。

归并排序算法的空间复杂度为：O(n）

二路归并排序是我们所学过的最耗费内存的（空间复杂度最高）的排序算法。

常见内排序方法的性能总结
排序方法平均时间复杂度空间复杂度稳定性
直接插入排序O(n2) 排序趟数与关键字初始次序无关(n-1趟)O(1)稳定
折半插入排序O(n2）仅减少了比较元素的次数，未改变移动次数O(1)稳定
希尔排序最优可达O(n1.3)O(1)不稳定
冒泡排序O(n2)O(1)稳定
快速排序O(nlog2n)O(log2n)不稳定
简单选择排序O(n2) 比较次数始终是n(n-1)/2;排序趟数与关键字初始次序无关O(1)不稳定
堆排序O(nlog2n)O(1)不稳定
二路归并排序O(nlog2n)O(n)稳定
基数排序O( d*(n+r) ) 元素移动次数(排序趟数)与关键字初始次序无关O(r)稳定