数据结构
网络
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 次浏览
广告