更新於 2024/09/20閱讀時間約 4 分鐘

經典演算法 陣列排序 Sort an Array Leetcode #912

raw-image

題目敘述  Sort an Array

這題就是經典的考排序驗算法,不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。

題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。


測試範例

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

約束條件

Constraints:

  • 1 <= nums.length <= 5 * 10^4

陣列長度介於1~五萬之間。

  • -5 * 10^4 <= nums[i] <= 5 * 10^4

陣列元素都介於 負五萬 ~ 正五萬 之間。


演算法 採用較佳的O( n logn ) 演算法


題目已經明言規定不可以呼叫程式語言或者平台內建的sort function,就是要求我們真正實作一個upper bound為O( n log n)的排序演算法。

考慮到退化的關係,QuickSort會在最差情況會退到O( n^2 )。


註: 退化的意思就是,Worst case發生在當所有element 都已經排好,或者逆序排好,或者陣列元素都相同的時候。


所以本題我們選擇Merge Sort來實作,Merge sort 即使在最差情況 worst case依然能保障O( n log n)的complexity upper bound 。


程式碼 較佳的O( n logn ) MergeSort演算法

class Solution:
 def sortArray(self, nums: List[int]) -> List[int]:
  
  # Use divide and conquer strategy with mergesort
  def mergeSort(left, right):

   if left >= right:
    # only one element, no need to sort
    # invalid interval, no need to sort
    return
   
   # Divide :
   mid = left + (right - left) // 2
   mergeSort( left , mid )
   mergeSort( mid+1, right)

   # Conquer, also known as merge
   a, b = left, mid+1
   merging = []
   
   # Two way merge between left half and right half
   while a <= mid and b <= right:

    if nums[a] < nums[b]:
     merging.append( nums[a] )
     a += 1
    else:
     merging.append( nums[b] )
     b += 1

   # Only left half remains
   while a <= mid:
    merging.append( nums[a] )
    a += 1

   # Only right half remains
   while b <= right:
    merging.append( nums[b] )
    b += 1

   # Write back to originally specific interval
   nums[left : right+1] = merging

   return

複雜度分析

時間複雜度:

O( n log n),至多 log n 層,每層merge又耗費O(n)去合併左半部和右半部子陣列。


空間複雜度:

O( n ) 合併時耗費O(n)的輔助空間去儲存merge完的結果


Reference:

[1] Python O( n log n) by merge sort — Sort an Array — LeetCode

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.