Try   HackMD

快速排序(Quick Sort)

介紹

快速排序是一種分治算法(Divide and Conquer),它將原問題劃分為兩個子問題,一個是比基準值小的數,另一個是比基準值大的數。然後遞歸地解決這兩個子問題,最終得到排序後的結果。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
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]

複雜度

時間複雜度

平均為:

O(nlogn)

最壞情況每次都選到最小值當作基準值:

O(n2)

空間複雜度

O(logn)

實戰

題目說明

912. Sort an Array

給你一個整數陣列nums,請將陣列以升序排列並返回。您必須在O(nlog(n))時間複雜度內解決此問題,並使用較小的空間複雜度。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
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 }