在 JavaScript 中实现分治逻辑以实现快速排序
javascriptweb developmentfront end technologyobject oriented programming更新于 2025/12/5 4:28:17
我们需要编写一个 JavaScript 函数，该函数接受一个数字数组并使用快速排序算法对其进行排序。
快速排序
该算法基本上是一种分治算法，我们在每次循环中选择一个枢轴，并将所有小于枢轴的元素放在其左侧，所有大于枢轴的元素放在其右侧(如果其升序排列，否则相反)
示例
让我们来编写该函数代码 −
const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// 查找"枢轴"数组中的元素，用于比较所有其他元素
// ，然后根据元素的值在元素之前或之后移动元素
// 旋转
const quickSort = (arr, left = 0, right = arr.length - 1) => {
let len = arr.length, index;
if(len > 1) {
index = partiton(arr, left, right)
if(left < index - 1) {
quickSort(arr, left, index - 1)
}
if(index < right) {
quickSort(arr, index, right)
}
}
return arr
}
const partion = (arr, left, right) => {
let middle = Math.floor((right + left) / 2),
pivot = arr[middle],
i = left, // 将指针起始于数组中的第一个元素
array
j = right // 将指针起始于数组中的最后一项
while(i <= j) {
// 将左指针向右移动，直到
// 左侧的值大于枢轴值
while(arr[i] < pivot) {
i++
}
// 将右指针向左移动，直到
// 右侧的值小于枢轴值
while(arr[j] > pivot) {
j--
}
// 如果左指针小于或等于
// 右指针，则交换值
if(i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]] // ES6 解构交换
i++
j--
}
}
return i
}
console.log(quickSort(arr));
输出
控制台中的输出 −
[ 2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434 ]
相关文章
有用资源
javascript 参考教程 - 该教程包含有关 javascript 的更多信息:https://www.cainiaomax.com/javascript/
