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

題目在這裡:

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

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

測試範例:

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 * 104
• -5 * 104 <= nums[i] <= 5 * 104

演算法:

題目已經明言規定不可以呼叫程式語言或者平台內建的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 。

程式碼:

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