算法系列——JavaScript快速排序思想實現

lentrue 發布于2019-08-21 17:33 / 2469人閱讀

摘要：源碼實現快速排序理論理解起來很容易，但經常是實際寫代碼，無從下手，下面是我根據快排的步驟實現的遞歸快速排序。合并第一次快速排序的，，數組。

原理

快速排序離不開遞歸的思想，你如果不了解遞歸，可以結合我另外一篇文章來學習算法入門之遞歸分而治之思想的實現

網上有有趣的動態圖來表示快速排序，但其實我們大部分程序員都是腦子不太好使那種，即使看了形象生動的動態圖，還是想不到具體實現思路。

排序都有基本的步驟，快排也不例外，通常分為這么幾步：

1、選擇基準值；

2、需要2個空數組，分別位于基準值的左邊和右邊，小于基準值的push到左邊的數組，大于基準值的push到右邊的數組；

3、遞歸重復上面的步驟。

具體思路分析

原始數組	[2, 4, 1, 5, 3, 1]
找基準值 base	末尾元素1
拆分	left [1] <- [base] -> [2, 4, 5, 3] right
遞歸	對left和right的數組重復第一步找新的基準值
模擬遞歸1	[1], [1], [2] <- [3] -> [4, 5]
模擬遞歸2	[1], [1], [2], [3], [4] <- [5] -> []
遞歸結束，合并數組	[...[1], ...[1], ...[2], ...[3], ...[4], ...[5]]

這個表格模擬快速排序的具體步驟，遞歸是將一種規律重復執行N次的操作，我們找到快速排序的規律，然后return 遞歸，當遞歸到數組為1個元素時，不再遞歸，因為只剩一個元素的數組不需要再比較了。

JavaScript源碼實現快速排序

理論理解起來很容易，但經常是實際寫代碼，無從下手，下面是我根據快排的步驟實現的遞歸快速排序。qSort函數不復雜，他表示執行一次找基準值并且遍歷比較的過程，而你可能不太理解的是函數最后面的return。

return [...qSort(left), ...[base], ...qSort(right)]

將這個return拆分開來看。

1、返回值應該是個數組。

return []

2、合并第一次快速排序的left，base，right數組。接著就交給遞歸去執行左邊和右邊數組的排序。

return [qSort(left), [base], qSort(right)]

3、因為qSort返回的是數組，不是數組元素，所以需要用ES6語法...來散列開。

完整代碼：

function qSort(arr) {
  //聲明并初始化左邊的數組和右邊的數組
  var left = [], right = []
  //使用數組最后一個元素作為基準值
  var base = arr[arr.length - 1]
  //當數組長度只有1或者為空時，直接返回數組，不需要排序
  if(arr.length <= 1) return arr
  
  //進行遍歷
  for(var i = 0, len = arr.length; i < len - 1; i++) {
    if(arr[i] <= base) {
    //如果小于基準值，push到左邊的數組
      left.push(arr[i])
    } else {
    //如果大于基準值，push到右邊的數組
      right.push(arr[i])
    }
  }
  //遞歸并且合并數組元素
  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)。

云服務器 GPU云服務器快速排序算法最好的快速排序算法最快速的排序算法 javascript編程思想

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/89668.html

JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

摘要：之所以把計數排序桶排序基數排序放在一起比較，是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者...

Awbeci 2019-08-26 10:24 評論0 收藏0
算法系列——JavaScript中廣度優先搜索思想實現

摘要：散列表上面的地圖向我們展示了如何用廣度優先搜索的思想找到北京到廣州的最短路線。在廣度優先搜索中，我們需要用到隊列的這種思想來實現查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實現，利用遞歸和廣度優先搜索的思想實現。什么是廣度優先搜索？如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。假設看這篇文章的都和我一樣是個前端工程師，我們要從廣度優先搜索（BFS）中學到什么...

everfly 2019-08-21 17:36 評論0 收藏0