【JavaScript快速排序算法】不同版本原理分析

說明

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

實(shí)現(xiàn)過程

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

示意圖

quick1.png

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

性能分析

平均時(shí)間復(fù)雜度：O(NlogN)
最佳時(shí)間復(fù)雜度：O(NlogN)
最差時(shí)間復(fù)雜度：O(N^2)
空間復(fù)雜度：根據(jù)實(shí)現(xiàn)方式的不同而不同，可以查看不同版本的源碼

代碼

快排方式1, 新建數(shù)組遞歸版本。無需交換，每個(gè)分區(qū)都是新數(shù)組，數(shù)量龐大。

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

function quickSort1(arr) {
  // 數(shù)組長(zhǎng)度為1就不再分解
  console.log('origin array:', arr)
  if (arr.length <= 1) {
    return arr
  }

  var pivot
  const left = []
  const right = []
  // 設(shè)置中間數(shù)，取最中間的項(xiàng)
  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)
    // 當(dāng)中間基數(shù)等于i時(shí)跳過?；鶖?shù)數(shù)待遞歸完成時(shí)合并到到新數(shù)組。
    if (midIndex === i) {
      continue
    }
    // 當(dāng)前數(shù)組里面的項(xiàng)小于基數(shù)則添加到左側(cè)
    if (arr[i] < pivot) {
      left.push(arr[i])
      // 大于等于則添加到右側(cè)
    } else {
      right.push(arr[i])
    }
  }

  arr = quickSort1(left).concat(pivot, quickSort1(right))
  console.log('sorted array:', arr)
  // 遞歸調(diào)用遍歷左側(cè)和右側(cè)，再將中間值連接起來
  return arr
}

遞歸的過程

// 基于中間數(shù)進(jìn)行遞歸分解：
      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]
// 將遞歸后的最小單元和基數(shù)連接起來
// 得到：[7, 8, 9, 10, 11, 12, 13]

快排方式2, 標(biāo)準(zhǔn)分區(qū)遞歸版本。左右分區(qū)遞歸交換排序，無需新建數(shù)組。

這個(gè)版本是最常見的標(biāo)準(zhǔn)分區(qū)版本，簡(jiǎn)單好懂。先寫一個(gè)分區(qū)函數(shù)，依據(jù)基準(zhǔn)值把成員項(xiàng)分為左右兩部分?；鶞?zhǔn)值可以是數(shù)列中的任意一項(xiàng)，為了交換方便，基準(zhǔn)值一般最左或最右側(cè)項(xiàng)。把小于基準(zhǔn)值的放在左側(cè)，大于基準(zhǔn)值的放在右側(cè)，最后返回分區(qū)索引。這樣就得到一個(gè)基于基準(zhǔn)值的左右兩個(gè)部分。再將左右兩個(gè)部分，分別進(jìn)行分區(qū)邏輯的遞歸調(diào)用，當(dāng)左右值相等，也就是最小分區(qū)只有1項(xiàng)時(shí)終止。

// 分區(qū)函數(shù)，負(fù)責(zé)把數(shù)組分按照基準(zhǔn)值分為左右兩部分
// 小于基準(zhǔn)的在左側(cè)，大于基準(zhǔn)的在右側(cè)最后返回基準(zhǔn)值的新下標(biāo)
function partition(arr, left, right) {
  // 基準(zhǔn)值可以是left與right之間的任意值，再將基準(zhǔn)值移動(dòng)至最左或最右即可。
  // 直接基于中間位置排序，則需要基于中間位置左右交換，參加基于中間位置交換的版本。
  // 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++) {
    // 如果比較項(xiàng)小于基準(zhǔn)值則進(jìn)行交換，并且分區(qū)索引增加1位
    // 也就是將大于基準(zhǔn)值的全部往右側(cè)放，以分區(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ū)遞歸調(diào)用。
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, 標(biāo)準(zhǔn)左右交換遞歸版本?；谥虚g位置不斷左右交換，無需新建數(shù)組。

此版本基于中間位置，建立雙指針，同時(shí)從前往后和從后往前遍歷，從左側(cè)找到大于基準(zhǔn)值的項(xiàng)，從右側(cè)找到小于基準(zhǔn)值的項(xiàng)。
再將大于基準(zhǔn)值的挪到右側(cè)，將小于基準(zhǔn)值的項(xiàng)挪到左側(cè)，直到左側(cè)位置大于右側(cè)時(shí)終止。左側(cè)位置小于基準(zhǔn)位置則遞歸調(diào)用左側(cè)區(qū)間，右側(cè)大于基準(zhǔn)位置則遞歸調(diào)用右側(cè)區(qū)間，直到所有項(xiàng)排列完成。

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]

  // 當(dāng)左側(cè)小于等于右側(cè)則表示還有項(xiàng)沒有對(duì)比，需要繼續(xù)
  while (i <= j) {
    // 當(dāng)左側(cè)小于基準(zhǔn)時(shí)查找位置右移，直到找出比基準(zhǔn)值大的位置來
    while (arr[i] < pivot) {
      console.log('arr[i] < pivot:', ' i=' + i + ' j=' + j + ' pivot=' + pivot)
      i++
    }
    // 當(dāng)前右側(cè)大于基準(zhǔn)時(shí)左移，直到找出比基準(zhǔn)值小的位置來
    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)

    // 當(dāng)左側(cè)位置小于等于右側(cè)時(shí)，將數(shù)據(jù)交換，小的交換到基準(zhǔn)左側(cè)，大的交換到右側(cè)
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      // 縮小搜查范圍，直到左側(cè)都小于基數(shù)，右側(cè)都大于基數(shù)
      i++
      j--
    }
  }

  // 左側(cè)小于基數(shù)位置，不斷遞歸左邊部分
  if (left < j) {
    console.log('left < j:recursion:  left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]' + arr)
    quickSort3(arr, left, j)
  }
  // 基數(shù)位置小于右側(cè)，不斷遞歸右側(cè)部分
  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, 非遞歸左右交換版本?；谥虚g位置不斷左右交換，利用stack或queue遍歷。

這種方式標(biāo)準(zhǔn)左右交換遞歸版本的非遞歸版本，其原理一樣，只是不再遞歸調(diào)用，而是通過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
  // 與標(biāo)準(zhǔn)遞歸版相同，只是將遞歸改為遍歷棧的方式
  // 先將左右各取一個(gè)入棧
  stack.push(left)
  stack.push(right)

  while (stack.length) {
    // 如果棧內(nèi)還有數(shù)據(jù)，則一并馬上取出，其他邏輯與標(biāo)準(zhǔn)遞歸版同
    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) {
      // 與遞歸版不同，這里當(dāng)左側(cè)小于基數(shù)位置時(shí)添加到棧中，以便繼續(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) {
      // 當(dāng)右側(cè)大于等于基數(shù)位置時(shí)添加到棧中，以便繼續(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
}

測(cè)試

(function () {
  const arr = [7, 11, 9, 10, 12, 13, 8]
  // 構(gòu)建數(shù)列，可以任意構(gòu)建，支持負(fù)數(shù)，也不限浮點(diǎn)
  // 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')
})()

/**
// 測(cè)試結(jié)果
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
 */

鏈接

多種語(yǔ)言實(shí)現(xiàn)快速排序算法源碼：https://github.com/microwind/algorithms/tree/master/sorts/quicksort

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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容