Title Date Modified Category
insert sort 2019-07-09 12:00 2019-07-09 12:00 algorithm

1. insert sort

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表。

/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L)
{
    int i, j;
    for (i = 2; i < L->length; i++)
    {
        if (L->r[i] < L->r[i - 1]) /* 需将L->r[i]插入有序子表 */
        {
            L->r[0] = L->r[i]; /* 设置哨兵 */
            for (j = i-1; L->r[j] > L->r[0]; j--)
            {
                L->r[j+1] = L->r[j]; /* 记录后移 */
            }
            L->r[j+1] = L->r[0]; /* 插入到正确位置 */
        }
    }
}

1.1. 直接插入排序复杂度分析

从空间上来看,它只需要一个记录的辅助空间,因此关键是看它的时间复杂度。

当最好的情况,O(n)。

最坏的情况.

平均情况n^2/4。

直接插入排序法的时间复杂度为O(n^2).

同样的O(n^2)时间复杂度,直接插入排序法比冒泡和简单选择排序的性能要好一些。

2. 参考资料

2.1. books

  • 《大话数据结构》

results matching ""

    No results matching ""