精华内容
下载资源
问答
  • 常见算法

    千次阅读 2016-10-08 22:52:58
     根据加密结果是否可以被解密,算法可以分为可逆加密和不可逆加密(单向加密),从这个意义上来说,单向加密只能称之为加密算法而不是加解密算法。对于可逆加密,又可以根据密钥的的对称性分为对称加密和非对称加密...

    算法分类

      根据加密结果是否可以被解密,算法可以分为可逆加密和不可逆加密(单向加密),从这个意义上来说,单向加密只能称之为加密算法而不是加解密算法。对于可逆加密,又可以根据密钥的的对称性分为对称加密和非对称加密。具体的分类结构如下:

    • 可逆加密
    • 对称加密:DES,3DES,AES,PBE
    • 非对称加密:RSA,DSA,ECC
    • 不可逆加密(单向加密):MD5,SHA,HMAC

    密钥介绍

      在详细介绍各种加解密算法之前,我们需要对“密钥”这一概念做一下简单介绍,方便我们对下面内容的展开。

      密钥在加解密算法中是一个参数,其长度根据不同的算法有所不同,同一算法的密钥长度也有可能有不同的要求。一般来说,密钥的长度与安全性成正比。在使用时,将明文(或密文)连同密钥放入相应的加密(或解密容器),即可得到密文(或明文),实现加解密。

      在加密算法诞生之初,密钥的形式为对称的,这是说,加密与解密的密钥是相同的。这样是符合我们的思维习惯的。但是,这里存在一个问题,就是密钥在传递或保存的过程中如果被窃取,那么黑客是很容易将密文解密获得正确的明文的。对称形式的密钥虽然简单高效,但是安全性不高。

      鉴于对称密钥的缺陷,人们又提出了一种新的密钥形式,非对称密钥。非对称密钥的加解密密钥不再相同,而是分为公钥和私钥,公钥用于加密,私钥用于解密。私钥是不公开不传送的,仅仅由通信双方持有保留;而公钥是可以公开传送的,甚至不担心丢失,因为即便公钥被窃取,黑客还是无法将密文解密为明文(这一功能由私钥提供)。可以看到,非对称密钥的安全性较对称密钥是更好的。

      非对称密钥还提供一种功能,即数字签名。通过私钥进行签名,公钥进行认证,达到身份认证的目的。

      需要说明的是,上面对于密钥的介绍均是基于可逆加密,对于不可逆加密,是不存在密钥概念的。

    模式介绍

      在详细介绍各种加解密算法之前,我们需要对“模式”这一概念做一下简单介绍,方便我们对下面内容的展开。

      对于可逆加密,在加密时可以选择加密模式,可以理解为加密算法可以有不同的工作方式,不同的工作方式之间存在效率、方式等方面的区别。要注意的是,对同一个数据,加密选择的模式与解密选择的模式必须相同,否则解密得不到正确的结果。

      Android可逆加密的模式主要有四种:ECB (电子密码本模式)、CBC(分组连接模式)、CFB(密码反馈模式)、OFB (输出反馈模式)。

    ECB (电子密码本模式):

      其使用方式是一个明文分组加密成一个密文分组,相同的明文分组永远被加密成相同的密文分组。直接利用加密算法分别对每个64位明文分组使用相同的64位密钥进行加密。每个明文分组的处理是相互独立的。

      缺点:在给定密钥k 下,同一明文组总是产生同一密文组,这会暴露明文组的数据格式。某些明文的数据格式会使得明文组有大量的重复或较长的零串,一些重要的数据常常会在同一位置出现,特别是格式化的报头、作业号、发报时间、地点等特征都将被泄露到密文之中,使攻击者可以利用这些特征。

      优点:用同个密钥加密的单独消息,其结果是没有错误传播。实际上,每一个分组可被看作是用同一个密钥加密的单独消息。密文中数据出了错,解密时,会使得相对应的整个明文分组解密错误,但它不会影响其他明文。然而,如果密文中偶尔丢失或添加一些数据位,那么整个密文序列将不能正确的解密。除非有某帧结构能够重新排列分组的边界。

    CBC(分组连接模式):

      对于相同的明文,加密结果不同。这就加大了密码破解者的破译难度。在密钥固定不变的情况下,改变每个明文组输入的链接技术,这样, 密文组不仅与当前的明文组有关,而且通过反馈的作用还与以前的明文组有关。这从密码学的本质上来说是一种混淆操作。

      优点:能隐蔽明文的数据模式; 在某种程度上能防止数据篡改, 诸如明文组的重放,嵌入和删除等.

      缺点:会出现错误传播(errorpropagation). 密文中任一位发生变化会涉及后面一些密文组. 但CBC 模式的错误传播不大, 一个传输错误至多影响两个消息组的接收结果,错误传播最多持续2个分组

    CFB(密码反馈模式):
      采用密文反馈的模式增强密文之间的相关性。若待加密的消息必须按字符比特处理时,可采用CFB。每次加密s bit 明文。(1<= s<= 原来的固有长度)

      优点:CFB 模式除有CBC 模式的优点外, 其自身独特的优点是它特别适用于用户数据格式的需要。

      缺点:一是对信道错误较敏感且会造成错误传播。CFB由于采用的是密文反馈,故若某个密文分组在传输中出现一位或多位的错误,将会引起当前分组和后续部分分组的解密错误。二是数据加密的速率降低。但这种模式多用于数据网中较低层次, 其数据速率都不太高。

    OFB (输出反馈模式):
      克服了CBC和CFB模式带来的错误传播问题,但对密文被篡改难于进行检测

    算法介绍

    单向加密

      前面说过,单向加密的结果是不可以被解密的,因此,单向加密的主要用途并不是传统意义上的加解密工作,而是对明文数据的保密和摘要提取。单向加密主要有MD5、SHA、HMAC等算法。

    特点

      1. 压缩性:任意长度的数据,单向加密后长度都是固定的。
      2. 抗修改性:对原数据进行任何改动,哪怕只修改1个字节,所得到的结果都有很大区别。
      3. 弱抗碰撞性:已知原数据和其单向加密结果,想找到一个具有相同结果的数据(即伪造数据)是非常困难的。
      4. 强抗碰撞性:想找到两个不同的数据,使它们具有相同的单向加密结果,是非常困难的。
      5. 简单高效:对数据进行单向加密处理速度是很快的。

    注:上述特点是基于某一特定单向加密算法而言,不同的单向加密算法之间有区别

      我们可以看到,单向加密对数据加密结果的一致性是有较高的保证的,也就是,对一个数据进行加密,想要伪造一个数据去得到相同的结果,几乎是不可能的。同时,由于单向加密速度较快而且加密结果长度一定,常常将单向加密的结果作为生成可逆加密中密钥的第一个步骤,这个我们在后文中会讲到。

    • 应用:

    1. 数据加密,安全访问认证

      这是单向加密最广泛的用途。具体来说,就是对用户密码的保护。我们在登陆一个网站或应用时,常常需要输入自己的密码或者要求客户端或浏览器帮助我们保存密码。但是,密码是不能明文传输验证或保存的。这是因为用户往往是一个密码用于多个网站甚至银行,一旦其中的某一个网站泄露了用户密码,那么该用户的其他网站信息也会存在被窃取的可能。因此,一般的做法为在用户登录验证或保存密码时,先对密码明文做一次单项加密,然后将该结果与服务器端的用户密码单向加密结果进行比对,如果一致则允许访问,否则拒绝。例如,2012年QQ的记住密码功能就是将用户的密码进行了一次MD5加密,然后存在了本地的数据库中。

      可能有读者会意识到,既然单向加密对同一明文的加密结果永远不变,那么如果用户的密码不变,黑客只要拿到加密后的结果就可以随意登陆对应网站了,安全性又如何保证呢?确实是这样的。这就要求工程师在设计登陆或保存密码策略时,尽量不要泄漏加密算法的选择;另一方面,也可以采取一些特别的手段来对加密对象进行处理,比如对密码加“盐”。加盐的思想会在后面对HMAC的介绍中有所体现。

    2.文件完整性验证,数字签名

      有时候,我们需要对文件或者数据是否被篡改进行确认,用到的就是单向加密技术,主要是基于单向加密的压缩性、抗修改性和简单高效性。在这里举一个例子,便于读者理解。有事我们下载了一个镜像之后,会发现下载页面还提供了一组 MD5 值,这组 MD5 值是用来验证文件的一致性的,当我们下载好镜像之后,需要对该镜像做一次 MD5 的校验,得到的 MD5 值与下载页面提供的 MD5 值进行对比,以此来验证该镜像是否被篡改。

    • 安全性:

      单向加密的安全性主要取决于加密结果的长度,对于同一加密算法,安全性与加密结果的长度成正比。单向加密是存在被破解的可能的,主要有暴力破解、查字典法破解和社会工学破解等。但破解成本很高而且需要的时间较长,如果不是极重要的数据,几乎没有破解的必要。

    • 算法分类:
    1. MD5:
        MD5是应用最广泛的一种单向加密算法,其在数据加密、安全访问认证和文件完整性验证等方面都有应用。MD5加密输出是一个128位的十六进制数字串。Android SDK提供了MD5的使用接口,使用时直接调用即可。示例如下:

           MessageDigest md5 = MessageDigest.getInstance("MD5"); //获得MD5加密实例 
           md5.update(stringToEncrypt.getBytes());  
           byte[] encrypted = md5.digest();//加密返回值为byte[]数组
    2. SHA:
        SHA实际上是一组加密算法的合称,包括SHA-1,SHA-256,SHA-384,SHA-512。其中应用最广的是SHA-1,HTTPS中使用的HASH散列函数多使用SHA-1。相比较于MD5,SHA族有更高的安全性,到目前为止还没有人能破译其加密结果,但其加密速度比MD5慢,是以速度换取了安全性。另一方面,SHA对加密的数据有一定的长度限制。具体各SHA算法的比较如下表格:

      对于SHA算法,Android SDK也提供了相应接口,方便开发者使用。与MD5类似,以SHA-1为例:

            MessageDigest sha = MessageDigest.getInstance("SHA-1"); //获得SHA-1加密实例 
            sha.update(stringToEncrypt.getBytes());  
            byte[] encrypted = sha.digest();//加密返回值为byte[]数组
    1. HMAC:
        HMAC不同于上面的传统单向加密算法,它的加密形式与可逆加密相同,加密过程需要一个密钥和一个消息为输入,生成一个消息摘要作为输出。定义HMAC需要一个加密用散列函数(表示为H,可以是MD5或者SHA-1)和一个密钥K。我们用B来表示数据块的字节数。(以上所提到的散列函数的分割数据块字长B=64),用L来表示散列函数的输出数据字节数(MD5中L=16,SHA-1中L=20)。鉴别密钥的长度可以是小于等于数据块字长的任何正整数值。应用程序中使用的密钥长度若是比B大,则首先用使用散列函数H作用于它,然后用H输出的L长度字符串作为在HMAC中实际使用的密钥。一般情况下,推荐的最小密钥K长度是L个字节,结合SHA-1的HMAC代码实现如下:

           SecretKeySpec secret = new SecretKeySpec(key.getBytes(), type);//key为开发者自己设定的密钥字符串
           Mac mac = Mac.getInstance("HmacSHA1");//SHA-1的HMAC
           mac.init(secret);
           byte[] digest = mac.doFinal(stringToEncrypt.getBytes());//加密返回值为byte[]数组

    对称加密

      对称加密算法,应用的时间比较早,技术相对来说比较成熟,在对称加密算法中,数据发信方将明文(原始数据)和加密密钥一起经过特殊加密算法处理后,使其变成复杂的加密密文发送出去。收信方收到密文后,若想解读原文,则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文。在对称加密算法中,使用的密钥只有一个,发收信双方都使用这个密钥对数据进行加密和解密,这就要求解密方事先必须知道加密密钥。对称加密算法的特点是算法公开、计算量小。不足之处是,交易双方都使用同样钥匙,安全性得不到保证。

    • 特点

      1. 密钥较小(一般小于256bit),密钥越大,加密越强,但加密解密越慢
      2. 优点:算法公开、计算量小、加密速度快、加密效率高,适用于大量数据的加密
      3. 缺点:密钥分配与管理,安全性较低
      4. 四种算法DES,3DES,AES,PBE
    • 算法

    1.DES:
      DES算法是一种分组加密机制,将明文分成N个组,然后对各个组进行加密,形成各自的密文,最后把所有的分组密文进行合并,形成最终的密文。把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是64位。

    • 简介:
      DES算法是这样工作的:
        如Mode为加密,则用Key 去把数据Data进行加密, 生成Data的密码形式(64位)作为DES的输出结果;
        如Mode为解密,则用Key去把密码形式的数据Data解密,还原为Data的明码形式(64位)作为DES的输出结果。
        在通信网络的两端,双方约定一致的Key, 在通信的源点用Key对核心数据进行DES加密,然后以密码形式在公共通信网(如电话网)中传输到通信网络的终点,数据到达目的地后,用同样的Key对密 码数据进行解密,便再现了明码形式的核心数据。这样,便保证了核心数据(如PIN、MAC等)在公共通信网中传输的安全性和可靠性。

    • 支持模式:
        ECB、CBC、CFB、OFB

      • 优缺点:

        (1)DES算法加密解密速度比较快,密钥比较短,加密效率很高但通信双方都要保持密钥的秘 密性,为了安全还需要经常更换DES密钥

        (2) 产生密钥简单,但安全性完全依赖密钥,密钥必须高度保密,因而难以做到一次一密

      • 应用:DES算法在POS、ATM、磁卡及智能卡(IC卡)、加油站、高速公路收费站等领域被广泛应用,以此来实现关键数据的保密,如信用卡持卡人的PIN的加密传输,IC卡与POS间的双向认证、金融交易数据包的MAC校验等,均用到DES算法。

      • 算法实现:Android的SDK提供了DES的接口,我们可以直接调用实现。DES算法的入口参数有三个:Key、Data、Mode。其中Key为8个字节共64位,是DES算法的工作密钥;Data也为8个字节64位,是要被加密或被解密的数据;Mode为DES的工作方式,有两种:加密或解密。

        加密:

          DESKeySpec dks = new DESKeySpec(key);//创建DESKeySpec对象,其中key为64位的密钥  
          SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("DES");//DES密钥工厂实例    
          SecretKey securekey = keyFactory.generateSecret(dks);
          Cipher cipher = Cipher.getInstance("DES/ECB/PKCS5Padding");//密钥容器的实例。传入的参数依次为加密算法,加密模式,填充模式(可选NOPadding,PKCS5Padding,PKCS7Padding)
          cipher.init(Cipher.ENCRYPT_MODE, securekey);//初始化密钥容器。加密时第一个参数必须是Cipher.ENCRYPT_MODE
          byte[] encryptResult=cipher.doFinal(stringToEncrypt.getBytes());

        解密:

          DESKeySpec dks = new DESKeySpec(key);//key必须与加密时保持一致  
          SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("DES");
          SecretKey securekey = keyFactory.generateSecret(dks);
          Cipher cipher = Cipher.getInstance("DES/ECB/PKCS5Padding");//传入的参数必须与加密时保持一致
          cipher.init(Cipher.DECRYPT_MODE, securekey);//解密时第一个参数必须是Cipher.DECRYPT_MODE
          byte[] decryptResult=cipher.doFinal(encryptResult.getBytes());

    2.3DES:
      3DES算法是在DES的基础上发展出来的。在一些对安全性要求较高的场景下,DES的64位密钥安全性不能满足要求,于是人们采取了一种“简单暴力”的办法——三重数据加密,对数据进行加密,这样来说,破解的概率就小了很多。3DES的密钥长度为168位。由于3DES与DES的使用极其相似,只是密钥的长度有所改变,这里就不展开介绍了,感兴趣的读者可以尝试使用相应接口。

    3.AES:
      AES 加密算法作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点。AES 设计有三个密钥长度:128,192,256 位。是目前可获得的最安全的加密算法。

    • 支持模式:
        CFB/OFB/ECB/CBC

    • 优缺点:
        AES各方面均优于其他对称加密算法,缺点也只在于对称加密的局限。

    • 应用:
        AES的应用十分广泛,与DES是对称加密中的主流使用算法,并有逐渐取代DES的趋势。

    • 代码实现:
      加密:

            SecretKey secretKey = KeyGenerator.getInstance("AES").generateKey();//获得密钥实例
            cipher = Cipher.getInstance("AES/ECB/PKCS5Padding");//密钥容器的实例。传入的参数依次为加密算法,加密模式,填充模式(可选NOPadding,PKCS5Padding,PKCS7Padding)
            cipher.init(Cipher.ENCRYPT_MODE, secretKey);//使用加密模式初始化 密钥容器
            byte[] encryptResult = cipher.doFinal(stringToEncrypt.getBytes());

      解密:

            SecretKey secretKey = KeyGenerator.getInstance("AES").generateKey();//密钥必须与加密时保持一致
            Cipher cipher = Cipher.getInstance("AES/ECB/PKCS5Padding");//传入的参数必须与加密时保持一致
             cipher.init(Cipher.DECRYPT_MODE, secretKey);//解密时必须是Cipher.DECRYPT_MODE
            byte[] decryptResult=cipher.doFinal(encryptResult.getBytes());

    4.PBE:
      PBE算法使用的场景并不多,我们不必拘泥于它的使用和实现,但是它提供了一种加密思想是值得我们学习参考的——加“盐”扰乱。

    • “加盐”介绍:
        前面我们曾说到,对称加密很大的一个安全缺陷就是加密解密使用相同的密钥,这种密钥的不变性给密钥的安全传输和储存造成了很大的问题。那么有没有办法解决这个问题呢?一个办法就是给密钥加“盐”。这里的“盐”可以是随机数、用户ID、位置地理信息等等。“盐”最重要的作用就是对密钥的扰乱,使黑客无法确定真实的密钥,只要通信双方约定“盐”的形式,并且不泄漏,就能保证加密的安全性。我们通过PBE加盐的方式来了解加“盐”的思想:

      PBE加密首先用口令取代了密钥的概念。在加密时,PBE并不是使用口令直接加密,而是使用算法中的KDF函数通过“盐”对口令进行扰乱生成准密钥,然后使用一种散列函数多次迭代生成最终的密钥,密钥生成后,PBE在选用对称加密算法对数据进行加密。

    具体的实现可以是这样的:

    1、消息传递双方约定口令,这里甲方构建口令
    
    2、甲方构建口令后,公布给乙方
    
    3、由口令构建方(甲方)构建本次消息传递使用的盐,其实也可以双方约定一个数据,例如硬盘号,今天的日期等等,不一定非要写个安全算法计算出来,只要双方一致就行
    
    4、甲方使用口令、盐对数据加密
    
    5、甲方将盐、加密数据发送给消息接收者(乙方)
    
    6、乙方用收到的口令、盐(可以是约定的数据)对数据进行解密

      我们可以看到,对密钥加“盐”实际上是一种混淆扰乱的手段。但我们还可以从PBE的加盐思想中抽取出一种更简单的理解,“盐”就是密钥的一部分,只不过这一部分密钥是通信双方在通信之前就协商好的不被外界所知道的,通信过程中,双方只需传输另一部分非盐密钥即可,即使非盐密钥被截获,黑客也无法拿到整个密钥破解密文。

    非对称加密     

      非对称加密算法需要两个密钥来进行加密和解密,分别是公钥和私钥,需要注意的一点,这个公钥和私钥必须是一对的,如果用公钥对数据进行加密,那么只有使用对应的私钥才能解密,反之亦然。非对称加密算法的出现,就是为了解决只有一把密钥的加解密,只要这一把密钥丢失或者被公开,那么加密数据就很容易被攻击。同时,也正是由于非对称加密算法的出现,才有了后面的数字签名、数字证书等等。

    • 特点:算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂,而使得加密解密速度没有对称加密解密的速度快。

    • 使用:非对称加密主要有两种使用方面:加解密和数字签名验证。

    公钥加密,私钥解密;私钥签名,公钥验证
      主要说一下数字签名:
      数字签名采用公开密钥算法实现,数字签名与通常的数据加密算法作用是不同的,它们的实现过程与使用的密钥不同。数字签名使用的是发送方的密钥对,发送方用自己的私有密钥进行加密,接收方用发送方的公开密钥进行解密。数字签名是为了证实信息确实是由某个用户发送,对网络中是否有人看到该信息并不关心。 数据加密使用的是接受方的密钥对,发送方用接收方的公开密钥进行加密,接受方用自己的私有密钥进行解密。加密是一个多对一的关系:任何知道接受方公开密钥的人都可以向接收方发送加密信息,只有拥有接收方私有密钥的人才能对信息解密。一个用户通常有两个密钥对,一个用来对数字签名进行加密解密,一个用来对私密密钥进行加密解密。

    • 算法

    1.RSA:
      RSA是企业级应用标准,很多第三方的加密软件使用RSA 2048bit加密

    • 优点:
        密码分配简单,安全保障性高

    • 缺点:

      1.速度慢,RSA最快的情况也比DES慢上好几倍,RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右
      2.一般来说只用于少量数据加密
      3.产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。

    实际上,这些缺点是非对称加密本身的局限。

    • 算法实现:

            KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");//产生RSA密钥对产生器
            kpg.initialize(2048);//密钥对产生器初始化,参数为密钥长度,可选长度 512 1024 2048
            KeyPair kp = kpg.genKeyPair();//得到密钥对
            PublicKey publicKey = kp.getPublic();//公钥
            PrivateKey privateKey = kp.getPrivate();//私钥
      
            加密:
            BigInteger e = publicKey.getPublicExponent();//获取参数
            BigInteger n = publicKey.getModulus();//获取参数
            BigInteger m = new BigInteger(stringToEncrypt.getBytes());
            BigInteger c = m.modPow(e, n);//计算密文C
      
            解密:
            BigInteger c = new BigInteger(stringToDecrypt);
            BigInteger d = privateKey.getPrivateExponent();//获取参数
            BigInteger n = privateKey.getModulus();//获取参数
            BigInteger m = c.modPow(d, n);//计算解密结果m

    2.DSA:
      一般用于数字签名和认证,在DSA数字签名和认证中,发送者使用自己的私钥对文件或消息进行签名,接受者收到消息后使用发送者的公钥来验证签名的真实性。DSA只是一种算法,和RSA不同之处在于它不能用作加密和解密,也不能进行密钥交换,只用于签名,它比RSA要快很多。

    • 优点:
        安全性与RSA相近,产生密钥速度比RSA快很多

    • 缺点:
        如果使用DSA作为数字签名的加密算法,则只能使用SHA1作为消息散列(即消息摘要)算法。

    而如果使用RSA作为数字签名加密算法,对消息摘要算法则会有多种选择

    • 算法实现:
        由于DSA主要用于数字签名认证,不用于加解密工作,这里就不写加解密代码的具体实现了。

    3.ECC:
      ECC是一种高效的非对称加密算法,经常使用于移动设备上。

    • 优点:
        ECC 与 RSA 相比,有以下的优点:

      1)相同密钥长度下,安全性能更高,如160位ECC已经与1024位RSA、DSA有相同的安全强度。
      
        (2)计算量小,处理速度快,在私钥的处理速度上(解密和签名),ECC远 比RSA、DSA快得多。
      
        (3)存储空间占用小 ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多, 所以占用的存储空间小得多。
      
        (4)带宽要求低使得ECC具有广泛得应用前景。
    • 算法实现:
        ECC与RSA有着相似的特性,它们的代码实现也十分相似,只是在产生密钥对产生器时有所区别,其它地方没有差别,因此这里不写代码实现。有需要的读者可以参照上面RSA的实现。

    总结

      到这里,我们对三大类算法的介绍就结束了。可以看到,不同算法有着不同的特点特性,开发者在选择使用时需要结合考虑使用场景、需求、成本等各个方面的因素。对于单向加密与可逆加密,开发者很容易区别选择;但对于对称加密与非对称加密,选择可能就不是很容易决断了,这里,我们提供一种思路,也是被广泛接纳使用的——由于对称加密速度快但相对安全性低,非对称加密安全性高但速度相对慢——我们使用对称加密对大量的数据明文做加密,然后使用非对称加密对对称加密密钥进行加密,这样就兼顾了速度与安全的问题。


    展开全文
  • PHP常见算法合集

    万次阅读 2020-10-24 01:07:40
    PHP常见算法合集,常码字不易,出精品更难,没有特别幸运,那么请先特别努力,别因为懒惰而失败,还矫情地将原因归于自己倒霉。你必须特别努力,才能显得毫不费力。如果这篇文章能给你带来一点帮助,希望给飞兔小...

    〝 古人学问遗无力,少壮功夫老始成 〞

    PHP常见算法合集,常码字不易,出精品更难,没有特别幸运,那么请先特别努力,别因为懒惰而失败,还矫情地将原因归于自己倒霉。你必须特别努力,才能显得毫不费力。如果这篇文章能给你带来一点帮助,希望给飞兔小哥哥一键三连,表示支持,谢谢各位小伙伴们。

    目录

    一、文件夹遍历

    二、九九乘法表

    三、无限极递归分类

    四、冒泡排序

    五、选择排序

    六、插入排序

    七、快速排序


    一、文件夹遍历

    <?php
    function allFile($path = __DIR__, $level = 1)
    {
        if (is_dir($path) && is_readable($path)) {
            if($pd = opendir($path)) {
                while (($file = readdir($pd)) !== false) {
                    if($file != '.' && $file != '..') {
                        if (($subPath = $path . DIRECTORY_SEPARATOR . $file) && is_dir($subPath)) {
                            echo "<pre />";
                            echo '<span style="color: red;font-weight:bold;">' . str_repeat("--", $level) . $subPath . '</span>';
                            self::allFile($subPath, $level++);
                        } else {
                            echo "<pre />";
                            echo str_repeat("--", $level) . $subPath;
                        }
                    }
                }
            }
        } else {
            echo "{$path} is not a available dir";
        }
    }
    

    二、九九乘法表

    <?php
    function create()
    {
        for ($i = 1; $i <= 9; $i++) {
            for ($j = 1; $j <= $i; $j++) {
                echo $j . '*' . $i . '=' . $i * $j . PHP_EOL;
            }
            echo "<br />";
        }
    }

    三、无限极递归分类

    ①、递归算法

    <?php
    function getTree($array, $pid =0, $level = 0)
    {
        //声明静态数组,避免递归调用时,多次声明导致数组覆盖
        static $list = [];
     
        foreach ($array as $key => $value) {
            //第一次遍历,找到父节点为根节点的节点 也就是pid=0的节点
            if ($value['pid'] == $pid) {
                //父节点为根节点的节点,级别为0,也就是第一级
                $value['level'] = $level;
                //把数组放到list中
                $list[] = $value;
                //把这个节点从数组中移除,减少后续递归内存消耗
                unset($array[$key]);
                //递归调用
                getTree($array, $value['id'], $level+1);
            }
        }
        return $list;
    }

    ②、引用算法

    <?php
    function getTree($array)
    {
        //第一步 构造数据
        $items = [];
        foreach($array as $value) {
            $items[$value['id']] = $value;
        }
     
        //第二部 遍历数据 生成树状结构
        $tree = [];
        foreach($items as $key => $value) {
            if(isset($items[$item['pid']])) {
                $items[$item['pid']]['son'][] = &$items[$key];
            } else {
                $tree[] = &$items[$key];
            }
        }
        return $tree;
    }

    四、冒泡排序

    <?php
    function bubbleSort($arr)
    {
        $len = count($arr);
        for($i=1; $i<$len; $i++) {
            for($k=0; $k<$len-$i; $k++) {
                if($arr[$k] > $arr[$k+1]) {
                    $tmp=$arr[$k+1];
                    $arr[$k+1]=$arr[$k];
                    $arr[$k]=$tmp;
                }
            }
        }
        return $arr;
    }

    五、选择排序

    <?php
    function selectSort($arr)
    {
        $len=count($arr);
        for($i=0; $i<$len-1; $i++) {
            $p = $i;
            for($j=$i+1; $j<$len; $j++) {
                if($arr[$p] > $arr[$j]) {
                    $p = $j;
                }
            }
            if($p != $i) {
                $tmp = $arr[$p];
                $arr[$p] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
        return $arr;
    }

    六、插入排序

    <?php
    function insertSort($arr)
    {
        $len=count($arr);
        for($i=1; $i<$len; $i++) {
            $tmp = $arr[$i];
            for($j=$i-1;$j>=0;$j--) {
                if($tmp < $arr[$j]) {
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $tmp;
                } else {
                    break;
                }
            }
        }      
        return $arr;
    }

    七、快速排序

    <?php
    function quickSort($arr) {
        $len = count($arr);
     
        if($len <= 1) return $arr;
     
        $base_num = $arr[0];
        $left_array = [];
        $right_array = [];
        for($i=1; $i<$len; $i++) {
            if($base_num > $arr[$i]) {
                $left_array[] = $arr[$i];
            } else {
                $right_array[] = $arr[$i];
            }
        }
        $left_array = self::quickSort($left_array);
        $right_array = self::quickSort($right_array);
        return array_merge($left_array, array($base_num), $right_array);
    }

     

    展开全文
  • MapReduce常见算法

    千次阅读 2016-04-06 18:53:08
    MapReduce常见算法 作者:数据分析玩家  对于MapReduce,常见的算法有单词计数、数据去重、排序、TopK、选择、投影、分组、多表链接、单表关联。本文将具体阐述两个算法:数据去重与TopK。  为了让大家看的更清楚...

    2016年4月6日18:28:29

    MapReduce常见算法

    作者:数据分析玩家

           对于MapReduce,常见的算法有单词计数、数据去重、排序、TopK、选择、投影、分组、多表链接、单表关联。本文将具体阐述两个算法:数据去重与TopK。

           为了让大家看的更清楚,现在将所用数据grade.txt数据列出:

    <strong>HeBei	568
    HeBei	313
    HeBei	608
    HeBei	458
    HeBei	157
    HeBei	629
    HeBei	594
    HeBei	305
    HeBei	168
    HeBei	116
    ShanDong	405
    ShanDong	667
    ShanDong	289
    ShanDong	463
    ShanDong	59
    ShanDong	695
    ShanDong	74
    ShanDong	547
    ShanDong	115
    ShanDong	534
    ShanXi	74
    ShanXi	254
    ShanXi	270
    ShanXi	30
    ShanXi	130
    ShanXi	149
    ShanXi	417
    ShanXi	486
    ShanXi	156
    ShanXi	608
    JiangSu	628
    JiangSu	567
    JiangSu	681
    JiangSu	289
    JiangSu	314
    JiangSu	147
    JiangSu	389
    JiangSu	491
    JiangSu	353
    JiangSu	162
    HeNan	202
    HeNan	161
    HeNan	121
    HeNan	450
    HeNan	603
    HeNan	144
    HeNan	250
    HeNan	521
    HeNan	86
    HeNan	404</strong></strong>
    首先先讲述第一个业务:求取每一个省份分数的最大值,这个业务涉及到了数据的去重与topone。

    先将源代码列出供大家参考:

    <strong>package Top;
    
    import java.io.IOException;
    import java.net.URI;
    import java.net.URISyntaxException;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.FSDataInputStream;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.IOUtils;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    
    //本程序的目的是通过MapReduce进行数据的去重,同时求取topone
    public class Top0
    {       
    	     public  static String path1 = "hdfs://hadoop:9000/grade.txt";
    	     public  static String path2 = "hdfs://hadoop:9000/gradedir";
             public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException, URISyntaxException
             {
            	    FileSystem fileSystem = FileSystem.get(new URI(path1),new Configuration());
            	    if(fileSystem.exists(new Path(path2)))
            	    {
            	    	fileSystem.delete(new Path(path2), true);
            	    }
            	    Job job = new Job(new Configuration()); 
            	    //编写MapReduce程序的驱动
            	    FileInputFormat.setInputPaths(job, new Path(path1));
            	    job.setMapperClass(MyMapper.class);
            	    job.setReducerClass(MyReducer.class);
            	    job.setOutputKeyClass(Text.class);
            	    job.setOutputValueClass(LongWritable.class);
            	    FileOutputFormat.setOutputPath(job, new Path(path2));    
            	    //提交任务
            	    job.waitForCompletion(true);
            	    FSDataInputStream fr = fileSystem.open(new Path("hdfs://hadoop:9000/gradedir/part-r-00000"));
            	    IOUtils.copyBytes(fr, System.out, 1024, true); 
             }
             public static class MyMapper extends Mapper<LongWritable, Text, Text, LongWritable>
             {
            	    protected void map(LongWritable k1, Text v1,Context context)throws IOException, InterruptedException
            	    {
            	              String[] splited = v1.toString().split("\t");
            	              String province = splited[0];
            	              String grade = splited[1];
            	              context.write(new Text(province),new LongWritable(Long.parseLong(grade)));
            	    }
            	 
             }
             public static class MyReducer extends Reducer<Text, LongWritable, Text, LongWritable>
             {
            	    protected void reduce(Text k2, Iterable<LongWritable> v2s,Context context)throws IOException, InterruptedException
            	    {
            	             long topgrade = Long.MIN_VALUE;
            	             for (LongWritable v2 : v2s)
    						 {
    							 if(v2.get()>topgrade)
    							 {
    								 topgrade = v2.get();
    							 }
    						 }
            	             context.write(k2,new LongWritable(topgrade));     
            	    }
             }
    }</strong>

    MapReduce程序运行之后显示的结果为:


    接下来讲述第二个业务:求取每个省份分数的前三个最大值,这个业务涉及到了数据的去重与topk.

    先将源代码列出供大家参看:

    <strong>package Top;
    
    import java.io.IOException;
    import java.net.URI;
    import java.net.URISyntaxException;
    import java.util.ArrayList;
    import java.util.Collections;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.FSDataInputStream;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.IOUtils;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    
    public class Top3
    {
        public  static String path1 = "hdfs://hadoop:9000/grade.txt";
        public  static String path2 = "hdfs://hadoop:9000/gradedir2";
        public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException, URISyntaxException
        {
       	    FileSystem fileSystem = FileSystem.get(new URI(path1),new Configuration());
       	    if(fileSystem.exists(new Path(path2)))
       	    {
       	    	fileSystem.delete(new Path(path2), true);
       	    }
       	    Job job = new Job(new Configuration()); 
       	    //编写MapReduce程序的驱动
       	    FileInputFormat.setInputPaths(job, new Path(path1));
       	    job.setMapperClass(MyMapper.class);
       	    job.setReducerClass(MyReducer.class);
       	    job.setOutputKeyClass(Text.class);
       	    job.setOutputValueClass(LongWritable.class);
       	    FileOutputFormat.setOutputPath(job, new Path(path2));    
       	    //提交任务
       	    job.waitForCompletion(true);
       	    FSDataInputStream fr = fileSystem.open(new Path("hdfs://hadoop:9000/gradedir2/part-r-00000"));
       	    IOUtils.copyBytes(fr, System.out, 1024, true); 
        }
    	    public static class MyMapper extends Mapper<LongWritable, Text, Text, LongWritable>
    	    {
    		    	protected void map(LongWritable k1, Text v1,Context context)throws IOException, InterruptedException
    		    	{ 
    		    		  String[] splited = v1.toString().split("\t"); 
    		    		  String province = splited[0];
    		    		  String grade = splited[1];
    		    		  context.write(new Text(province),new LongWritable(Long.parseLong(grade)));
    		    	} 
    	    }
    	    public static class MyReducer extends Reducer<Text, LongWritable, Text,Text>
    	    {
    	    	    protected void reduce(Text k2, Iterable<LongWritable> v2s,Context context)throws IOException, InterruptedException
    	    	    {
    					ArrayList<Long> arr = new ArrayList<Long>();  
    	    	    	for (LongWritable v2 : v2s)
    					 {
    						arr.add(v2.get());
    					 }
    	    	    	Collections.sort(arr);
    	    	    	Collections.reverse(arr);
    	    	    	context.write(k2,new Text(arr.get(0)+"\t"+arr.get(1)+"\t"+arr.get(2)+""));
    	    	    }    
    	    }
    }</strong>

    MapReduce程序运行之后显示的结果为:


           对于MapReduce更重要的是可以灵活运用,尤其是shuffle阶段是MapReduce自动运行的,我们往往可以在里面做很多的文章。对于上面的两个程序,如有问题可以给我留言.
                                                                                                                           
                                                                                                                                                    2016年4月6日18:52:15


           

    展开全文
  • python实现常见算法

    千次阅读 多人点赞 2019-05-17 10:48:32
    常见算法: 一、排序引入 1.排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 2.排序算法的稳定性 稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。...

    常见算法:

    一、排序引入

    1.排序与搜索
    排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。
    2.排序算法的稳定性
    稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。

    1 8 3 8 5 6 7 2
    (4,1) (3,1) (3,7) (5,6)
    (3,7)(3,1)

    如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。
    不稳定排序算法可能会在相等的键值中改变纪录的相对次序
    

    二、冒泡排序

    1.什么是冒泡排序
    冒泡排序(Bubble Sort)是一种简单的排序算法。
    它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
    遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
    冒泡排序算法的工作原理如下:
    比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
    对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
    除了最后一个,所有的元素重复以上的步骤。
    持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
    2.冒泡排序的分析
    交换过程:
    在这里插入图片描述
    3.冒泡排序的实现

    def bubble_sort(alist):
        # 外层循环控制比较几轮
        n = len(alist)
        for j in range(n - 1):
            # 内存循环控制交换
            # -j是不再换已经排好的
            for i in range(n - 1 - j):
                # 若前一个比后一个大,则换
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i + 1] = alist[i + 1], alist[i]
    
    if __name__ == '__main__':
        li = [33, 11, 26, 78, 3, 9, 40]
        print(li)
        bubble_sort(li)
        print(li)
    

    优化有序的情况,最优时间复杂度O(n)

    def bubble_sort(alist):
        # 外层循环控制比较几轮
        n = len(alist)
        for j in range(n - 1):
            # 定义计数器
            count = 0
            # 内存循环控制交换
            # -j是不再换已经排好的
            for i in range(n - 1 - j):
                # 若前一个比后一个大,则换
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i + 1] = alist[i + 1], alist[i]
                    # 计数器
                    count += 1
            if count == 0:
                return
    

    4.时间复杂度
    最优时间复杂度:O(n)
    最坏时间复杂度:O(n²)
    稳定性:稳定
    5.评价
    优点:稳定,简单
    缺点:效率不很高,运行时间较长

    三、选择排序

    1.什么是选择排序
    选择排序(Selection sort)是一种简单直观的排序算法。
    选择排序算法的工作原理如下:
    首先在序列中找到最小或最大元素,存放到排序序列的前或后。
    然后,再从剩余元素中继续寻找最小或最大元素。
    然后放到已排序序列的末尾。
    以此类推,直到所有元素均排序完毕。
    2.选择排序的分析
    排序过程:
    在这里插入图片描述
    3.选择排序的实现

    alist = [3, 11, 26, 26,7, 3, 9, 4]
     选择排序把数据当成2部分
     alist = [3,        11, 26, 26,7, 9, 4]
     alist = [3, 4     11, 26, 26,7, 9]
     怎么找到最小值? 索引min = 0
     最终min = 0
     min = 1开始
     min = 6
     alist[1] alist[6]
    
    def select_sort(alist):
        n = len(alist)
        # 外层控制比较几轮
        for j in range(n - 1):
            min_index = j
            # 内层控制元素比较和更新索引
            for i in range(j + 1, n):
                # 进行比较
                if alist[min_index] > alist[i]:
                    # 更新索引
                    min_index = i
            # 退出循环后,交换数据
            alist[j], alist[min_index] = alist[min_index], alist[j]
            if __name__ == '__main__':
       			 li = [3, 11, 26, 26, 7, 3, 9, 4]
        		print(li)
        		select_sort(li)
        		print(li)
    

    4.时间复杂度
    最优时间复杂度:O(n²)
    最坏时间复杂度:O(n²)
    稳定性:不稳定
    5.评价
    优点:移动次数少
    缺点:比较次数多

    四、插入排序

    1.什么是插入排序
    插入排序(Insertion Sort)是一种简单直观的排序算法。
    插入排序算法的工作原理如下:
    构建有序序列
    在已排序序列中扫描未排序数据
    找到相应位置并插入
    2.插入排序的分析
    排序过程:
    在这里插入图片描述
    3.插入排序的实现
    插入排序

    def insert_sort(alist):
        n = len(alist)
        # 外层循环控制从右边取多少元素
        for j in range(1, n):
            # i = [1,2,3...]
            i = j
            # 内存循环
            while i > 0:
                if alist[i] < alist[i - 1]:
                    alist[i], alist[i - 1] = alist[i - 1], alist[i]
                    # 控制循环结束
                    i -= 1
                else:
                    break
    
    
    if __name__ == '__main__':
        li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(li)
        insert_sort(li)
        print(li)
    

    4.时间复杂度
    最优时间复杂度:O(n)
    最坏时间复杂度:O(n²)
    稳定性:稳定
    5.评价
    优点:稳定,比较快
    缺点:比较次数不确定,数据量越大,该算法越渣

    五、希尔排序

    1.什么是希尔排序
    希尔排序(Shell Sort)是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。
    希尔排序是非稳定排序算法,是DL.Shell于1959年提出的。
    希尔排序算法的工作原理如下:
    把记录按下标的一定增量分组,对每组使用直接插入排序算法排序。
    随着增量逐渐减少,每组包含的关键词越来越多。
    当增量减至1时,整个文件恰被分成一组,算法便终止。
    2.希尔排序的分析
    排序过程:
    增量用gap代表,第一次增量3是将数据分3组

    3.希尔排序的实现

    在这里插入图片描述

    def shellSort(nums):
        # 设定步长
        step = len(nums)/2
        while step > 0:
            for i in range(step, len(nums)):
                # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
                while i >= step and nums[i-step] > nums[i]:
                    nums[i], nums[i-step] = nums[i-step], nums[i]
                    i -= step
            step = step/2
        return nums
    
    
    if __name__ == '__main__':
        nums = [9,3,5,8,2,7,1]
        print shellSort(nums)
    
    
    """
    [1, 2, 3, 5, 7, 8, 9]
    """
    

    4.时间复杂度
    最优时间复杂度:根据步长序列的不同而不同,最优是1.3,根据数学运算算出的gap
    最坏时间复杂度:O(n²)
    稳定性:不稳定
    5.评价
    优点:平均时间短,数据移动少
    缺点:不稳定

    六、快速排序

    1.什么是快速排序
    快速排序(Quicksort),又称划分交换排序(partition-exchange sort)。
    通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。
    整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    快速排序算法的工作原理如下:
    从数列中挑出一个元素,称为"基准"(pivot)。
    重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
    在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
    2.快速排序的分析
    排序过程:
    在这里插入图片描述
    3.快速排序的实现
    快排:first理解为第一个位置的索引,last是最后位置索引

    def quick_sort(alist, first, last):
        # 递归终止条件
        if first >= last:
            return
    
            # 设置第一个元素为中间值
        mid_value = alist[first]
        # low指向
        low = first
        # high
        high = last
        # 只要low小于high就一直走
        while low < high:
            # high大于中间值,则进入循环
            while low < high and alist[high] >= mid_value:
                # high往左走
                high -= 1
            # 出循环后,说明high小于中间值,low指向该值
            alist[low] = alist[high]
            # high走完了,让low走
            # low小于中间值,则进入循环
            while low < high and alist[low] < mid_value:
                # low向右走
                low += 1
            # 出循环后,说明low大于中间值,high指向该值
            alist[high] = alist[low]
        # 退出整个循环后,low和high相等
        # 将中间值放到中间位置
        alist[low] = mid_value
        # 递归
        # 先对左侧快排
        quick_sort(alist, first, low - 1)
        # 对右侧快排
        quick_sort(alist, low + 1, last)
    
    
    if __name__ == '__main__':
        li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(li)
        quick_sort(li, 0, len(li) - 1)
        print(li)
    

    4.时间复杂度
    最优时间复杂度:O(nlogn)
    遍历每个数是O(n),访问每个数是O(logn),最终是O(nlogn)
    可以转换为求二叉树深度的思想
    最坏时间复杂度:O(n²)
    稳定性:不稳定
    5.评价
    优点:效率高,数据移动比较少,数据量越大,优势越明显
    缺点:不稳定

    七、归并排序

    1.什么是归并排序
    归并排序(MergeSort)是采用分治法的一个非常典型的应用。
    归并排序的思想就是先递归分解数组,再合并数组。
    归并排序算法的工作原理如下:
    将数组分解最小之后,然后合并两个有序数组。
    比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。
    然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
    2.归并排序的分析
    排序过程:
    在这里插入图片描述
    3.归并排序的实现
    归并排序

    def merge_sort(alist):
        n = len(alist)
    
        # 递归结束条件
        if n <= 1:
            return alist
    
        # 中间位置
        mid = n // 2
        # 递归拆分左侧
        left_li = merge_sort(alist[:mid])
        # 递归拆分右侧
        right_li = merge_sort(alist[mid:])
        # 需要2个游标,分别指向左列表和右列表第一个元素
        left_point, right_point = 0, 0
        # 定义最终返回的结果集
        result = []
        # 循环合并数据
        while left_point < len(left_li) and right_point < len(right_li):
            # 谁小谁放前面
            if left_li[left_point] <= right_li[right_point]:
                # 放进结果集
                result.append(left_li[left_point])
                # 游标移动
                left_point += 1
            else:
                result.append(right_li[right_point])
                right_point += 1
        # 退出循环时,形成左右两个序列
        result += left_li[left_point:]
        result += right_li[right_point:]
        return result
    
    
    if __name__ == '__main__':
        li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(li)
        sort_li = merge_sort(li)
        print(li)
        print(sort_li)
    

    4.时间复杂度
    最优时间复杂度:O(nlogn)
    最坏时间复杂度:O(nlogn)
    稳定性:稳定
    5.评价
    优点:稳定,数据量越大越优秀
    缺点:需要额外空间
    6.常见算法的效率比较

    快速排序消耗空间因为每次递归时,要保持一些数据
    最优情况:每一次平均分组的情况 O(logn)
    最坏情况:退化为冒泡排序的情况 O(n)
    堆排序是结合二叉树去做的
    

    八、搜索

    1.搜索引入
    搜索是在一个数据集合中找到一个特定数据的算法
    搜索通常的答案是真的或假的
    搜索的常见方法有二分查找、哈希查找等
    2.二分法查找
    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好。
    缺点是要求待查表为有序表
    因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
    二分查找的工作原理如下:
    首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功。
    否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
    重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    3.二分查找的实现
    递归实现
    非递归实现
    递归的实现

    def my_search(alist, item):
        n = len(alist)
        # 递归结束条件
        if n > 0:
            # 折半
            mid = n // 2
            # 判断中间元素是否为要查的元素
            if alist[mid] == item:
                return True
            # 判断中间元素与item的大小
            elif item < alist[mid]:
                # 继续递归查找
                return my_search(alist[:mid], item)
            else:
                return my_search(alist[mid + 1:], item)
        return False
    

    非递归实现

    def my_search2(alist, item):
        n = len(alist)
        # 起始,0
        first = 0
        # 结束位置
        last = n - 1
        while first <= last:
            # 折半
            mid = (first + last) // 2
            # 判断中间元素
            if alist[mid] == item:
                return True
            elif item < alist[mid]:
                last = mid - 1
            else:
                first = mid + 1
        return False
    
    
    if __name__ == '__main__':
        # 2个注意点:必须用有序的顺序表
        li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
        print(my_search(li, 17))
        print(my_search2(li, 111))
    

    4.时间复杂度
    最优时间复杂度:O(1)
    最坏时间复杂度:O(logn)

    总结

    在这里插入图片描述

    展开全文
  • 面试常见算法

    千次阅读 2019-01-22 11:58:14
    面试常见算法 /** * 快速排序 * 选择一个基准值,将比基准值小的放在左侧,大的放在右侧 * 再将两侧的数组进行递归调用即可 */ public void quickSort(int[] numbers, int start, int end){ if (start &lt...
  • JS常见算法小总结

    万次阅读 多人点赞 2019-05-14 16:23:21
    今天与大家一起来测试一下常用算法的性能解析: 首先我们创建一个含有十万个数组的数组用来测试: let array = []; for (let i = 0; i < 100000; i++) { array.push(i) } 接下来我们一起分析各个算法的性能: ...
  • 常见算法复杂度样例

    千次阅读 2020-02-15 15:29:26
    大O表示法 用O(n)来体现算法时间复杂度的记法被称作大O表示法。一般我们我们评估一个算法都是直接评估它...常见算法复杂度样例 常数阶 int sum = 0, n = 10; // 语句执行一次 int sum = (1+n)*n/2; // 语句执行...
  • 《算法导论》常见算法总结

    万次阅读 多人点赞 2018-11-08 15:51:55
    调整过程如下图所示: 4、堆排序算法 堆排序算法过程为:先调用创建堆函数将输入数组A[1…n]造成一个最大堆,使得最大的值存放在数组第一个位置A[1],然后用数组最后一个位置元素与第一个位置进行交换,并将堆的大小...
  • 机器学习笔记(常见算法

    千次阅读 2020-04-08 02:32:06
    大概了解常见算法
  • 机器学习常见算法整理

    万次阅读 2019-12-06 16:56:01
    1.XGBoost算法 1.1算法特性 用于解决二分类问题,同时通过使用许多策略能够防止过拟合现象发生,模型准确率比普通算法要高。XGBoost支持并行化计算,使得算法在模型训练及模型计算时运行速度快,效率高。XGBoost...
  • iOS面试题系列之常见算法

    万次阅读 2016-05-02 00:27:34
    iOS面试中熟悉常见算法1、 对以下一组数据进行降序排序(冒泡排序)。“24,17,85,13,9,54,76,45,5,63” int main(int argc, char *argv[]) { int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63}; int...
  • 面试常见算法-排序查找算法

    千次阅读 2015-06-22 07:37:26
    算法是程序员必被的一个技能,在面试中常常出现,下面总结了面试中出现的常见算法,这些算法程序员应该牢记在心中,要非常熟练。
  • 常见算法复杂度对比

    千次阅读 2018-02-26 12:02:28
    常见算法复杂度对比 快速排序 nlogn 堆排序 nlogn 冒泡排序 在改良的冒泡下 最优时间复杂度为n 插入排序 最优下n 选择排序 n*n 归并 nlogn …… 下面上图 测试: 对N个数进行排序,在各自最优条件下...
  • 在上一篇文章 【算法大杂烩】常见算法的归类和总结——非对称加密算法 中我们简要介绍了常见的非对称加密算法的相关知识。这次我们乘胜追击,介绍【信息摘要算法】, 通过本文的阅读,你可以了解到以下知识: 什么...
  • java算法大全源码包 java算法大全,有近100多种常见算法的源代码,是学习JAVA算法的难得资料。
  • 常见算法时间复杂度比较

    千次阅读 2017-05-29 16:34:11
    Python常见算法时间复杂度比较
  • 在上一篇文章【算法大杂烩】常见算法的归类和总结——对称加密算法 中我们简要介绍了常见的对称加密算法的相关知识。这次我们趁热打铁,介绍【非对称加密算法】, 通过本文的阅读,你可以了解到以下知识: 什么...
  • 常见算法时间复杂度

    千次阅读 2016-08-30 17:41:57
    常见算法时间复杂度: O(1): 表示算法的运行时间为常量 O(n): 表示该算法是线性算法 O(㏒2n): 二分查找算法 O(n2): 对数组进行排序的各种简单算法,例如直接插入排序的算法。 O(n3): 做两个n阶矩阵的乘法运算 ...
  • 人工智能常见算法简介

    万次阅读 多人点赞 2018-09-16 16:39:52
    人工智能的三大基石—算法、数据和计算能力,算法作为其他之一,是非常重要的,那么人工智能都会涉及哪些算法呢?不同算法适用于哪些场景呢? 按照模型训练方式不同可以分为监督学习(Supervised Learning),无...
  • 人工智能之机器学习常见算法

    万次阅读 多人点赞 2016-05-22 15:47:54
    摘要之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是...这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有
  • C#常见算法面试

    千次阅读 2016-06-16 18:50:51
    转载于:C#常见算法面试 一、求以下表达式的值,写出您想到的一种或几种实现方法: 1-2+3-4+……+m  //方法一,通过顺序规律写程序,同时也知道flag标志位的重要性。  static int F1(int m) { int ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,599
精华内容 21,439
关键字:

常见算法