数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何在 JavaScript 中实现快速排序？
在本文中，我们将讨论如何使用合适的示例在 JavaScript 中实现快速排序。
快速排序
快速排序是一种分治算法，类似于归并排序。在快速排序中，我们选择一个基准元素，并围绕基准元素划分数组。选择基准元素的方法有很多。
始终选择第一个元素作为基准元素。
始终选择最后一个元素作为基准元素。（在下面的程序中实现）
随机选择一个元素作为基准元素
选择中间元素作为基准元素。
快速排序中的主要过程是分区。分区的目的是，给定一个数组，并将数组中的一个元素 x 视为基准元素。将基准元素保持在已排序数组中的正确位置。然后将所有小于基准元素的元素放在左侧，大于基准元素的元素放在右侧。
输入和输出场景
考虑一个数组，其中包含一些以随机顺序排列且未排序的元素，我们可以通过执行归并排序来对这些元素进行排序。让我们检查下面的场景。
Input = [0, 10, 4, 1, 3]; Output = 0, 1, 3, 4, 10
简单的分区和快速排序函数
选择一个元素 x 作为基准。小于基准元素的元素将位于基准元素的左侧，大于基准元素的元素将位于基准元素的右侧。
快速排序是如何工作的？
要了解快速排序是如何工作的，让我们假设一个数组 arr=[7, 4, 10, 6, 3, 9]
索引为 0 1 2 3 4 5
Low = 0，High = 5，基准元素 = 9
最初，较小元素的索引 i = -1
通过将第一个元素与基准元素进行比较，7 小于 9。因此，7 被放置在索引 0 处，i 移动到 i=0。
现在，让我们将 4 与基准元素进行比较，4 小于 9，因此 i 将位于 i=1 处，4 将被放置在那里。
将 10 与基准进行比较，10 大于 9。i 不会递增（i = 1）。
让我们转到下一个元素 6，由于 6 小于基准，它将位于 i=2 处。9 将被移动到 i = 3。
将 3 与基准进行比较，3 小于 10。因此 i 将递增并变为 i=3，10 和 3 将被交换。
现在将 10 与基准进行比较。由于 10 大于基准元素，它将被放置在 i=4 处，10 将位于 i=5 处。
分区
现在，让我们围绕基准元素执行分区。
基准 = 9。
在 9 处执行分区，小于 9 的元素应在左侧，大于 9 的元素应在右侧。
然后将最后一个元素视为基准，并继续执行分区，如下面的图所示。
现在，让我们在下面的程序中实现上述快速排序过程。
示例
在下面的示例中，我们将最后一个元素视为基准 -
<!DOCTYPE html>
<html>
<head>
<title>Implementation of Quick Sort</title>
</head>
<body>
<script>
function Quicksort(array){
if (array.length < 2){
return array;
}
let pivot_element = array[array.length - 1]
let left_sub_array = [];
let right_sub_array = [];
for (let i = 0; i < array.length - 1; i++){
if (array[i] < pivot_element) {
left_sub_array.push(array[i])
} else {
right_sub_array.push(array[i])
}
}
return [...Quicksort(left_sub_array), pivot_element, ...Quicksort(right_sub_array)];
}
const array = [0, 10, 4, 1, 3];
document.write(Quicksort(array));
</script>
</body>
</html>
3K+ 次查看
