JavaScript快速排序算法不同版本原理解析

更新時間：2023年08月15日 09:58:23 作者：刀法如飛

這篇文章主要為大家介紹了JavaScript快速排序算法不同版本原理解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

說明

快速排序（QuickSort），又稱分區(qū)交換排序（partition-exchange sort），簡稱快排?？炫攀且环N通過基準劃分區(qū)塊，再不斷交換左右項的排序方式，其采用了分治法，減少了交換的次數。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸或迭代進行，以此讓整個數列變成有序序列。

實現過程

在待排序區(qū)間找到一個基準點(pivot)，便于理解一般是位于數組中間的那一項。
逐個循環(huán)數組將小于基準的項放左側，將大于基準的項放在右側。一般通過交換的方式來實現。
將基準點左側全部項和基點右側全部項分別通過遞歸(或迭代)方式重復第1項，直到所有數組都交換完成。

示意圖

解釋：以某個數字為基點，這里取最右側的數字8，以基點劃分為兩個區(qū)間，將小于8的數字放在左側區(qū)間，將大于8的數字放在右側區(qū)間。再將左側區(qū)間和右側區(qū)間分別放到遞歸，按照最右側為基點，繼續(xù)分解。直到分解完畢，排序完成。這是其中一種常見的分區(qū)遞歸法，除了這種方式外，還有其他實現方式。

性能分析

平均時間復雜度：O(NlogN)

最佳時間復雜度：O(NlogN)

最差時間復雜度：O(N^2)

空間復雜度：根據實現方式的不同而不同，可以查看不同版本的源碼

快排方式1, 新建數組遞歸版本

無需交換，每個分區(qū)都是新數組，數量龐大。

這個版本利用了JS數組可變且隨意拼接的特性，讓每個分區(qū)都是一個新數組，從而無需交換數組項。
這個方式非常簡單易懂，但理論上來講不是完全意義上的快排，效率較差。

