直接插入排序法

时间:2021-11-22 15:29:45

直接插入排序(straight insertion sort)是一个简单的排序方法,他的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表。

例如,已知待排序的一组记录初始排列如下:
      49,38,65,97,76,13,27,49 -----a

假设排序过程中,前4个记录已经有序,构成了一个有序列,如
      38,49,65,97 ----------b

现在要将第五个记录76插入到上面序列中,以得到一个新的含5个记录的有序序列。在b序列中进行查找以确定76应该插入的位置,然后进行插入。

假设从左开始查找,则76应该插入到65和97之间。这就是一趟直接插入排序。

一般情况下,第i趟直接插入排序操作为:在含有i-1个序列中有序子序列中插入一个新记录,变成含有i个有序序列的子序列

和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r【0】位置设置监视哨。

在自i-1起往前搜索的过程中,可以同时后移记录。

整个排序过程为进行n-1趟插入,即:先将序列中第1个记录看成是一个有序的子序列,然后从第二个记录器开始逐个插入,直至整个序列变成关键字非递减有序序列为止

-------------------------
void InsertSort(SqList @l)
{
for( i = 2 ; i <= l.length; ++i)
{
if(LT(l.r[i].key,l.r[i-1].key))//小于,将l.r[i]插入有序表
{
l.r[0] = l.r[i];//复制为哨兵
l.r[i] = l.r[i-1];
for( j = i - 2; lt(l.r[0].key,l.r[j].key) ; --j)
    l.r[j+1] = l.r[j];//记录后移
l.r[j+1] = l.r[0];//插入到正确位置
}
}
}

*********************************************************************************************

插入排序用的是顺序结构来描述,也就是数组结构来描述。
通过比较大小以后,要把一个合适的数据插入到数组的某个位置上来,但是因为是数组结构,要添加某个数据到数组的某个
位置上,就必须把这个位置给空余出来。所以就要把这个位置以及这个位置以后的数据全部后移,这样才会空出这个位置来
然后把数据赋值给这个位置,这也就是代码中内层for循环的意义和作用。
数组的0位置起哨兵作用,数组中两两比较以后,较小就赋值给哨兵,哨兵就是要待插入的数据,因此只要比哨兵大的数据都应该向后移动,这样就能空余出来一个位置,让哨兵来填充



c#版本的直接插入排序算法。

static void Order(ref int[] array)
        {
            for (int i = 2; i < array.Length; ++i)
            {
                if (array[i] < array[i - 1])
                {
                    array[0] = array[i];
                    array[i] = array[i - 1];
                    int j = 0;
                    for ( j = i - 2; array[0] < array[j]; --j)
                    {
                        array[j + 1] = array[j];
                    }
                    array[j + 1] = array[0];
                }
            }
        }

本文使用Blog_Backup未注册版本导出,请到soft.pt42.com注册。