資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究用 JavaScript 實現分治演算法，以實現快速排序
我們需要編寫一個 JavaScript 函式，其中包含一個數字陣列，並使用快速排序演算法對其進行排序。
快速排序
此演算法本質上是一種分而治之演算法，其中我們在每次迴圈中選擇一個基準，並將所有小於基準的元素放在其左側，並將所有大於基準的元素放在其右側（如果是升序排序，否則相反）
示例
讓我們為這個函式編寫程式碼 −
const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// Find a "pivot" element in the array to compare all other
// elements against and then shift elements before or after
// pivot depending on their values
const quickSort = (arr, left = 0, right = arr.length - 1) => {
let len = arr.length, index;
if(len > 1) {
index = partition(arr, left, right)
if(left < index - 1) {
quickSort(arr, left, index - 1)
}
if(index < right) {
quickSort(arr, index, right)
}
}
return arr
}
const partition = (arr, left, right) => {
let middle = Math.floor((right + left) / 2),
pivot = arr[middle],
i = left, // Start pointer at the first item in the
array
j = right // Start pointer at the last item in the array
while(i <= j) {
// Move left pointer to the right until the value at the
// left is greater than the pivot value
while(arr[i] < pivot) {
i++
}
// Move right pointer to the left until the value at the
// right is less than the pivot value
while(arr[j] > pivot) {
j--
}
// If the left pointer is less than or equal to the
// right pointer, then swap values
if(i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]] // ES6 destructuring swap
i++
j--
}
}
return i
}
console.log(quickSort(arr));輸出
控制檯中的輸出 −
[ 2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434 ]
更新於： 15-Sep-2020
509 次觀看
廣告