首页 > 编程学习 > 8.2 数据结构——插入排序

8.2 数据结构——插入排序

发布时间:2022/11/27 11:05:37

1、基本思想:每步将一个排序的对象,按其关键码大小插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。即边插入边排序,保证子序列中随时都是有序的。

2、基本操作:

(1)在有序序列中插入一个元素,保持序列有序,有序长度不断增减;

(2)起初,a[0]是长度为1的子序列。然后逐一将a[1]到a[n-1]插入到有序子序列中;

(3)在插入a[i]前,数组a的前半段(a[0]~a[i-1])是有序段,后半段(a[i]~a[n-1])是停留在输入次序的“无序段”;

(4)插入a[i]使a[0]~a[i-1]有序,也就是要为a[i]找到有序位置j(0 <= j <= i),将a[i]插入到a[j]的位置上。

3、插入排序的分类

(1)直接插入排序:顺序法定位插入位置

(2)二分插入排序:二分法定位插入位置

(3)希尔排序:缩小增量多遍插入排序

8.2.1 直接插入排序

 1、复制插入元素, x = a[i];

2、记录后移,查找插入位置;

for (int j = i - 1; j >= 0 && x < a[j]; j--)
{
    a[j+1] = a[j];
}

3、插入到正确位置 a[j+1] = x;

使用哨兵的方式:

 1、复制为哨兵 L->r[0] = L->r[i];

2、记录后移,查找插入位置

for (int j = i - 1; L->r[0].key < L->r[i].key; --j)
{
    L->r[j+1] = L->r[j];
}

 3、插入到正确位置,L->r[j+1] = L->r[0]

直接插入排序算法:

void InsertSort(SQList *L)
{
    for (int i = 2; i <= L->length; i++)
    {
        if (L->r[i]->key < L->r[i-1].key)
        {
            L->r[0] = L->r[i]
            for (int j = i - 1; L->r[0].key < L->r[j].key; j--) //记录后移,找到插入位置
            {
                L->r[j+1] = L->r[j];
            }
            L->r[j+1] = L->r[0];
        }
    }
}

8.2.2 折半插入排序

查找插入位置时采用折半查找法

折半插入排序算法

void BInsertSort(SQList *L)
{
    for (int i = 2; i <= L->length; i++)
    {
        L->r[0] = L->[i];
        int low = 1, high = i - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (L->r[0].key < L->r[mid].key)
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (int j = i - 1; j >= high + 1; j--)
        {
            L->r[j+1] = L->r[j];    
        }
        L->r[high + 1] = L->r[0];
    }
}

 8.2.3 希尔排序(Donald.L.Shell)

基本思想:先将整个待排记录序列分割成若干个子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,在对全部记录进行一次直接插入排序。

希尔排序的特点:

(1)缩小增量,(2)多遍插入排序

希尔排序的思路

(1)定义增量序列Dk:Dm > Dm-1 > ... >D1 = 1

(2)对每个Dk进行“Dk间隔”插入排序(K= M,M-1,...,1)

希尔排序的特点:

(1)一次移动,移动位置较大,跳跃式地接近排序的最终位置; 

(2)最后一次只需要少量移动

(3)增量序列必须是递减的,最后一个必须是1

(4)增量序列应该是互质的

希尔排序算法(主程序):

void ShellSort(SQList *L, int dlta[], int len)
{
    //按增量序列dlta[0~len-1]对顺序表L做希尔排序
    for (int k = 0; k < len; k++)
        ShellInsert(L, dlta[k]);
}

希尔排序(其中一趟的排序操作)

void ShellInsert(SQList *L, int dk)
{
    //对顺序表L进行一趟增量为dk的希尔排序,dk为步长因子
    for (int i = dk + 1; i <= L->length; i++)
    {
        if (L->r[i].key < L->r[i-dk].key)
        {
            L->r[0] = L->r[i];
            for (int j = i - dk; j > 0 && L->r[0].key < L->r[j].key; j = j-dk)
            {
                L->r[j+dk] = L->r[j];
            }
            L->r[j+dk] = L->r[0];
        }
    }
}

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式