JavaScript实现快速排序的两种方式——分治策略+数组合并

「爱情、让人受尽委屈。」 2022-11-15 14:07 180阅读 0赞

> **介绍快速排序**：快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种**分治**的策略，通常称其为分治法(Divide-and-ConquerMethod)。

"快速排序"的思想很简单，整个排序过程只需要三步：

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

1.  方法一

> 核心：选择"**基准**"（pivot），**并将其与原数组分离，再定义两个空数组**，用来存放一左一右的两个子集。

<script>
    
      function quickSort(arr) { 
      //检查数组的元素个数，如果小于等于1，就返回。
        if (arr.length<=1){ 
          return  arr;
        }
        //找到中间项,在原有的数组中将其移除
        let middleIndex=Math.floor(arr.length/2);
        let middleValue=arr.splice(middleIndex,1)[0];
      // 新建两个左右数组
        let leftArr=[];
        let rightArr=[];
        for (let i=0;i<arr.length;i++){ 
          let item=arr[i];
          //比中间值小的值，放到左数组中。大的值放到右数组中
          item<middleValue?leftArr.push(item):rightArr.push(item);
        }
        //递归调用并且将排好的数组进行一个拼接,就是最终的结果
        //concat也不适合大量数据的排序,会消耗大量内存
        return quickSort(leftArr).concat(middleValue,quickSort(rightArr));
      }
      let testArr=[1,3,5,2,12,33,44,32,11];
      console.log(quickSort(testArr));
    </script>

1.  分治策略

> 使用分治策略，通过原地交换而不是创建合并新的数组来实现该方法。

<script>
      //定义一个交换函数，使用数组解构的方式交换。
      function swap(A,i,j) { 
        [A[i],A[j]] = [A[j],A[i]];
      }
      //定义分区函数，返回中心点的位置
      function partition(A,lo,hi){ 
        const pivot = A[hi-1];
        let i=lo,j=hi-1;
        while (i !== j){ 
          A[i] <= pivot?i++:swap(A,i,--j);
        }
        swap(A,j,hi-1);
        //返回中心点的位置
        return j;
      }
      //利用上面两个函数，进行快排的实现
      function qsort(A,lo=0,hi=A.length){ 
        if (hi-lo <= 1)  return;
        const p=partition(A,lo,hi);
        //两个分区都进行排序
        qsort(A,lo,p);
        qsort(A,p+1,hi);
      }
      //测试结果
      const  A=[12,32,44,2,456,22,10];
      qsort(A);
      console.log(A);
    </script>

参考链接附上（内置详细动画以及原理介绍，非常详细，推荐学习）  
[1：https://juejin.cn/post/6844903782019514381\#heading-21][1_https_juejin.cn_post_6844903782019514381_heading-21]  
[2：js讲解常见常用的数据结构：https://www.bilibili.com/video/BV19E411M78q?p=39&spm\_id\_from=pageDriver][2_js_https_www.bilibili.com_video_BV19E411M78q_p_39_spm_id_from_pageDriver]

[1_https_juejin.cn_post_6844903782019514381_heading-21]: https://juejin.cn/post/6844903782019514381#heading-21
[2_js_https_www.bilibili.com_video_BV19E411M78q_p_39_spm_id_from_pageDriver]: https://www.bilibili.com/video/BV19E411M78q?p=39&spm_id_from=pageDriver

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 JavaScript实现快速排序的两种方式——分治策略+数组合并

> 介绍快速排序：快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod

「爱情、让人受尽委屈。」/ 2022年11月15日 14:07/ 0 赞/ 181 阅读

相关快速排序的三种实现方式

// 把小的插入头部位置，可用于链表结构的快排一次划分 // ps:如果是链表结果，需要将这里的 ++j 换成 j = j->next 。 int Pa

快来打我*/ 2022年09月10日 03:23/ 0 赞/ 174 阅读

相关分治——合并排序

分治思路： 1. 大问题分解为子问题 2. 子问题相互独立，可以直接解决 3. 将子问题合解，得到原问题的解使用分治法进行数组排序。 \ 将一个数列等分为两半，

- 日理万妓/ 2022年08月21日 04:54/ 0 赞/ 186 阅读

相关分治法之合并排序（C实现）

include <stdio.h> void merge(int a[],int p,int q,int r) { int

迷南。/ 2022年08月09日 18:51/ 0 赞/ 185 阅读

相关 JavaScript实现的两种排序算法

想学一点原生的js，闲来无事写的冒泡排序和快速排序，欢迎指正，不喜勿喷。 // 冒泡 function PP(arr){ for( var i =

墨蓝/ 2022年07月13日 03:40/ 0 赞/ 193 阅读

相关两种交换排序代码实现(冒泡排序+快速排序【可多种方式优化】)

交换排序 1、冒泡排序 2、快速排序【可多种方式优化】交换排序 1、冒泡排序 afsaf package sort; publ

系统管理员/ 2022年05月26日 12:57/ 0 赞/ 220 阅读

相关两种链表排序法（快速排序和合并排序）

链表快速排序 class nodelist: def __init__(self,x): self.val = x

超、凢脫俗/ 2022年05月17日 04:43/ 0 赞/ 120 阅读

相关快速排序的两种实现（java）

用递归方式去做，这个比较明确，下面针对具体的方法分两种情况（1）第一种　　做两个游标，找！从前面找到比标准值大的数，从后面找到比标准值小的数，然后交换位置。以此重复

ゞ浴缸里的玫瑰/ 2022年05月16日 03:35/ 0 赞/ 164 阅读

相关 js 合并数组(两种方式)

let arr1=\[1,2,3\]; let arr2=\[4,5,6\]; console.log(arr1.concat(arr2) ) //\[1,2,3,

灰太狼/ 2022年05月11日 08:06/ 0 赞/ 201 阅读

相关 javascript三种方法实现将两个数组合并

javascript三种方法实现将两个数组合并三种方法将两个数组合并方法一：使用concat 方法二：使用循环方法三：使用apply

小灰灰/ 2020年06月02日 11:54/ 0 赞/ 783 阅读