你可能不知道的快速排序：三路快排-低调大师

你可能不知道的快速排序：三路快排

2020-10-13 499

快速排序

快速排序是什么快速排序是图灵奖得主C. A. R. Hoare（1934--）于1960时提出来的。

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。整个排序过程只需要三步：

在数据集之中，选择一个元素作为"基准"（pivot）。
所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

引自wikipedia 快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

步骤

找到该数组的基准点(中间数)，并创建两个空数组left和right；
遍历数组，拿出数组中的每个数和基准点进行比较，如果比基准点小就放到left数组中，如果比基准点大就放到right数组中；
对数组left和right进行递归调用。

方法一

function quickSort(arr) {
      if (arr.length<=1) {return arr;}
      var left = [],
        right = [],
        baseDot =Math.round(arr.length/2),
        base =arr.splice(baseDot, 1)[0];

      for (var i =0; i <arr.length; i++) {
        if (arr[i] < base) {
          left.push(arr[i])
        }else {
          right.push(arr[i])
        }
      }

      return quickSort(left).concat([base], quickSort(right));
    }

实现一个quickSort的封装，并且定义left和right，找到数组的基准点baseDot和对应的基数base，然后遍历数组的每一项和base进行对比，最后递归调用，给出一个跳出条件if (arr.length <= 1) {return arr;}

方法二

function quickSort(array, left, right) {
      var length =array.length;
        left =typeof left ==='number'? left :0,
        right =typeof right ==='number'? right : length-1;

        if (left < right) {
            var index = left -1;
            for (var i = left; i <= right; i++) {
                if (array[i] <= array[right]) {
                    index++;
                    var temp = array[index];
                    array[index] = array[i];
                    array[i] = temp;
                }
            }
            quickSort(array, left, index -1);
            quickSort(array, index +1, right);
        }
        return array;
    }

快速排序的基本思想就是分治法

引自wikipedia 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

快速排序的改进方法：三路快排

定义

三路快速排序是快速排序的的一个优化版本，将数组分成三段，即小于基准元素、等于基准元素和大于基准元素，这样可以比较高效的处理数组中存在相同元素的情况,其它特征与快速排序基本相同。

我这里简单概括一下思路，有兴趣的同学可到上面的链接上阅读：[快速排序及优化(Java实现)][Java]

随机选取基准值base(支点随机选取),参考[快速排序算法的优化思路总结][Link 1]
配合着使用插入排序(当问题规模较小时，近乎有序时，插入排序表现的很好)
当大量数据，且重复数多时，用三路快排

    <!DOCTYPE html>
    <html>
    
     <head>
      <meta charset="UTF-8">
      <title></title>
      <script type="text/javascript">
       console.time("test0")
       function qSort(arr) {
        if(arr.length == 0) {
         return [];
        }
        var left = [];
        var right = [];
        var pivot = arr[0];
        for(var i = 1; i < arr.length; i++) { // 注意这里的起始值，因为有一个作为flag了
         if(arr[i] < pivot) {
          left.push(arr[i]);
         } else {
          right.push(arr[i]);
         }
        }
        return [...qSort(left), pivot, ...qSort(right)];
       }
       console.log(qSort([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]));
       console.timeEnd("test0")
      </script>
      <script type="text/javascript">
       console.time("test1")
       function qSort3(arr) {       //三路快排
        if(arr.length == 0) {
         return [];
        }
        var left = [];
        var center = [];
        var right = [];
        var pivot = arr[0];    //偷懒，直接取第一个,实际取值情况 参考[快速排序算法的优化思路总结]
        for(var i = 0; i < arr.length; i++) {      
         if(arr[i] < pivot) {
          left.push(arr[i]);
         } else if(arr[i] == pivot) {
          center.push(arr[i]);
         } else {
          right.push(arr[i]);
         }
        }
        return [...qSort3(left), ...center, ...qSort3(right)];
       }
       console.log(qSort3([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]))
       console.timeEnd("test1")
      </script>
     </head>
    
     <body>
     </body>
    
    </html>

可以看到对有重复数据的数据优化还是很可观的。

本文分享自微信公众号 - JavaScript忍者秘籍（js-obok）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

微信关注我们

原文链接：https://my.oschina.net/u/3024426/blog/4671651

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

git代码版本管理(1)——git版本回滚

git代码版本管理(1)——git版本回滚 1、问题背景在利用github、gitlab、Gitee等代码管理器中对代码的管理，我们有时会出现错误提交的情况，此时我们希望能撤销提交操作，让程序回到提交之前的样子。本文总结了两种解决方法：回退（reset）、反做（revert）。 push前与push后。 2、git提交小知识使用git的每次提交，Git都会自动把它们串成一条时间线，这条时间线就是一个分支。如果没有新建分支，那么只有一条时间线，即只有一个分支，在Git里，这个分支叫主分支，即master分支。有一个HEAD指针指向当前分支（只有一个分支的情况下会指向master，而master是指向最新提交）。每个版本都会有自己的版本信息，如特有的版本号、版本名等。如下图，假设只有一个分支：每次提交都会生成一次提交的ID号(此ID号唯一)(如下图) 3、解决方式 3.1 还没有push推送到远端、只执行了本地commit提交 [root@db test]# ls # 当前本地仓库下的文件README.md 第一次提交.txt 第二次提交.txt[root@d...

2020-10-12

653

每个时代，都不会亏待会学习的人。大家好，我是 yes。这种设计类问题想必大家都不陌生，面试时或多或少都能碰到。比如如何写一个线程池？如何写一个 HashMap ？如何写一个 RPC 框架等等，当然这里的写不是真的叫你用代码写出来，只是说说设计理念，整体架构。这个面试题来自于一个读者的字节面试经历，我会从面试技巧和消息中间件的设计两个方面阐述。我觉得重点在于面试技巧，因为它通用。两种极端的情况大多数同学遇到这种问题会出现两种极端的情况：第一种：一脸懵逼，两眼无神，不知从何说起，万般思绪，都化作一声叹息。第二种：夸夸其谈，像是口中架起了一把加特林，哒哒哒哒哒哒哒哒，还冒着蓝火。第一种不用说了，好一点的面试官可能会引导你，会问一些提示性的问题，一步一步地带你渐入佳境，当然你要是胸中无点滴，那还是没救的，场面就异常地尴尬。第二种会把面试官整蒙了，或许你真的懂很多，很多细节也都清晰，但是你不能一股脑儿的都抛出来，这会显得你抓不住重点。面试官也是人这点其实很关键，很多把面试官当成一个莫得感情的提问机器人，觉得他无所不能可以完全 get 到你的点，殊不知你引以为傲的细节回答...

2020-10-13

508

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。