說明
快速排序（QuickSort），又稱磁區交換排序（partition-exchange sort），簡稱快排，快排是一種通過基準劃磁區塊，再不斷交換左右項的排序方式，其采用了分治法，減少了交換的次數，它的基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回或迭代進行，以此讓整個數列變成有序序列，
實作程序
- 在待排序區間找到一個基準點(pivot)，便于理解一般是位于陣列中間的那一項，
- 逐個回圈陣列將小于基準的項放左側，將大于基準的項放在右側，一般通過交換的方式來實作，
- 將基準點左側全部項和基點右側全部項分別通過遞回(或迭代)方式重復第1項，直到所有陣列都交換完成，
示意圖
解釋：以某個數字為基點，這里取最右側的數字8，以基點劃分為兩個區間，將小于8的數字放在左側區間，將大于8的數字放在右側區間，再將左側區間和右側區間分別放到遞回，按照最右側為基點，繼續分解，直到分解完畢，排序完成，這是其中一種常見的磁區遞回法，除了這種方式外，還有其他實作方式，
性能分析
平均時間復雜度：O(NlogN)
最佳時間復雜度：O(NlogN)
最差時間復雜度：O(N^2)
空間復雜度：根據實作方式的不同而不同，可以查看不同版本的原始碼
代碼
快排方式1, 新建陣列遞回版本，無需交換，每個磁區都是新陣列，數量龐大，
這個版本利用了JS陣列可變且隨意拼接的特性，讓每個磁區都是一個新陣列，從而無需交換陣列項，
這個方式非常簡單易懂，但理論上來講不是完全意義上的快排，效率較差，
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時跳過，基數數待遞回完成時合并到到新陣列， 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, 標準磁區遞回版本，左右磁區遞回交換排序，無需新建陣列，
這個版本是最常見的標準磁區版本，簡單好懂，先寫一個磁區函式，依據基準值把成員項分為左右兩部分，基準值可以是數列中的任意一項，為了交換方便，基準值一般最左或最右側項，把小于基準值的放在左側，大于基準值的放在右側，最后回傳磁區索引，這樣就得到一個基于基準值的左右兩個部分，再將左右兩個部分，分別進行磁區邏輯的遞回呼叫，當左右值相等，也就是最小磁區只有1項時終止，
// 磁區函式，負責把陣列分按斬訓準值分為左右兩部分 // 小于基準的在左側，大于基準的在右側最后回傳基準值的新下標 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++) { // 如果比較項小于基準值則進行交換，并且磁區索引增加1位 // 也就是將大于基準值的全部往右側放，以磁區索引為分割線 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 } // 磁區遞回版本，磁區遞回呼叫， 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, 標準左右交換遞回版本，基于中間位置不斷左右交換，無需新建陣列，
此版本基于中間位置，建立雙指標，同時從前往后和從后往前遍歷，從左側找到大于基準值的項，從右側找到小于基準值的項，
再將大于基準值的挪到右側，將小于基準值的項挪到左側，直到左側位置大于右側時終止，左側位置小于基準位置則遞回呼叫左側區間，右側大于基準位置則遞回呼叫右側區間，直到所有項排列完成，
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] // 當左側小于等于右側則表示還有項沒有對比，需要繼續 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) { // 與遞回版不同，這里當左側小于基數位置時添加到堆疊中，以便繼續回圈 console.log('left < j:recursion: left=' + left + ' right=' + right + ' i=' + i + ' j=' + j + 'arr[]=' + arr) stack.push(left) stack.push(j) } if (i < right) { // 當右側大于等于基數位置時添加到堆疊中，以便繼續回圈 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548289.html
標籤：其他