JavaScript Quicksort递归
我们需要编写一个包含数字数组的JavaScript函数。函数应应用快速排序算法对数组进行升序或降序排序。
快速排序算法
Quicksort遵循以下步骤-
步骤1-将任何元素作为枢轴（最好是第一个或最后一个，但任何元素都可以作为枢轴）
第2步-根据数据透视表对数组进行分区
步骤3-在左侧分区上递归快速排序
第4步-递归在正确的分区上快速排序
QuickSort的平均和最佳情况下的时间复杂度为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 ]
热门推荐
10 小红书平安祝福语简短
11 生日祝福语大全女孩简短
12 收生日红包祝福语 简短
13 领证幽默祝福语简短
14 法考面试祝福语简短
15 老哥出门祝福语简短语
16 送灯祝福语简短独特
17 幼儿狗年祝福语大全简短
18 好听的元旦简短祝福语