即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

插入排序:2路插入排序原理解析及源码演示

编程语言 scuyxi 11℃ 0评论
本文目录
[隐藏]

1.原理

2路插入排序是在直接插入排序的基础上进行优化:减少排序过程中元素移动的次数。不过需要额外增加n个辅助空间。

2.关键思路

把新增的辅助空间(n个元素的数组),当做一个环对待,再第一个元素插入之后(标记当前最大最小元素),以后分别从两边插入数据,比最大元素大的放右边,比最大元素小的放左边。


如果大于最小,小于最大,则按照常规插入排序的思路,把最大的元素依次往右边移动,直到找到合适的位置。

3.源码

template <class T>

//2_insert_sort
int sort(T* t, int n)
{
    int comp_times = 0;
    T *tmp = new T[n];
    tmp[0] = t[0];
    int big = 0, small = 0;
    for(int i=1; iif(current >= tmp[big])
        {
            big = (big + 1 + n) % n;
            tmp[big] = current;
            comp_times++;
        }
        else if(current <= tmp[small])
        {
            small = (small - 1 + n) % n;
            tmp[small] = current;
            comp_times++;
        }
        else
        {
            int p = (big + 1 + n) % n;
            while(tmp[(p - 1 + n) % n] > current)
            {
                tmp[(p + n) % n] = tmp[(p - 1 + n) % n];
                p = (p - 1 + n) % n;
                comp_times++;
            }
            tmp[(p + n) % n] = current;
            big = (big + 1 + n) % n;
        }
    }
    for(int k=0; kdelete[] tmp;
    return comp_times;
}

运行结果:


这里写图片描述

4.时间复杂度

o(n2)




最好情况下:

o(n)

如:已经有序的情况

9 7 5 3 2 1

或者:(不会遇到比最大元素小比最小元素大的情况)

8 7 6 5 9 4 3

5.空间复杂度

由于借助了辅助空间,空间复杂度为:


o(n)

转载请注明:CodingBlog » 插入排序:2路插入排序原理解析及源码演示

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情