內部排序：排序期間元素全部存放在內存中
外部排序：排序期間元素無法全部同時放在內存中

插入排序

基本思想：每次將一個待排序的記錄按其關鍵字大小插入到前面已排好序的子序列中。
1.直接插入排序
就地排序，空間復雜度為O(1)

void InsertSort(ElemType A[], int n)
{
    int i, j;
    for(i=2;i<=n;++i)
        if(A[i].key<A[i-1].key){
            A[0]=A[i];    //復制為哨兵A[0]不存放元素
            for(j=i-1;A[0].key<A[j].key;--j)    //后移
                A[j+1]=A[j];
            A[j+1]=A[0];    //插入
        }
}

時間效率
最好的情況：表中元素已有序，每插入一個元素只需比較一次無序移動，O(n)
最壞的情況：表中元素逆序，總比較次數Σi，總移動次數Σ(i+1)（i屬于[2,n]）
平均 O(n^2)
穩(wěn)定
適用性：適用于順序存儲和鏈式存儲的線性表。適合基本有序和數據量不大的排序表。為鏈式存儲時，可從前往后查找指定元素的位置。注：大部分排序算法都僅適用于順序存儲的線性表。

2.折半插入排序
基本思想：上一個方法是邊比較邊移動的，折半插入排序，先用折半查找找到插入位置，在統(tǒng)一移動。適用于順序存儲的線性表。

void InsertSort(ElemType A[], int n)
{
    int i, j, low, high, mid;
    for(i=2;i<=n;++i){
        A[0]=A[i];
        low=1; high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid].key>A[0].key)    high=mid-1;
            else low=mid+1;
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];
        A[high+1]=A[0];
    }
}

減少了比較次數O(nlog2n)
時間復雜度仍為O(n^2)
穩(wěn)定

3.希爾排序
（縮小增量排序）
基本思想：先將待排序表分割為若干形如L[i, i+d, i+2d, ... , i+kd]的特殊子表，分別進行直接插入排序，當整個表中的元素已呈基本有序時，再對全體記錄進行一次直接排序。（相隔d的元素分為一組分別進行直接插入排序，縮小d直到d為1即整體進行直接插入排序）
d1=n/2 d(i+1)=?di/2?

void ShellSort(ElemType A[], int n)
{
     for(dk=n/2;dk>=1;dk=dk/2)
        for(i=dk+1;i<=n;++i)   //前dk個分別是dk個組的第一個所以從dk+1開始排序
            if(A[i].key<A[i-dk].key){
                A[0]=A[i];
                for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk)
                    A[j+dk]=A[j];
                A[j+dk]=A[0];
            }
}

空間效率O(1)
時間效率：當n在某個范圍內是，O(n^{1.3)，最壞情況O(n}2)
不穩(wěn)定：當相同關鍵字被劃分到不同子表時，可能會改變相對次序。
適用性：僅適用于順序存儲的線性表