数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

0. 数据结构图文解析系列

数据结构系列文章

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

数据结构图文解析之:栈的简介及C++模板实现

数据结构图文解析之:队列详解与C++模板实现

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

数据结构图文解析之:AVL树详解及C++模板实现

数据结构图文解析之:二叉堆详解及C++模板实现

数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

数据结构图文解析之:二分查找及与其相关的几个问题解析

1. 插入排序简介

插入排序是一种简单直观的排序算法,它也是基于比较的排序算法。它的工作原理是通过不断扩张有序序列的范围,对于未排序的数据,在已排序中从后向前扫描,找到相应的位置并插入。插入排序在实现上通常采用就地排序,因而空间复杂度为O(1)。在从后向前扫描的过程中,需要反复把已排序元素逐步向后移动,为新元素提供插入空间,因此插入排序的时间复杂度为O(n^2);

2. 直接插入排序图解

一般来说,插入排序都采用在数组上就地排序实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

假设我们要对数组{12,4,5,2,6,14}进行插入排序,排序过程为:

2.1. 代码实现

template <typename T>
void InsertSort(T array[],int length)
{
    if (array == nullptr || length < 0)
        return;
    int i, j;
    for (i = 1; i < length; i++)
    {
        if (array[i]<array[i - 1])
        {
            int temp = array[i];     
            for (j = i - 1; array[j]>temp; j--) //元素后移
            {
                array[j + 1] = array[j];
            }
            array[j+1] = temp;        //在合适的位置上出入元素
        }
    }
}

2.2. 复杂度分析

  • 插入排序的最好情况是数组已经有序,此时只需要进行n-1次比较,时间复杂度为O(n);
  • 最坏情况是数组逆序排序,此时需要进行n(n-1)/2次比较以及n-1次赋值操作(插入);
  • 平均来说插入排序算法的复杂度为O(n^2)。

插入排序不适合对大量数据进行排序应用,但排序数量级小于千时插入排序的效率还不错,可以考虑使用。插入排序在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。

直接插入排序采用就地排序,空间复杂度为O(1).

2.3. 稳定性

直接插入排序是稳定的,不会改变相同元素的相对顺序。

3. 二分查找插入排序

上面的插入排序实现中,为了找到元素的合适的插入位置,我们采用从后到前遍历的顺序查找进行比较,为了减少比较的次数,我们可以换种查找策略:采用二分查找。 我们定义一个二分查找函数,函数返回插入位置的下标:

/*二分查找函数,返回插入下标*/
template <typename T>
int BinarySearch(T array[], int start, int end, T k)
{
    while (start <= end)
    {
        int middle = (start + end) / 2;
        int middleData = array[middle];
        if (middleData > k)
        {
            end = middle - 1;
        }
        else
            start = middle + 1;
    }
    return start;
}
//二叉查找插入排序
template <typename T>
void InsertSort(T array[], int length)
{
    if (array == nullptr || length < 0)
        return;
    int i, j;
    for (i = 1; i < length; i++)
    {
        if (array[i]<array[i - 1])
        {
            int temp = array[i];
            int insertIndex = BinarySearch(array, 0,i, array[i]);//使用二分查找在有序序列中进行查找,获取插入下标
            for (j = i - 1; j>=insertIndex; j--) //移动元素
            {
                array[j + 1] = array[j];   
            }       
            array[insertIndex] = temp;    //插入元素
        }
    }
}

3.2. 复杂度分析

我们这个二分查找的算法并不会因为等于某一个值而停止查找,它将查找整个序列直到start<=end条件不满足而得到插入的位置,所以对于长度为n的数组来说,比较次数为log2n ,时间复杂度为O(log2n)。二分插入排序的主要操作为比较+后移赋值,则:

  • 最坏情况:每次都在有序序列的起始位置插入,则整个有序序列的元素需要后移,时间复杂度为O(n^2)
  • 最好情况:待排序数组本身就是正序的,每个元素所在位置即为它的插入位置,此时时间复杂度仅为比较时的时间复杂度,为O(log2n)
  • 平均情况:O(n^2)

空间复杂度上, 二分插入排序也是就地排序算法,它的空间复杂度为O(1).

3.3. 稳定性

二分插入排序是稳定的。元素的相对顺序在排序后不会被改变。

原创文章,转载请注明: http://www.cnblogs.com/QG-whz/p/5194569.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

使用数字进行字符遍历

有些时候使用数字进行遍历,然后将数字转化成需要的进制数,再将进制数对应成需要的字符是一种非常有效的方法。 如: 输入一个正整数X,在下面的等式左边的数字之间添加...

233100
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

31070
来自专栏ACM算法日常

基础算法|6 折半插入排序 - HDU 1412

我们之前已经了解了5种基础算法,是否自己找了一些题练练手呢~话不多说,让我们进入第6中基础算法的学习吧。本篇我们将学习又一种排序算法——折半插入排序算...

12340
来自专栏desperate633

LintCode 搜索插入位置题目分析代码

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

9530
来自专栏数据结构与算法

洛谷P2181 对角线(组合数)

题目描述 对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: ? 输入输出格式 输入格式: 第一行一个...

36650
来自专栏小L的魔法馆

C++继承与多态练习--计算图形面积

44890
来自专栏猿人谷

C语言函数指针基础

本文写的非常详细,因为我想为初学者建立一个意识模型,来帮助他们理解函数指针的语法和基础。如果你不讨厌事无巨细,请尽情阅读吧。 函数指针虽然在语法上让人有些迷惑,...

450100
来自专栏大闲人柴毛毛

动态规划法(三)——最长公共子序列

问题描述 给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子...

38440
来自专栏技术博文

PHP实现经典算法

前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序。 $arr = array(1,43,54,62,21,6...

28440
来自专栏PHP在线

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

46080

扫码关注云+社区

领取腾讯云代金券