聲明：版權所有，歡迎轉載。 聯系信箱：[email protected]】
直接排序算是比較常用的算法了。不多說，直接切入正文。
1、基本思想
假設待排序的記錄存放在數組R[1..n]中。初始時，R[1]自成1個有序區，無序區為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當前的有序區R[1..i-1]中，生成含n個記錄的有序區。
2、第i-1趟直接插入排序：
通常將一個記錄R[i](i=2，3，…，n-1)插入到當前的有序區，使得插入後仍保證該區間裡的記錄是按關鍵字有序的操作稱第i-1趟直接插入排序。
排序過程的某一中間時刻，R被劃分成兩個子區間R[1．．i-1]已排好序的有序區）和R[i．．n]當前未排序的部分，可稱無序區）。
直接插入排序的基本操作是將當前無序區的第1個記錄R[i]插人到有序區R[1．．i-1]中適當的位置上，使R[1．．i]變為新的有序區。因為這種方法每次使有序區增加1個記錄，通常稱增量法。
插入排序與打撲克時整理手上的牌非常類似。摸來的第1張牌無須整理，此後每次從桌上的牌(無序區)中摸最上面的1張並插入左手的牌(有序區)中正確的位置上。為了找到這個正確的位置，須自左向右(或自右向左)將摸來的牌與左手中已有的牌逐一比較。
一趟直接插入排序方法
1．簡單方法
首先在當前有序區R[1..i-1]中查找R[i]的正確插入位置k(1≤k≤i-1)；然後將R[k．．i-1]中的記錄均後移一個位置，騰出k位置上的空間插入R[i]。
注意：
若R[i]的關鍵字大於等於R[1．．i-1]中所有記錄的關鍵字，則R[i]就是插入原位置。
2．改進的方法
一種查找比較操作和記錄移動操作交替地進行的方法。
具體做法：
將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：
① 若R[j]的關鍵字大於R[i]的關鍵字，則將R[j]後移一個位置；
②若R[j]的關鍵字小於或等於R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。
關鍵字比R[i]的關鍵字大的記錄均已後移，所以j+1的位置已經騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。
int insertSortArray(int array[], int len)
{
int index = 1;
int bottom, tmp;
for (; index < len; index++)
{
if(array[index] < array[index - 1])
{
tmp = array[index];
array[index] = array[index - 1];
for (bottom = index - 1; tmp < array[bottom]; bottom--)//移位
{
array[bottom + 1] = array[bottom];
}
array[bottom + 1] = tmp;
}
}
return TRUE;
}哨兵監視哨）的作用：
1.作為臨時變量存放R[i]的副本。
2.在查找循環中用來監視下標變量j是否越界。
算法效率：
時間復雜度最好的情況是已經排好序，比較次數為n-1，移動次數為0；最壞的情況是反序時進行插入排序，平均的移動次數和比較次數都是O(n*n）。空間復雜度為O(1)。
排序特點：
1.是一種穩定的排序方法。
2.適用於接近排好序的情況。
3.適用於n較小的情況。
4.直至最後一趟排序過程才能確定一個元素的最終位置。
從空間來看，它只需要一個記錄的輔助空間R[0]；從時間來看，n個記錄要進行n-1趟插入過程，每一趟都要進行與關鍵字的比較和記錄的移動，但是比較的次數是不固定的。最好的情況是記錄已經是排列有序的，則每一趟都只需要比較一次，就可以找到插入記錄的位置，不需移動記錄，復雜度為On）；最壞情況是記錄逆序存放，則每一趟都要與前面的關鍵字進行比較並移動記錄，復雜度為On*n）。所以平均性能的復雜度為On*n）。
因此，直接插入排序算法非常適合記錄基本有序且記錄數不是很多的情形。
本文出自 “驿落黃昏” 博客，請務必保留此出處http://yiluohuanghun.blog.51cto.com/3407300/1266966
