快速排序是一種分治算法(Divide and Conquer),它將原問題劃分為兩個子問題,一個是比基準值小的數,另一個是比基準值大的數。然後遞歸地解決這兩個子問題,最終得到排序後的結果。
Learn More →
(圖片來自data_structures_algorithms)
運用了分治法的概念,將大的數值移到左邊,小的數值移到右邊,再遞迴運算左右兩側的數值,直到最終整個數列有序
Error: Expected an atom of EOF but received ordinary at position 13: `QUICK-SORT(p,↱ r): if p`
基準值(pivot)並進行數值交換,使得數列的左半部分都小於等於基準值,右半部分都大於等於基準值。最後返回基準值的位置。
Error: Expected an atom of EOF but received ordinary at position 12: `partition(p,↱ r): x = A`
let arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
function partition(p, r){
let x = arr[r];
let i = p - 1;
for (let index = p; index <= r - 1; index++) {
if(arr[index] <= x){
i = i + 1;
[arr[i], arr[index]] = [arr[index], arr[i]];
}
}
[arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
return i + 1;
}
function quickSort(p , r){
if (p < r){
let q = partition(p, r);
quickSort(p, q - 1);
quickSort(q + 1, r);
}
}
quickSort(0, arr.length - 1)
console.log(arr) // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
平均為:
最壞情況每次都選到最小值當作基準值:
給你一個整數陣列nums
,請將陣列以升序排列並返回。您必須在O(nlog(n))
時間複雜度內解決此問題,並使用較小的空間複雜度。
Learn More →
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
return quickSort(nums)
};
function partition(nums, p, r){
let x = nums[r];
let i = p - 1;
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
for (let index = p; index <= r - 1; index++) {
if(nums[index] <= x){
i = i + 1;
swap(nums, index, i)
}
}
swap(nums, r, i + 1)
return i + 1;
}
function quickSort(nums, p = 0 , r = nums.length - 1){
if (p < r){
let q = partition(nums, p, r);
quickSort(nums, p, q - 1);
quickSort(nums, q + 1, r);
}
return nums
}
最小生成樹(Minimum Spanning Tree,MST)是指在一個帶權無向圖中,找到一棵包含所有節點,權值最小的樹。其中,權值是指樹中所有邊權重的總和。
May 9, 2025運算式(Expression)有三種表示方式:中序式(Infix)、前序式(Prefix)、後序式(Postfix)
Dec 27, 2024Pinia簡介
Dec 26, 2024氣泡排序是反覆進行將相鄰數字做比較後重新排序,因排序時一個一個浮出序列頂部,很像水中泡泡浮起來的樣子,亦稱泡泡排序,最壞情況下,數是由大排到小,每次比較後將數值對調,因此,時間複雜度為O(n^2)。
Dec 24, 2024or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up