快速排序演算法通過多次比較和交換來實作排序，其排序流程如下：
(1) 首先設定一個分界值，通過該分界值將陣列分成左右兩部分，
(2) 將大于或等于分界值的資料集中到陣列右邊，小于分界值的資料集中到陣列的左邊，此時，左邊部分中各元素都 小于分界值，而右邊部分中各元素都大于或等于分界值，
(3) 然后，左邊和右邊的資料可以獨立排序，對于左側的陣列資料，又可以取一個分界值，將該部分資料分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值，右側的陣列資料也可以做類似處理，
(4) 重復上述程序，可以看出，這是一個遞回定義，通過遞回將左側部分排好序后，再遞回排好右側部分的順序，當左、右兩個部分各資料排序完成后，整個陣列的排序也就完成了，
var arr = [9, 4, 3, 1, 6, 3, 8, 7]
/**
* 快速排序
* @param {array} - arr 需要排序的陣列
* @returns {array}
*/
function quickSort (arr) {
if (arr.length <= 1) return arr
var arr1 = [], arr2 = []
for (var i = 1; i < arr.length; i++) {
if (arr[i] < arr[0]) {
arr1.push(arr[i])
} else {
arr2.push(arr[i])
}
}
arr1 = quickSort(arr1)
arr2 = quickSort(arr2)
arr1.push(arr[0])
return arr1.concat(arr2)
}
console.log(quickSort(arr)) // [1, 3, 3, 4, 6, 7, 8, 9]
微信交流群
前端面試：劍指 Offer (3群)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/498894.html
標籤：JavaScript
上一篇：純CSS 格子背景
下一篇：Vue實作記住賬號密碼功能