插入排序

一、简单插入排序

插入排序将数组分为排序区和乱序区，排序过程中每次从乱序区中选择一个元素放入排序区，直到乱序区没有元素

1
2
3
4
5
6
7
8
9
10
11
void insertion(vector<int>& nums)
{
    int size = nums.size();
    for (int i = 1; i < size; i++)
    {
        for (int j = i; j > 0 && （nums[j] < nums[j-1]）; j--)
        {
            swap(nums, j, j - 1);
        }
    }
}

二、优化

1. 融合二分查找

使用二分查找快速查找新元素在排序区的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//哨兵和二分查找相结合的插入排序
void insert_sort( vector<int>& nums )
{
    int target;
    int k;
    for ( int i = 1; i < size; ++i )
    {
        target = nums[i];
        //找到target应该插入的位置
        k = bin_search( nums, 0, i, target );
        for ( int j = i-1; j >= k; --j )
        {
            nums[j+1] = nums[j];
        }
        nums[k] = target;
    }
}

2. 加入哨兵位

在将新元素插入排序区使用哨兵位避免频繁交换元素的开销

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//带哨兵的插入排序
void insert_sort( vector<int>& nums )
{
    int size = nums.size();
    int sentry;
    for ( int i = 1; i < size; ++i )
    {
        sentry = nums[i];
        for ( int j = i-1; j >= 0; j-- )
        {
            if ( sentry < array[j] )
                nums[j+1] = nums[j];
            else break;
        }
        if ( j+1 != i )
            nums[j+1] = sentry;
    }
}

三、性能分析

  • 时间复杂度：O(N2)
  • 空间复杂度：O(1)
  • 排序方式：原地
  • 稳定性：稳定
数据结构和算法 算法 排序
笔记 比较排序

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！