forked from itcharge/AlgoNote
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArray-MergeSort.py
More file actions
42 lines (35 loc) · 1.71 KB
/
Array-MergeSort.py
File metadata and controls
42 lines (35 loc) · 1.71 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
# 合并过程
def merge(self, left_nums: [int], right_nums: [int]):
nums = []
left_i, right_i = 0, 0
while left_i < len(left_nums) and right_i < len(right_nums):
# 将两个有序子数组中较小元素依次插入到结果数组中
if left_nums[left_i] < right_nums[right_i]:
nums.append(left_nums[left_i])
left_i += 1
else:
nums.append(right_nums[right_i])
right_i += 1
# 如果左子数组有剩余元素，则将其插入到结果数组中
while left_i < len(left_nums):
nums.append(left_nums[left_i])
left_i += 1
# 如果右子数组有剩余元素，则将其插入到结果数组中
while right_i < len(right_nums):
nums.append(right_nums[right_i])
right_i += 1
# 返回合并后的结果数组
return nums
# 分解过程
def mergeSort(self, nums: [int]) -> [int]:
# 数组元素个数小于等于 1 时，直接返回原数组
if len(nums) <= 1:
return nums
mid = len(nums) // 2 # 将数组从中间位置分为左右两个数组
left_nums = self.mergeSort(nums[0: mid]) # 递归将左子数组进行分解和排序
right_nums = self.mergeSort(nums[mid:]) # 递归将右子数组进行分解和排序
return self.merge(left_nums, right_nums) # 把当前数组组中有序子数组逐层向上，进行两两合并
def sortArray(self, nums: [int]) -> [int]:
return self.mergeSort(nums)
print(Solution().sortArray([0, 5, 7, 3, 1, 6, 8, 4]))