请选择 进入手机版 | 继续访问电脑版

石家庄老站长

点击联系客服
客服QQ:509006671 客服微信:mengfeiseo
 找回密码
 立即注册
查看: 16|回复: 0

算法介绍的经典算法:半插入排序整体分析

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-4-15 14:40:09 | 显示全部楼层 |阅读模式
此前,博主是经过实战开发经验投身训练事业的“山猪”,以动画片《狮子王》的“砰砰”的外号,总是以乐观积极的心态对待周围的事物。本人的技术路线从Java全栈工程师走向大数据开发、数据挖掘领域,现在终于有了可塑性。我想和大家交流一两次过去的成果。希望对学习道路有帮助。(大卫亚设,Northern  Exposure(美国电视),)与此同时,博主们想通过这次尝试建立一个完美的技术图书馆。与文章技术点相关的异常、错误和注意事项都记录在末尾。请以各种方式提供素材。

请批评文章中发生的任何错误,一定要及时纠正。如果您有想讨论和学习的问题,请联系我:zhuyc@vip.163.com。文章发表风格取决于专栏,都是自己的体系。不足之处请大家指出。(大卫亚设,北方执行部队)算法导论之经典算法:折半插入排序全面解析

本文关键字:算法导论、经典算法、插入排序、折半插入排序、算法实践

文章目录

算法介绍的经典算法:半插入排序整体分析1,算法1。算法定义2。补充的概念2,插入排序1。插入排序简介2。半插入排序3。伪代码3,算法实践1。算法实现2。时间复杂性3。空间复杂性

一、什么是算法

该列为《手撕算法》列的子列《算法导论》。对几种经典算法进行了说明和分析。在此之前,我们应该先知道什么是算法,能解决什么问题。

1. 算法的定义

以下是经典教材《Introduction.to.Algorithms》改编的内容。

Informally,an  algorithm  is  any  well-dened  computational  procedure  that  takes  some  value,or  set  of  values,as  input  and  produces

明确定义的所有计算过程都可以称为算法。也就是说,使用值或值集作为输入,并生成值或值集作为输出。因此,算法可以说是将输入转换为输出的一系列计算步骤。

这种概括是比较标准和抽象的,但其实说得清楚的是阶段明确的问题解决方法。因为在计算机上运行,所以通常用伪代码表示,清楚地表达想法和步骤,所以实际运行时可以用其他语言达到相同的效果。

综上所述,算法是解决问题的工具。在解释算法时,我们的重点是输入和3358www.sina.com/。也就是说,只要明确说明原始数据和结果数据,算法做的事情也会变得明确。当我们设计算法时,我们首先要明确我们拥有什么。
我们要什么,这一点相信大家在后面的文章中会慢慢体会到。

