JS实现快速排序

Jrain 发布于2019-08-22 18:31 / 970人阅读

摘要：看了一篇通俗易懂的快排文章快排，下面一步一步实现整个过程。快排的基本思想上面链接的文章对快排的思路提出了一个很形象的概念挖坑填数分治法，分三个步骤实现从数组中取出一个数作为基准。

看了一篇通俗易懂的快排文章快排，下面一步一步实现整个过程。

快排的基本思想

上面链接的文章对快排的思路提出了一个很形象的概念：挖坑填数 + 分治法，分三个步骤实现：

从数组中取出一个数作为基准(pivot)。

在原数组中进行移动，将大于基准的数放到基准右边，小于基准的数放到基准左边，在基准左右形成两个子数组。

在左右子数组中反复执行步骤1、2，直到所有子数组只剩下一个数。

详细步骤

初始数组如下所示，取第一个数为基准，此时：i = 0， j = 9， pivot = arr[0] = 36，此时 i = 0 的位置就挖了一个坑，等待小于36的数来填这个坑。i 先不变，j-- 从后往前找小于基准的数：

i= 0， j = 8 时，24 < 36，将 arr[8] 挖出，放入 arr[0] 的“坑中”（实际上在写程序时，是 arr[8] 与 arr[0] 交换）。接着arr[8] 的坑怎么填？调换顺序从前往后找比基准大的数（i++，j 不变）：

i= 3， j = 8 时，43 > 36，将 arr[3] 挖出，放入 arr[8] 的“坑中”。接着去找数填 arr[3] 的坑，调换顺序从后往前找比基准小的数：

i= 3， j = 5 时，20 > 36，反向查找：

i= j = 5 时，退出，第一趟排序完成，以 arr[5] = 36 为界分为左右两个子数组：

接着在左右两个子数组中重复上面的排序过程，直到每个子数组的长度为1，排序结束！下面只给出每一步的执行结果：

JS代码

// 快排
function quickSort(arr, i, j) {
  if(i < j) {
    let left = i;
    let right = j;
    let pivot = arr[left];
    while(i < j) {
      while(arr[j] >= pivot && i < j) {  // 从后往前找比基准小的数
        j--;
      }
      if(i < j) {
        arr[i++] = arr[j];
      }
      while(arr[i] <= pivot && i < j) {  // 从前往后找比基准大的数
        i++;
      }
      if(i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
    return arr;
  }
}

// example
let arr = [2, 10, 4, 1, 0, 9, 5 ,2];
console.log(quickSort(arr, 0 , arr.length-1));

有的书上是以中间的数作为基准数的，要实现这个方便非常方便，直接将中间的数和第一个数进行交换就可以了。

function quickSort(arr, i, j) {
  if(i < j) {
    let left = i;
    let right = j;
    let mid = Math.floor((left+right)/2);
    let temp = arr[left];
    arr[left] = arr[mid];
    arr[mid] = temp;
    let pivot = arr[left];
    while(i < j) {
      while(arr[j] >= pivot && i < j) {  // 从后往前找比基准小的数
        j--;
      }
      if(i < j) {
        arr[i++] = arr[j];
      }
      while(arr[i] <= pivot && i < j) {  // 从前往后找比基准大的数
        i++;
      }
      if(i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
    return arr;
  }
}

GPU云服务器云服务器 js快速排序快速排序法js js实现table排序快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95950.html

js实现冒泡排序,快速排序,选择排序

摘要：用冒泡排序快速排序选择排序冒泡排序冒泡排序是比较经典的排序方法，是一种用时间换空间的排序方法。找到并交换的时候，指针位置不变。选择排序没趟都会产生最小值，它不是相邻元素的比较而是在该元素设置一个索引。选择排序循环找到从开始到最后的最小的数用js冒泡排序,快速排序,选择排序 1.冒泡排序冒泡排序是比较经典的排序方法，是一种用时间换空间的排序方法。我总结了一下它的特点：（1）它的时间复...

bbbbbb 2019-08-22 16:56 评论0 收藏0
关于JS的快速排序实现方法

摘要：所有关键字比该记录关键字小的记录放置在前一部分，所有比它大的记录放置在后一部分，并把改记录排在这两部分的中间称为该记录归位，这个过程称作一次快速排序。代码如下大佬的代码还是比较厉害的，简单易懂，佩服以上就是相关的快速排序的实现方法由于自己不是计算机专业，数据结构没有太多研究，曾经面试时有被问过关于快速排序以及冒泡排序的写法，冒泡排序比较简单，当时能回答出来，但是快速排序当时就比较懵逼...

LeexMuller 2019-08-21 17:40 评论0 收藏0
js算法-快速排序(Quicksort)

摘要：快速排序英语，又称划分交换排序，简称快排，一种排序算法，最早由东尼霍尔提出。快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(nLogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nLogn)通常明显比其他算...

Taste 2019-08-23 14:35 评论0 收藏0
排序算法速度测试（插入排序、二分法插入、选择排序、快速排序、堆排序）js实现

摘要：公共函数库用于取出随机排列的数字原数组给原数组赋值排序算法插入排序时间复杂度二分法插入排序选择排序快速排序一堆排序测试用例插入排序时间测试二分法插入排序时间测试选择排序时间测试快速排序时间测试一堆公共函数库（用于取出随机排列的数字） module.exports={ randomIntegerArray:function(count){ var origina...

mochixuan 2019-08-20 16:04 评论0 收藏0
快速排序js实现

摘要：然后再分别对基数左边和右边的数组进行相同的操作，直到数组中只有一个元素时，返回该数组。快速排序算法今天大概讲下使用js实现快速排序算法：快速排序算法的思想类似于二分法，每次都是在数组中选择一个基数（可以是任意一个位置的数，不过一般选择中间的数字或者最左边的数字），每一轮结束后，比该基数小的数都位于该基数的左边，比该基数大的数都位于该基数的右边。然后再分别对基数左边和右边的数组进行...

zhoutk 2019-08-22 16:22 评论0 收藏0
js 排序算法之快速排序

摘要：快速排序是一种划分交换排序。快速排序基于冒泡递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。...

Eidesen 2019-08-23 11:38 评论0 收藏0