資訊專欄INFORMATION COLUMN
摘要：源碼實(shí)現(xiàn)快速排序理論理解起來很容易，但經(jīng)常是實(shí)際寫代碼，無從下手，下面是我根據(jù)快排的步驟實(shí)現(xiàn)的遞歸快速排序。合并第一次快速排序的，，數(shù)組。
原理
快速排序離不開遞歸的思想，你如果不了解遞歸，可以結(jié)合我另外一篇文章來學(xué)習(xí) 算法入門之遞歸分而治之思想的實(shí)現(xiàn)
網(wǎng)上有有趣的動(dòng)態(tài)圖來表示快速排序，但其實(shí)我們大部分程序員都是腦子不太好使那種，即使看了形象生動(dòng)的動(dòng)態(tài)圖，還是想不到具體實(shí)現(xiàn)思路。
排序都有基本的步驟，快排也不例外，通常分為這么幾步：
1、選擇基準(zhǔn)值；
2、需要2個(gè)空數(shù)組，分別位于基準(zhǔn)值的左邊和右邊，小于基準(zhǔn)值的push到左邊的數(shù)組，大于基準(zhǔn)值的push到右邊的數(shù)組；
3、遞歸重復(fù)上面的步驟。
具體思路分析| 原始數(shù)組 | [2, 4, 1, 5, 3, 1] |
|---|---|
| 找基準(zhǔn)值 base | 末尾元素1 |
| 拆分 | left [1] <- [base] -> [2, 4, 5, 3] right |
| 遞歸 | 對left和right的數(shù)組重復(fù)第一步找新的基準(zhǔn)值 |
| 模擬遞歸1 | [1], [1], [2] <- [3] -> [4, 5] |
| 模擬遞歸2 | [1], [1], [2], [3], [4] <- [5] -> [] |
| 遞歸結(jié)束，合并數(shù)組 | [...[1], ...[1], ...[2], ...[3], ...[4], ...[5]] |
這個(gè)表格模擬快速排序的具體步驟，遞歸是將一種規(guī)律重復(fù)執(zhí)行N次的操作，我們找到快速排序的規(guī)律，然后return 遞歸，當(dāng)遞歸到數(shù)組為1個(gè)元素時(shí)，不再遞歸，因?yàn)橹皇Ｒ粋€(gè)元素的數(shù)組不需要再比較了。
JavaScript源碼實(shí)現(xiàn)快速排序理論理解起來很容易，但經(jīng)常是實(shí)際寫代碼，無從下手，下面是我根據(jù)快排的步驟實(shí)現(xiàn)的遞歸快速排序。qSort函數(shù)不復(fù)雜，他表示執(zhí)行一次找基準(zhǔn)值并且遍歷比較的過程，而你可能不太理解的是函數(shù)最后面的return。
return [...qSort(left), ...[base], ...qSort(right)]
將這個(gè)return拆分開來看。
1、返回值應(yīng)該是個(gè)數(shù)組 。
return []
2、合并第一次快速排序的left，base，right數(shù)組。接著就交給遞歸去執(zhí)行左邊和右邊數(shù)組的排序。
return [qSort(left), [base], qSort(right)]
3、因?yàn)閝Sort返回的是數(shù)組，不是數(shù)組元素，所以需要用ES6語法...來散列開。
完整代碼：
function qSort(arr) {
//聲明并初始化左邊的數(shù)組和右邊的數(shù)組
var left = [], right = []
//使用數(shù)組最后一個(gè)元素作為基準(zhǔn)值
var base = arr[arr.length - 1]
//當(dāng)數(shù)組長度只有1或者為空時(shí)，直接返回?cái)?shù)組，不需要排序
if(arr.length <= 1) return arr
//進(jìn)行遍歷
for(var i = 0, len = arr.length; i < len - 1; i++) {
if(arr[i] <= base) {
//如果小于基準(zhǔn)值，push到左邊的數(shù)組
left.push(arr[i])
} else {
//如果大于基準(zhǔn)值，push到右邊的數(shù)組
right.push(arr[i])
}
}
//遞歸并且合并數(shù)組元素
return [...qSort(left), ...[base], ...qSort(right)]
}
const arr = [2, 4, 1, 5, 3, 1]
const s = qSort(arr)
console.log(s) // [1, 1, 2, 3, 4, 5]
時(shí)間復(fù)雜度
快速排序的平均時(shí)間復(fù)雜度是O(nlogn)，最差情況是O(n2)。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/89668.html
摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。歸并排序是一種穩(wěn)定的排序方法。因此，快速排序并不穩(wěn)定。希爾排序思想先將整個(gè)待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才...
摘要：之所以把計(jì)數(shù)排序桶排序基數(shù)排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。動(dòng)畫計(jì)數(shù)排序思想找出待排序的數(shù)組中最大和最小的元素。桶排序計(jì)數(shù)排序能派上用場嗎手機(jī)號(hào)碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者...
摘要：散列表上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。在廣度優(yōu)先搜索中，我們需要用到隊(duì)列的這種思想來實(shí)現(xiàn)查找。建立了下面這個(gè)模型武漢廣州西藏上海上海武漢廣州代碼完整實(shí)現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實(shí)現(xiàn)。 什么是廣度優(yōu)先搜索？ 如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。 假設(shè)看這篇文章的都和我一樣是個(gè)前端工程師，我們要從廣度優(yōu)先搜索（BFS）中學(xué)到什么...
閱讀 1890·2021-11-22 09:34
閱讀 3180·2019-08-30 15:55
閱讀 751·2019-08-30 15:53
閱讀 2130·2019-08-30 15:52
閱讀 3061·2019-08-29 18:32
閱讀 2076·2019-08-29 17:15
閱讀 2458·2019-08-29 13:14
閱讀 3610·2019-08-28 18:05
