資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究JavaScript QuickSort 遞迴
我們需要編寫一個 JavaScript 函式來接收一個包含數字的陣列。該函式應運用快速排序的演算法對陣列進行升序或降序排序。
快速排序演算法
快速排序遵循以下步驟 −
步驟 1 − 選取任意元素作為基準點（最好是第一個或最後一個，但任何元素都可以作為基準點）
步驟 2 − 根據基準點對陣列進行分割
步驟 3 − 對左分割槽遞迴應用快速排序
步驟 4 − 對右分割槽遞迴應用快速排序
快速排序的平均和最佳時間複雜度為 O(nlogn)，而在最壞情況下，它可能會慢至 O(n^2)。
示例
程式碼示例如下 −
const arr = [5,3,7,6,2,9];
const swap = (arr, leftIndex, rightIndex) => {
let temp = arr[leftIndex];
arr[leftIndex] = arr[rightIndex];
arr[rightIndex] = temp;
};
const partition = (arr, left, right) => {
let pivot = arr[Math.floor((right + left) / 2)];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
};
while (arr[j] > pivot) {
j--;
};
if (i <= j) {
swap(arr, i, j); //sawpping two elements
i++;
j--;
};
};
return i;
}
const quickSort = (arr, left = 0, right = arr.length - 1) => {
let index;
if (arr.length > 1) {
index = partition(arr, left, right);
if (left < index - 1) {
quickSort(arr, left, index - 1);
};
if (index < right) {
quickSort(arr, index, right);
};
}
return arr;
}
let sortedArray = quickSort(arr);
console.log(sortedArray);輸出
而控制檯中的輸出如下 −
[ 2, 3, 5, 6, 7, 9 ]
更新於：2020 年 11 月 24 日
800 次瀏覽
廣告