插入排序

  1. —插入排序—
    1. 算法描述
    2. 代码实现
      1. 直接插入排序
      2. 二分法插入排序
    3. 算法分析
    4. 稳定性

—插入排序—

​ 插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法描述

具体算法描述如下:

  • <1>.将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

  • <2>.从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。

    (如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

插入排序

代码实现

直接插入排序

void Insert_Sort(int a[], int n)
{

// 将第一个元素定为有序序列,从第二个元素开始遍历
for (int i = 1; i < n; ++i)
{
    int key = a[i];    //从第二个元素开始移动
    int j = i - 1;     // 第一个元素的下标
    while (j >= 0 && a[j] > key)   // 若有序序列有元素值比大无序序列中大
    {
        a[j + 1] = a[j];        //比此元素大的所有有序元素往后移+1
        j--;                    
    }
    a[j + 1] = key;         // 将key放入合适位置
}

}

二分法插入排序

————————-有待填坑———————-

算法分析

  • 平均情况:T(n) = O(n2)

  • 最佳情况:输入数组按升序排列。T(n) = O(n)

  • 最坏情况:输入数组按降序排列。T(n) = O(n2)

稳定性

  • 稳定

    若元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。故顺序不变


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 351134995@qq.com

×

喜欢就点赞,疼爱就打赏