Javascript算法——快速排序

馬忠志發布于2019-08-20 16:35 / 2876人閱讀

摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。這里主要介紹快速排序。快速排序是一種既不浪費空間又可以快一點的排序算法。

常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。這里主要介紹快速排序。

一圖勝千言：

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云服務器快速排序算法最好的快速排序算法最快速的排序算法快速排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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