查看“插入类排序”的源代码


===1）直接插入排序===
即当插入第i个记录时，R<sub>1，</sub>R<sub>2</sub>，...，R<sub>i-1</sub>均已排好序，因此，将第i个记录R<sub>i</sub>依次与R<sub>i-1</sub>，...，R<sub>2</sub>，R<sub>1</sub>进行比较，找到合适的位置插入。它简单明了，但速度很慢。[[文件:直接插入排序.png|无|缩略图|300x300像素|链接=http://www.jihongchang.top/index.php/%E6%96%87%E4%BB%B6:%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F.png]]<syntaxhighlight lang="c">
void insertSort(int data[], int n)
{
    //用直接插入排序法将data[0]~data[n-1]中的n个整数进行升序排列
    int i,j,tmp;
    for(i=1; i<n;i++)
    {
        if(data[i]<[i-1]){
            //将data[i]插入有序子序列data[0][i-1]
            tmp=data[i];
            for(j=i-2;j>=0&&data[j]>tmp;j--){
                //查找插入位置并将元素后移
                data[j+1]=data[j];
            }

            //插入正确位置
            data[j+1]=tmp;
        }//end if
    }//end for
}//end insertSort
</syntaxhighlight>如果数列基本有序，使用直接插入排序是比较有优势的。


===2）希尔（shell）排序===
https://www.bilibili.com/video/BV1hg411V7Bm/?p=68

先取一个小于n的证书d<sub>1</sub>作为第一个增量，把文件的全部记录分成d<sub>1</sub>个组。

所有距离为d<sub>i</sub>的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d<sub>2</sub><d<sub>1</sub>重复上述的分组和排序，直至所取的增量d<sub>t</sub>=1(d<sub>t</sub><d<sub>t-i</sub><O<d<sub>2</sub><d<sub>1</sub>)，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。[[文件:希尔排序.png|无|缩略图|600x600像素|链接=http://www.jihongchang.top/index.php/%E6%96%87%E4%BB%B6:%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F.png]]希尔排序是不稳定排序。

===考点：排序类型判断===
未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法为（）。

A、插入排序  A

B、选择排序

C、快速排序

D、冒泡排序