leetcode88.合并两个有序数组（简单题！）

思路：合并两个数组，再进行排序（利用快速排序）

class Solution(object):def quicksort(self, num, i, j):if i>=j: # 跳出循环的条件要出来return left = iright = jtemp = num[i]while left < right:while left < right and temp <= num[right]:right -= 1num[left] = num[right]while left < right and temp >= num[left]:left += 1num[right] = num[left]num[left] = tempself.quicksort(num,i,left-1)self.quicksort(num,left+1,j)def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""nums1[m:] = nums2# 法一 利用用快速排序self.quicksort(nums1,0,len(nums1)-1)# return nums1# 法二 直接调用函数sort（）# nums1.sort()

时间复杂度：O((m+n)log(m+n))

空间复杂度：最坏情况下O(m+n)    # 每层树每个节点都开辟空间来算的话是这样  ？？ ？？但是这里一般按照O（log（m+n））因为递归树有log（m+n）层。

快速排序的空间复杂度分析

快速排序的空间复杂度由以下两部分组成：

1. 递归栈空间：这部分空间用来保存每次递归调用时的函数参数、局部变量和返回地址等信息。

2. 临时空间：这部分通常是用于存储在排序过程中临时需要的变量，但在经典的快速排序实现中，这部分空间是常数级的。其实不用考虑这部分了。