Javascript算法——快速排序

马忠志发布于2019-08-20 16:35 / 2845人阅读

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。这里主要介绍快速排序。快速排序是一种既不浪费空间又可以快一点的排序算法。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。这里主要介绍快速排序。

一图胜千言：

1. 算法描述

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用。快速排序是一种既不浪费空间又可以快一点的排序算法。

2. 算法步骤

先从数列中取出一个数作为“基准”。

分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。

再对左右区间重复第二步，直到各区间只有一个数。

3. 算法实现

var quickSort = function(arr) {
    if (arr.length <= 1) { return arr; }
    var pivotIndex = Math.floor(arr.length / 2);   //基准位置（理论上可任意选取）
    var pivot = arr.splice(pivotIndex, 1)[0];  //基准数
    var left = [];
    var right = [];
    for (var 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));  //链接左数组、基准数构成的数组、右数组
};

云服务器 GPU云服务器快速排序算法最好的快速排序算法最快速的排序算法快速排序

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

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

深入浅出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 评论0 收藏0
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
算法系列——JavaScript快速排序思想实现

摘要：源码实现快速排序理论理解起来很容易，但经常是实际写代码，无从下手，下面是我根据快排的步骤实现的递归快速排序。合并第一次快速排序的，，数组。原理快速排序离不开递归的思想，你如果不了解递归，可以结合我另外一篇文章来学习算法入门之递归分而治之思想的实现网上有有趣的动态图来表示快速排序，但其实我们大部分程序员都是脑子不太好使那种，即使看了形象生动的动态图，还是想不到具体实现思路。排序...

lentrue 2019-08-21 17:33 评论0 收藏0
JavaScript算法详解——快速排序

摘要：常见排序实现的常见排序算法有冒泡排序选择排序插入排序谢尔排序快速排序递归快速排序堆栈归并排序堆排序过程快速排序的思想很简单，整个排序过程只需要三步在数据集之中，找一个基准点建立两个数组，分别存储左边和右边的数组利用递归进行下次比较看一个网页常见排序 javaScript实现的常见排序算法有:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序 ...

zhouzhou 2019-08-21 10:19 评论0 收藏0