包括直接插入排序，希尔插入排序。

• 直接插入排序：

将一个记录插入到已经排序好的有序表中。

1, sorted数组的第0个位置没有放数据。

2，从sorted第二个数据开始处理：

如果该数据比它前面的数据要小，说明该数据要往前面移动。

a，首先将该数据备份放到 sorted的第0位置当哨兵。

b，然后将该数据前面那个数据后移。

c，然后往前搜索，找插入位置。

d，找到插入位置之后讲 第0位置的那个数据插入对应位置。

O(n*n), 当待排记录序列为正序时，时间复杂度提高至O(n)。

实例：

• 希尔排序（缩小增量排序 diminishing increment sort）：

先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

实例：

插入排序Java代码：

public class InsertionSort {//   插入排序：直接插入排序，希尔排序        public void straightInsertionSort(double [] sorted){ int sortedLen= sorted.length; for(int j=2;j
    
     =0;k--){ if(sorted[k]>sorted[0]){ sorted[k+1]=sorted[k]; }else{ insertPos=k+1; break; } } sorted[insertPos]=sorted[0]; } } } public void shellInertionSort(double [] sorted, int inc){ int sortedLen= sorted.length; for(int j=inc+1;j
     
      =0;k-=inc){ if(sorted[k]>sorted[0]){ sorted[k+inc]=sorted[k]; //数据结构课本上这个地方没有给出判读，出错： if(k-inc<=0){ insertPos = k; } }else{ insertPos=k+inc; break; } } sorted[insertPos]=sorted[0]; } } } public void shellInsertionSort(double [] sorted){ int[] incs={ 7,5,3,1}; int num= incs.length; int inc=0; for(int j=0;j