理论篇-快速排序

快速排序是生产环境中经常被用到的排序算法。快速排序算法也是一种运用分而治之思想的算法。

在分的过程中有两种不同的实现思想，分别如下图所示:

fastsort_1

fastsort_2

最近又看到一种实现: 填坑法。该方法比较简单，也比较容易理解。基本思想如下:

  1. 将第一个数记下作为key，同时挖出第一个坑
  2. 然后从后向前找第一个小于等于key的数，然后将该数填充的之前的坑中，同时又挖出了另一个坑
  3. 然后从前向后找第一个大于key的数，然后将该数填充到之前的坑中，此时又挖了一个坑
  4. 一直循环过程2和3，直到相遇。最后将之前的key填到最后的坑中。

这样保证了相遇位置之前的所有数都小于等于关键字，之后的数都大于关键字。

源码参考

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    2、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: true
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

王彪<br>计算机科学与技术专业<br>email:841824090@qq.com<br>2009-2013 苏州大学<br>2013-2015 苏州思必驰信息科技有限公司<br>2016-2017 美团<br>2017-至今 搜狗