Javascript 中的归并排序与快速排序
javascriptweb developmentfront end technology
在本文中，我们将通过适当的示例讨论 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;
// 创建两个临时数组，即 LeftSub 和 RightSub 数组。
var LeftSub = new Array(size1);
var RightSub = new Array(size2);
// 将数据从 arr 分别复制到 LeftSub 和 RightSub 数组。
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;
// 将临时数组合并回 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++;
}
// 将 LeftSub 剩余元素复制到 arr 中
while (i < size1) {
arr[k] = LeftSub[i];
i++;
k++;
}
// 将 RightSub 剩余元素复制到 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 方法使用临时变量来交换元素 */
function swap(arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/* 方法分区将数组中的最后一个元素作为枢轴元素，将小于枢轴的元素放在数组中枢轴的左侧，将大于枢轴的元素放在数组中枢轴的右侧 */
function partition(arr, low, high) {
let pivot = arr[high];
let i = (low - 1);
for (let j = low; j <= high - 1; j++) {
// 如果元素小于枢轴
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>
执行上述代码后，将生成以下输出。
