資料結構
網路
關係型資料庫管理系統
作業系統
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+ 次檢視
