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