数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 中的归并排序与快速排序
在本文中，我们将讨论 JavaScript 中归并排序和快速排序之间的差异，并提供相应的示例。
归并排序和快速排序用于对元素进行排序，但方法不同。归并排序和快速排序都基于分治策略。
归并排序
它是一种稳定的排序算法。在归并排序中，它遵循一种递归方法，反复将数组分成两半，直到不再可能进行分割，即数组要么为空，要么只有一个元素。然后通过比较两个小数组的元素对它们进行排序，并通过构建一个更大的数组来合并它们。归并排序的最坏情况时间复杂度为 – O(nlogn)。
快速排序
在快速排序中，它选择一个元素作为枢纽。枢纽元素可以是第一个元素、最后一个元素、中间元素或任何随机元素。选择枢纽元素后，它会围绕所选枢纽对数组进行分区。快速排序的最坏情况时间复杂度为 – O(n^2)。
在辅助空间和局部性方面，快速排序优于归并排序。归并排序使用额外的空间进行排序。快速排序在额外空间方面优于归并排序，因为它只需要很少的额外空间。当我们有更大的数据结构时，归并排序优于快速排序。
示例 1
这是一个实现归并排序的示例程序。
<!DOCTYPE html>
<html>
<head>
<title>Merge sort in JavaScript</title>
</head>
<body style="text-align : center">
<h3>MergeSort in JavaScript</h3>
<p id='output'></p>
<script>
function merge(arr, l, m, r) {
var size1 = m - l + 1;
var size2 = r - m;
// Create two temporary arrays i.e. LeftSub and RightSub Arrays.
var LeftSub = new Array(size1);
var RightSub = new Array(size2);
// Copy data from arr to LeftSub and RightSub Arrays respectively.
for (var i = 0; i < size1; i++)
LeftSub[i] = arr[l + i];
for (var j = 0; j < size2; j++)
RightSub[j] = arr[m + 1 + j];
var i = 0,
j = 0,
k = l;
// Merge the temporary arrays back into arr[l..r]
while (i < size1 && j < size2) {
if (LeftSub[i] <= RightSub[j]) {
arr[k] = LeftSub[i];
i++;
} else {
arr[k] = RightSub[j];
j++;
}
k++;
}
// Copy the remaining elements of LeftSub into arr
while (i < size1) {
arr[k] = LeftSub[i];
i++;
k++;
}
// Copy the remaining elements of RightSub into arr
while (j < size2) {
arr[k] = RightSub[j];
j++;
k++;
}
}
function mergeSort(arr, left, right) {
if (left >= right) {
return;
}
var mid = left + parseInt((right - left) / 2);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
function displayArray(A) {
A.forEach(ele => {
document.getElementById('output').innerHTML += ele + " ";
});
document.getElementById('output').innerHTML += '<br/>';
}
var arr = [10,7,27,5,2,9];
var size = arr.length;
document.getElementById('output').innerHTML += 'Before sorting : ';
displayArray(arr);
mergeSort(arr, 0, size - 1);
document.getElementById('output').innerHTML += '<br/>' + 'After sorting : ';
displayArray(arr);
</script>
</body>
</html>
执行上述代码后，将生成以下输出。
示例 2
这是一个实现快速排序的示例程序。
<!DOCTYPE html>
<html>
<head>
<title>Quick sort in JavaScript</title>
</head>
<body style="text-align : center">
<h3>quickSort in JavaScript</h3>
<p id='output'></p>
<script>
/* Swap method uses temp variable to swap the elements */
function swap(arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/* The method partition takes last element in the array as a pivot element, places elements which are lesser than pivot to the left of pivot in the array and places elements which are greater than pivot to the right of pivot in the array */
function partition(arr, low, high) {
let pivot = arr[high];
let i = (low - 1);
for (let j = low; j <= high - 1; j++) {
// If element is less than pivot
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
function quickSort(arr, low, high) {
if (low < high) {
let pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
function displayArray(A) {
A.forEach(ele => {
document.getElementById('output').innerHTML += ele + " ";
});
document.getElementById('output').innerHTML += '<br/>';
}
var arr = [25,9,1,16,4,49,36];
var size = arr.length;
document.getElementById('output').innerHTML += 'Before sorting : ';
displayArray(arr);
quickSort(arr, 0, size - 1);
document.getElementById('output').innerHTML += '<br/>' + 'After sorting : ';
displayArray(arr);
</script>
</body>
</html>
执行上述代码后，将生成以下输出。
更新于: 2022-12-09
566 次浏览
广告