美文网首页
JS实现快速排序算法

JS实现快速排序算法

作者: 蓝醇 | 来源:发表于2019-06-06 16:33 被阅读0次

采用了分治的思想
(1)在数据集之中,选择一个元素作为"基准"(pivot)。
(2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
(3)对"基准"左边和右边的两个子集,递归地排序 。直到所有子集只剩下一个元素为止。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  } 
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0]; 
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]); 
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(array));

相关文章

  • 七大排序算法之快速排序

    七大排序算法之快速排序 @(算法笔记)[排序算法, 快速排序, C++实现] [TOC] 快速排序的介绍: 快速排...

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • 手撕代码 之 快速排序

    1.实现快速排序算法 问题描述给定一个无序数组int[ ] a,使用快速排序算法进行排序。 解题思路对于快速排序,...

  • JS实现快速排序算法

    快速排序 快速排序 由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割...

  • JS实现快速排序算法

    采用了分治的思想(1)在数据集之中,选择一个元素作为"基准"(pivot)。(2)所有小于"基准"的元素,都移到"...

  • 三大排序算法

    归并排序[稳定的排序算法] 递归实现 非递归实现 快速排序[不稳定的排序算法] 堆排序[不稳定的排序算法]

  • 快速排序

    手写java版快速排序算法实现

  • 基础算法|快速排序

    快速排序(Quicksort),是对冒泡排序算法的一种改进。 快速排序算法通过多次比较和交换来实现排序,其排序流程...

  • 快速排序&快速排序与归并排序的对比

    快速排序算法 快速排序算法是从上到下解决问题使用递归实现,通过巧妙的方式,实现原地排序 分析时间复杂度O(nlog...

  • 算法

    算法和数据结构 十大排序实现原理?使用场景js中sort使用的是哪种排序?sort使用的是插入排序和快速排序结合的...

网友评论

      本文标题:JS实现快速排序算法

      本文链接:https://www.haomeiwen.com/subject/aoeuxctx.html