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