2. 补充的概念
  • 数据结构
    算法经常会和数据结构一起出现,这是因为对于同一个问题(如:排序),使用不同的数据结构来存储数据,对应的算法可能千差万别。所以在整个学习过程中,也会涉及到各种数据结构的使用。
    常见的数据结构包括:数组、堆、栈、队列、链表、树等等。

  • 算法的效率
    在一个算法设计完成后,还需要对算法的执行情况做一个评估。一个好的算法,可以大幅度的节省运行的资源消耗和时间。在进行评估时不需要太具体,毕竟数据量是不确定的,通常是以数据量为基准来确定一个量级,通常会使用到时间复杂度空间复杂度这两个概念。

  • 时间复杂度
    通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句(赋值、判断、四则运算等基础操作)。我们可以把时间频度记为T(n),它与算法中语句的执行次数成正比。其中的n被称为问题的规模,大多数情况下为输入的数据量。
    对于每一段代码,都可以转化为常数或与n相关的函数表达式,记做f(n)。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式,在合并后保留量级最大的部分即可确定时间复杂度,记做O(f(n)),其中的O就是代表数量级
    常见的时间复杂度有(由低到高):O(1)、O(
       
         
          
          
            
             
              log
             
             
              ⁡
             
            
            
             2
            
          
          
            n
          
          
          
           \log _{2} n
          
         
        log2​n)、O(n)、O(
       
         
          
          
            n
          
          
            
             
              log
             
             
              ⁡
             
            
            
             2
            
          
          
            n
          
          
          
           n\log _{2} n
          
         
        nlog2​n)、O(
       
         
          
          
            
             n
            
            
             2
            
          
          
          
           n^{2}
          
         
        n2)、O(
       
         
          
          
            
             n
            
            
             3
            
          
          
          
           n^{3}
          
         
        n3)、O(
       
         
          
          
            
             2
            
            
             n
            
          
          
          
           2^{n}
          
         
        2n)、O(n!)。

  • 空间复杂度
    程序从开始执行到结束所需要的内存容量,也就是整个过程中最大需要占用多少的空间。为了评估算法本身,输入数据所占用的空间不会考虑,通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如:如果需要借助一个临时变量来进行两个元素的交换,则空间复杂度为O(1)。

  • 伪代码约定
    伪代码是用来描述算法执行的步骤,不会具体到某一种语言,为了表达清晰和标准化,会有一些约定的含义:
    缩进:表示块结构,如循环结构或选择结构,使用缩进来表示这一部分都在该结构中。
    循环计数器:对于循环结构,在循环终止时,计数器的值应该为第一个超出界限的值。
    to:表示循环计数器的值增加。
    downto:表示循环计数器的值减少。
    by:循环计数器的值默认变化量为1,当大于1时可以使用by。
    变量默认是局部定义的
    数组元素访问:通过"数组名[下标]"形式,在伪代码中,下标从1开始("A[1]“代表数组A的第一个元素)。
    子数组:使用”…"来代表数组中的一个范围,如"A[i…j]"代表从第i个到第j个元素组成的子数组。
    对象与属性:复合的数据会被组织成对象,如链表包含后继(next)和存储的数据(data),使用“对象名 + 点 + 属性名”。
    特殊值NIL:表示指针不指向任何对象,如二叉树节点无子孩子可认为左右子节点信息为NIL。
    return:返回到调用过程的调用点,在伪代码中允许返回多个值。
    and和or:与运算和或运算默认短路,即如果已经能够确定表达式结果时,其他条件不会去判断或执行。

    二、插入排序
    1. 插入排序介绍
    插入排序的基本思路是每次插入一个元素,每一趟完成对一个待排元素的放置,直到全部插入完成。

  • 直接插入排序
    直接插入排序是一种最简单的排序方法,过程就是将每个待排元素逐个插入到已经排好的有序序列中。
    文章传送门:算法导论之经典算法:直接插入排序全面解析。

  • 折半插入排序
    由于在插入排序的过程中,已经生成了一个(排好的元素组成的)有序数列。所以在插入待排元素时可以使用折半查找的方式更快速的确定新元素的位置,当元素个数较多时,折半插入排序优于直接插入排序

  • 希尔排序
    希尔排序可以看做是分组插入的排序方法,把全部元素分成几组(等距元素分到一组),在每一组内进行直接插入排序。然后继续减少间距,形成新的分组,进行排序,直到间距为1时停止。

    2. 折半插入排序
  • 输入
    n个数的序列,通常直接存放在数组中,可能是任何顺序。

  • 输出
    输入序列的一个新排列,满足从小到大的顺序(默认讨论升序,简单的修改就可以实现降序排列)。

  • 算法说明
    每次从原有数据中取出一个数,插入到之前已经排好的序列中,直到所有的数全部取完,那么新的有序排列也就完成了。这个过程与直接插入排序十分类似,不同的地方在于插入时如何寻找位置。

    [ol]
  • 直接插入排序:从后(排好的最后一个元素)至前逐一比较寻找位置。
  • 折半插入排序:利用已排好的元素有序的特点,使用折半查找的方式快速确定位置。[/ol]
    对于折半查找的详细步骤,可直接查看文章:算法导论之经典算法:折半查找全面解析。

  • 算法流程
    以下图片取材自《数据结构简明教程》:



    [ol]
  • 输入数据集被分为有序区无序区两部分。
  • 最初有序区没有元素,从无序区不断取出元素放入,保证放入的元素均已有序。
  • 已知前i个元素已排好(下标从0至i-1),从无序区取出第一个元素(数据集的第i + 1个元素)。
  • 先与有序区的最后一个元素比较
      [ol]
  • 如果较大则代表该元素已经在合适的位置,则直接归入有序区,进入下一个元素的判断。
  • 如果较小则需要进一步确定位置,执行以下步骤。[/ol]
  • 搜索区间为从lowhigh,初始区间为整个有序区(从0至i-1)。
  • 将待插入元素记录在临时变量tmp中,为后续的元素串位做准备。
  • 计算mid = (low + high) / 2,将该位置的元素与 **R **比较。
  • 不断的缩小搜索区间,直到确定插入位置(原理与折半查找相同)。
  • 确定位置后,将有序区中的元素从后至前逐个后串,最后将tmp中的值覆盖到插入位置。[/ol]
    3. 伪代码
    折半插入排序可以看做是将直接插入排序折半查找两种算法进行结合,排序的思路与直接插入排序相同,只是在确定插入位置时借助了折半查找的方法(不考虑集合中有重复元素的情况)。

    for i = 2 to A.length
        if A  tmp
                    high = mid - 1
                else
                    low = mid + 1
            for j = i - 1 downto high + 1
                A[j + 1] = A[j]
            A[high + 1] = tmp

    由于不会出现重复元素,所以最后一定会将搜索区间缩小至low与high重合(左右区间端点不断移动)。在最后一次循环时,lowhigh的值相同,在比较完成后,left与right发生交错,相差为1,此时要选择一个变量的值作为新插入元素的位置参照。
    需要明确的是,最后一次比较时不会出现左端点向左移或右端点向右移的情况,因为在上一次比较时,待插入元素必定是能够落在low与high的区间内的,这就决定了tmp一定大于low对应的元素,小于high对应的元素。
    并且由于mid的计算方法,最后一次比较是tmp与low对应元素的比较,并且tmp(待插入元素)是较大的,此时进else分支。并且我们知道最终的插入位置应该放在最后比较元素的后一个位置,也就是mid对应位置的后面,所以是mid + 1
    如果用low表示,就刚好是low,如果用right表示,则应该是high + 1

    三、算法实践
    1. 算法实现
  • 输入数据(input):11,34,20,10,12,35,41,32,43,14
  • Java源代码
    public class BinaryInsert {
        public static void main(String[] args) {
            // input data
            int[] a = {11,34,20,10,12,35,41,32,43,14};
            // 数组下标从0开始,j初始为1,指向第二个元素
            for (int i = 1;i  a.length;i++){
                if (a  a[i - 1]){
                    // 使用temp记录当前元素的值
                    int tmp = a;
                    // 初始化变量
                    int left = 0;
                    int right = i - 1;
                    // while循环作用:使用二分查找确定元素位置,并串出对应的位置
                    while(left  right){
                        // 取中间元素,以下写法防止数据量较大时发生溢出
                        int mid = (right - left) / 2 + left;
                        if(a[mid] > tmp){
                            // 待排元素较小,将搜索区间缩小至左一半
                            right = mid - 1;
                        }else {
                            // 待排元素较大,将搜索区间缩小至右一半
                            left = mid + 1;
                        }
                    }
                    // 将待排元素放在对应的位置
                    for (int j = i - 1;j >= right + 1;j--){
                        a[j + 1] = a[j];
                    }
                    a[right + 1] = tmp;
                }
            }
            // 查看排序结果
            for (int data : a){
                System.out.print(data + "\t");
            }
        }
    }

  • 执行效果


    2. 时间复杂度
    对于折半插入排序来说,由于元素的串位次数没有发生变化,只是在查找位置是更加快速了,所以总得来说与直接插入排序处于同一量级,在数据量很大时,要优于直接插入排序。

  • 最坏的情况
    如果输入的元素刚好是反向有序的,那么每次都需要进行位置的查找,但是在查找的次数要少一些。可以知道,由于区间每次缩小一半,可以得到寻找位置的次数最多为
         
          
          
            
             
             
               log
             
             
               ⁡
             
             
             
              2
             
            
            
             i
            
          
          
            \log _{2} i
          
          
         log2​i
    量级,但是由于移动元素的次数没变,时间复杂度依然是 O(
         
          
          
            
             
              n
             
             
              2
             
            
          
          
            n^{2}
          
          
         n2)


  • 最好的情况
    最好的情况与直接插入排序相同,如果元素已经是正向有序的,那么在最开始比较的时候就会认为在合适的位置,不需要再进行位置的寻找和串位,因此时间复杂度为O(n)

  • 平均情况
    综合两种情况,插入排序的时间复杂度为O(
         
          
          
            
             
              n
             
             
              2
             
            
          
          
            n^{2}
          
          
         n2)


    3. 空间复杂度
    算法执行过程中直接在原集合上操作,只需要几个额外的变量记录关键信息,所以空间复杂度为常数级:O(1)

  • 回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|无图版|手机版|小黑屋|石家庄@IT精英团

    GMT+8, 2021-5-15 02:38 , Processed in 0.048830 second(s), 19 queries .

    Powered by Discuz! X3.4

    © 2001-2021 Comsenz Inc.

    快速回复 返回顶部 返回列表