資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告