建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號「JS每日一題」，作者灰灰 。轉(zhuǎn)載本文請聯(lián)系JS每日一題公眾號。
創(chuàng)新互聯(lián)是網(wǎng)站建設技術企業(yè)，為成都企業(yè)提供專業(yè)的網(wǎng)站建設、成都網(wǎng)站制作，網(wǎng)站設計，網(wǎng)站制作，網(wǎng)站改版等技術服務。擁有十多年豐富建站經(jīng)驗和眾多成功案例，為您定制適合企業(yè)的網(wǎng)站。十多年品質(zhì)，值得信賴！
一、是什么
快速排序(Quick Sort)算法是在冒泡排序的基礎上進行改進的一種算法，從名字上看就知道該排序算法的特點是快、效率高，是處理大數(shù)據(jù)最快的排序算法之一
實現(xiàn)的基本思想是：通過一次排序?qū)⒄麄€無序表分成相互獨立的兩部分，其中一部分中的數(shù)據(jù)都比另一部分中包含的數(shù)據(jù)的值小
然后繼續(xù)沿用此方法分別對兩部分進行同樣的操作，直到每一個小部分不可再分，所得到的整個序列就變成有序序列
例如，對無序表49，38，65，97，76，13，27，49進行快速排序，大致過程為：
首先從表中選取一個記錄的關鍵字作為分割點(稱為“樞軸”或者支點，一般選擇第一個關鍵字)，例如選取 49
將表格中大于 49 個放置于 49 的右側(cè)，小于 49 的放置于 49 的左側(cè)，假設完成后的無序表為：{27，38，13，49，65，97，76，49}
以 49 為支點，將整個無序表分割成了兩個部分，分別為{27，38，13}和{65，97，76，49}，繼續(xù)采用此種方法分別對兩個子表進行排序
前部分子表以 27 為支點，排序后的子表為{13，27，38}，此部分已經(jīng)有序;后部分子表以 65 為支點，排序后的子表為{49，65，97，76}
此時前半部分子表中的數(shù)據(jù)已完成排序;后部分子表繼續(xù)以 65 為支點，將其分割為{49}和{97，76}，前者不需排序，后者排序后的結(jié)果為{76， 97}
通過以上幾步的排序，最后由子表{13，27，38}、{49}、{49}、{65}、{76，97}構成有序表：{13，27，38，49，49，65，76，97}
二、如何實現(xiàn)
可以分成以下步驟：
分區(qū)：從數(shù)組中選擇任意一個基準，所有比基準小的元素放在基準的左邊，比基準大的元素放到基準的右邊
遞歸：遞歸地對基準前后的子數(shù)組進行分區(qū)
用代碼表示則如下：
- function quickSort (arr) {
- const rec = (arr) => {
- if (arr.length <= 1) { return arr; }
- const left = [];
- const right = [];
- const mid = arr[0]; // 基準元素
- for (let i = 1; i < arr.length; i++){
- if (arr[i] < mid) {
- left.push(arr[i]);
- } else {
- right.push(arr[i]);
- }
- }
- return [...rec(left), mid, ...rec(right)]
- }
- return res(arr)
- };
快速排序是冒泡排序的升級版，最壞情況下每一次基準元素都是數(shù)組中最小或者最大的元素，則快速排序就是冒泡排序
這種情況時間復雜度就是冒泡排序的時間復雜度：T[n] = n * (n-1) = n^2 + n，也就是O(n^2)
最好情況下是O(nlogn)，其中遞歸算法的時間復雜度公式：T[n] = aT[n/b] + f(n)，推導如下所示：
關于上述代碼實現(xiàn)的快速排序，可以看到是穩(wěn)定的
三、應用場景
快速排序時間復雜度為O(nlogn)，是目前基于比較的內(nèi)部排序中被認為最好的方法，當數(shù)據(jù)過大且數(shù)據(jù)雜亂無章時，則適合采用快速排序
參考文獻
https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842
https://www.cnblogs.com/l199616j/p/10597245.html
網(wǎng)頁題目：面試官：說說你對快速排序的理解？如何實現(xiàn)？應用場景？
當前路徑：http://www.dlmjj.cn/article/dpsddep.html
