內(nèi)部排序：排序期間元素全部存放在內(nèi)存中
外部排序：排序期間元素無法全部同時放在內(nèi)存中
插入排序
基本思想：每次將一個待排序的記錄按其關(guān)鍵字大小插入到前面已排好序的子序列中耳鸯。
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)
最壞的情況：表中元素逆序谬哀，總比較次數(shù)Σi，總移動次數(shù)Σ(i+1)（i屬于[2,n]）
平均 O(n^2)
穩(wěn)定
適用性：適用于順序存儲和鏈式存儲的線性表严肪。適合基本有序和數(shù)據(jù)量不大的排序表史煎。為鏈式存儲時，可從前往后查找指定元素的位置驳糯。注：大部分排序算法都僅適用于順序存儲的線性表篇梭。
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];
}
}
減少了比較次數(shù)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在某個范圍內(nèi)是古胆，O(n1.3)肆良，最壞情況O(n2)
不穩(wěn)定：當相同關(guān)鍵字被劃分到不同子表時筛璧，可能會改變相對次序。
適用性：僅適用于順序存儲的線性表
