插入类排序

1）直接插入排序

即当插入第i个记录时，R_1，R₂，...，R_i-1均已排好序，因此，将第i个记录R_i依次与R_i-1，...，R₂，R₁进行比较，找到合适的位置插入。它简单明了，但速度很慢。

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

如果数列基本有序，使用直接插入排序是比较有优势的。

2）希尔（shell）排序

https://www.bilibili.com/video/BV1hg411V7Bm/?p=68

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

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

该方法实质上是一种分组插入方法。

希尔排序是不稳定排序。

考点：排序类型判断

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

A、插入排序 A

B、选择排序

C、快速排序

D、冒泡排序