function quickSort1(arr) {
  // 數組長度為1就不再分解
  console.log('origin array:', arr)
  if (arr.length <= 1) {
    return arr
  }
  var pivot
  const left = []
  const right = []
  // 設置中間數，取最中間的項
  var midIndex = Math.floor(arr.length / 2)
  pivot = arr[midIndex]
  for (var i = 0, l = arr.length; i < l; i++) {
    console.log('i=' + i + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
    // 當中間基數等于i時跳過?；鶖禂荡f歸完成時合并到到新數組。
    if (midIndex === i) {
      continue
    }
    // 當前數組里面的項小于基數則添加到左側
    if (arr[i] < pivot) {
      left.push(arr[i])
      // 大于等于則添加到右側
    } else {
      right.push(arr[i])
    }
  }
  arr = quickSort1(left).concat(pivot, quickSort1(right))
  console.log('sorted array:', arr)
  // 遞歸調用遍歷左側和右側，再將中間值連接起來
  return arr
}

遞歸的過程

// 基于中間數進行遞歸分解：
      f([7, 11, 9, 10, 12, 13, 8])
            /       10          \
      f([7, 9, 8])           f([11, 12, 13])
        /   9    \             /    12     \
   f([7, 8])    f([])       f([11])       f[13]
   /   8  \
f([7]) f([])
  [7]
// 將遞歸后的最小單元和基數連接起來
// 得到：[7, 8, 9, 10, 11, 12, 13]

快排方式2, 標準分區(qū)遞歸版本

左右分區(qū)遞歸交換排序，無需新建數組。

這個版本是最常見的標準分區(qū)版本，簡單好懂。先寫一個分區(qū)函數，依據基準值把成員項分為左右兩部分。基準值可以是數列中的任意一項，為了交換方便，基準值一般最左或最右側項。把小于基準值的放在左側，大于基準值的放在右側，最后返回分區(qū)索引。這樣就得到一個基于基準值的左右兩個部分。再將左右兩個部分，分別進行分區(qū)邏輯的遞歸調用，當左右值相等，也就是最小分區(qū)只有1項時終止。

// 分區(qū)函數，負責把數組分按照基準值分為左右兩部分
// 小于基準的在左側，大于基準的在右側最后返回基準值的新下標
function partition(arr, left, right) {
  // 基準值可以是left與right之間的任意值，再將基準值移動至最左或最右即可。
  // 直接基于中間位置排序，則需要基于中間位置左右交換，參加基于中間位置交換的版本。
  // var tmpIndex = Math.floor((right - left) / 2)
  // ;[arr[left + tmpIndex], arr[right]] = [arr[right], arr[left + tmpIndex]]
  var pivotIndex = right
  var pivot = arr[pivotIndex]
  var partitionIndex = left - 1
  for (var i = left; i < right; i++) {
    // 如果比較項小于基準值則進行交換，并且分區(qū)索引增加1位
    // 也就是將大于基準值的全部往右側放，以分區(qū)索引為分割線
    if (arr[i] < pivot) {
      partitionIndex++
      if (partitionIndex !== i) {
        [arr[partitionIndex], arr[i]] = [arr[i], arr[partitionIndex]]
      }
    }
  }
  partitionIndex++;
  [arr[partitionIndex], arr[pivotIndex]] = [arr[pivotIndex], arr[partitionIndex]]
  return partitionIndex
}
// 分區(qū)遞歸版本，分區(qū)遞歸調用。
function quickSort2(arr, left, right) {
  left = left !== undefined ? left : 0
  right = right !== undefined ? right : arr.length - 1
  if (left < right) {
    var pivot = partition(arr, left, right)
    quickSort2(arr, left, pivot - 1)
    quickSort2(arr, pivot + 1, right)
  }
  return arr
}

快排方式3, 標準左右交換遞歸版本

基于中間位置不斷左右交換，無需新建數組。

此版本基于中間位置，建立雙指針，同時從前往后和從后往前遍歷，從左側找到大于基準值的項，從右側找到小于基準值的項。

再將大于基準值的挪到右側，將小于基準值的項挪到左側，直到左側位置大于右側時終止。左側位置小于基準位置則遞歸調用左側區(qū)間，右側大于基準位置則遞歸調用右側區(qū)間，直到所有項排列完成。

function quickSort3(arr, left, right) {
  var i = left = left !== undefined ? left : 0
  var j = right = right !== undefined ? right : arr.length - 1
  // 確定中間位置，基于中間位置不停左右交換
  var midIndex = Math.floor((i + j) / 2)
  var pivot = arr[midIndex]
  // 當左側小于等于右側則表示還有項沒有對比，需要繼續(xù)
  while (i <= j) {
    // 當左側小于基準時查找位置右移，直到找出比基準值大的位置來
    while (arr[i] < pivot) {
      console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
      i++
    }
    // 當前右側大于基準時左移，直到找出比基準值小的位置來
    while (arr[j] > pivot) {
      console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
      j--
    }
    console.log('  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + ' midIndex=' + midIndex + ' pivot=' + pivot + ' arr[]=' + arr)
    // 當左側位置小于等于右側時，將數據交換，小的交換到基準左側，大的交換到右側
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      // 縮小搜查范圍，直到左側都小于基數，右側都大于基數
      i++
      j--
    }
  }
  // 左側小于基數位置，不斷遞歸左邊部分
  if (left < j) {
    console.log('left < j:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
    quickSort3(arr, left, j)
  }
  // 基數位置小于右側，不斷遞歸右側部分
  if (i < right) {
    console.log('i < right:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
    quickSort3(arr, i, right)
  }
  return arr
}

快排方式4, 非遞歸左右交換版本

基于中間位置不斷左右交換，利用stack或queue遍歷。

這種方式標準左右交換遞歸版本的非遞歸版本，其原理一樣，只是不再遞歸調用，而是通過stack來模擬遞歸效果。這種方式性能最好。

function quickSort4(arr, left, right) {
  left = left !== undefined ? left : 0
  right = right !== undefined ? right : arr.length - 1
  var stack = []
  var i, j, midIndex, pivot, tmp
  // 與標準遞歸版相同，只是將遞歸改為遍歷棧的方式
  // 先將左右各取一個入棧
  stack.push(left)
  stack.push(right)
  while (stack.length) {
    // 如果棧內還有數據，則一并馬上取出，其他邏輯與標準遞歸版同
    j = right = stack.pop()
    i = left = stack.pop()
    midIndex = Math.floor((i + j) / 2)
    pivot = arr[midIndex]
    while (i <= j) {
      while (arr[i] < pivot) {
        console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
        i++
      }
      while (arr[j] > pivot) {
        console.log('arr[j] > pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot + 'arr[]=' + arr)
        j--
      }
      if (i <= j) {
        tmp = arr[j]
        arr[j] = arr[i]
        arr[i] = tmp
        i++
        j--
      }
    }
    if (left < j) {
      // 與遞歸版不同，這里當左側小于基數位置時添加到棧中，以便繼續(xù)循環(huán)
      console.log('left < j:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
      stack.push(left)
      stack.push(j)
    }
    if (i < right) {
      // 當右側大于等于基數位置時添加到棧中，以便繼續(xù)循環(huán)
      console.log('i < right:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr)
      stack.push(i)
      stack.push(right)
    }
  }
  return arr
}

測試

(function () {
  const arr = [7, 11, 9, 10, 12, 13, 8]
  // 構建數列，可以任意構建，支持負數，也不限浮點
  // const arr = [17, 31, 12334, 9.545, -10, -12, 1113, 38]
  console.time('sort1')
  const arr1 = arr.slice(0)
  console.log('sort1 origin:', arr1)
  console.log('\r\nquickSort1 sorted:', quickSort1(arr1))
  console.timeEnd('sort1')
  console.time('sort2')
  const arr2 = arr.slice(0)
  console.log('sort2 origin:', arr2)
  console.log('\r\nquickSort2 sorted:', quickSort2(arr2))
  console.timeEnd('sort2')
  console.time('sort3')
  const arr3 = arr.slice(0)
  console.log('sort3 origin:', arr3)
  console.log('\r\nquickSort3 sorted:', quickSort3(arr3))
  console.timeEnd('sort3')
  console.time('sort4')
  const arr4 = arr.slice(0)
  console.log('sort4 origin:', arr4)
  console.log('\r\nquickSort4 sorted:', quickSort4(arr4))
  console.timeEnd('sort4')
})()
/**
// 測試結果
jarry@jarrys-MacBook-Pro quicksort % node quick_sort.js
sort1 origin: [
   7, 11, 9, 10,
  12, 13, 8
]
origin array: [
   7, 11, 9, 10,
  12, 13, 8
]
i=0 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=1 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=2 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=3 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=4 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=5 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
i=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
origin array: [ 7, 9, 8 ]
i=0 midIndex=1 pivot=9 arr[]=7,9,8
i=1 midIndex=1 pivot=9 arr[]=7,9,8
i=2 midIndex=1 pivot=9 arr[]=7,9,8
origin array: [ 7, 8 ]
i=0 midIndex=1 pivot=8 arr[]=7,8
i=1 midIndex=1 pivot=8 arr[]=7,8
origin array: [ 7 ]
origin array: []
sorted array: [ 7, 8 ]
origin array: []
sorted array: [ 7, 8, 9 ]
origin array: [ 11, 12, 13 ]
i=0 midIndex=1 pivot=12 arr[]=11,12,13
i=1 midIndex=1 pivot=12 arr[]=11,12,13
i=2 midIndex=1 pivot=12 arr[]=11,12,13
origin array: [ 11 ]
origin array: [ 13 ]
sorted array: [ 11, 12, 13 ]
sorted array: [
   7,  8,  9, 10,
  11, 12, 13
]
quickSort1 sorted: [
   7,  8,  9, 10,
  11, 12, 13
]
sort1: 9.824ms
sort2 origin: [
   7, 11, 9, 10,
  12, 13, 8
]
partitioned arr= [
   7,  8,  9, 10,
  12, 13, 11
] partitionIndex: 1 left= [ 7 ] arr[partitionIndex]= 8 right= [ 8, 9, 10, 12, 13, 11 ] [
   7,  8,  9, 10,
  12, 13, 11
]
partitioned arr= [
   7,  8,  9, 10,
  11, 13, 12
] partitionIndex: 4 left= [ 9, 10 ] arr[partitionIndex]= 11 right= [ 11, 13, 12 ] [
   7,  8,  9, 10,
  11, 13, 12
]
partitioned arr= [
   7,  8,  9, 10,
  11, 13, 12
] partitionIndex: 3 left= [ 9 ] arr[partitionIndex]= 10 right= [ 10 ] [
   7,  8,  9, 10,
  11, 13, 12
]
partitioned arr= [
   7,  8,  9, 10,
  11, 12, 13
] partitionIndex: 5 left= [] arr[partitionIndex]= 12 right= [ 12, 13 ] [
   7,  8,  9, 10,
  11, 12, 13
]
quickSort2 sorted: [
   7,  8,  9, 10,
  11, 12, 13
]
sort2: 1.15ms
sort3 origin: [
   7, 11, 9, 10,
  12, 13, 8
]
arr[i] < pivot:  i=0 j=6 pivot=10
  left=0 right=6 i=1 j=6 midIndex=3 pivot=10 arr[]=7,11,9,10,12,13,8
arr[i] < pivot:  i=2 j=5 pivot=10
arr[j] > pivot:  i=3 j=5 pivot=10
arr[j] > pivot:  i=3 j=4 pivot=10
  left=0 right=6 i=3 j=3 midIndex=3 pivot=10 arr[]=7,8,9,10,12,13,11
left < j:recursion:  left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
arr[i] < pivot:  i=0 j=2 pivot=8
arr[j] > pivot:  i=1 j=2 pivot=8
  left=0 right=2 i=1 j=1 midIndex=1 pivot=8 arr[]=7,8,9,10,12,13,11
i < right:recursion:  left=0 right=6 i=4 j=2arr[]7,8,9,10,12,13,11
arr[i] < pivot:  i=4 j=6 pivot=13
  left=4 right=6 i=5 j=6 midIndex=5 pivot=13 arr[]=7,8,9,10,12,13,11
left < j:recursion:  left=4 right=6 i=6 j=5arr[]7,8,9,10,12,11,13
  left=4 right=5 i=4 j=5 midIndex=4 pivot=12 arr[]=7,8,9,10,12,11,13
quickSort3 sorted: [
   7,  8,  9, 10,
  11, 12, 13
]
sort3: 0.595ms
sort4 origin: [
   7, 11, 9, 10,
  12, 13, 8
]
arr[i] < pivot:  i=0 j=6 pivot=10arr[]=7,11,9,10,12,13,8
arr[i] < pivot:  i=2 j=5 pivot=10arr[]=7,8,9,10,12,13,11
arr[j] > pivot:  i=3 j=5 pivot=10arr[]=7,8,9,10,12,13,11
arr[j] > pivot:  i=3 j=4 pivot=10arr[]=7,8,9,10,12,13,11
left < j:recursion:  left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
i < right:recursion:  left=0 right=6 i=4 j=2arr[]=7,8,9,10,12,13,11
arr[i] < pivot:  i=4 j=6 pivot=13arr[]=7,8,9,10,12,13,11
left < j:recursion:  left=4 right=6 i=6 j=5arr[]=7,8,9,10,12,11,13
arr[i] < pivot:  i=0 j=2 pivot=8arr[]=7,8,9,10,11,12,13
arr[j] > pivot:  i=1 j=2 pivot=8arr[]=7,8,9,10,11,12,13
quickSort4 sorted: [
   7,  8,  9, 10,
  11, 12, 13
]
sort4: 0.377ms
 */

鏈接

多種語言實現快速排序算法源碼：https://github.com/microwind/algorithms/tree/master/sorts/quicksort

其他排序算法源碼：https://github.com/microwind/algorithms

以上就是JavaScript快速排序算法不同版本原理解析的詳細內容，更多關于JavaScript快速排序算法的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: