给定一个长度为n的数组，请你编写一个函数，返回该数组按升序排序后的结果。
数据范围:0<n<1x10^3，数组中每个元素都满足0<val<10^9
要求:时间复杂度O(n2)，空间复杂度O(n) 进阶:时间复杂度O(nlogn)，空间复杂度O(n)
注:本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。
示例1
输入：
[5,2,3,1,4]
返回值：
[1,2,3,4,5]
示例2
输入：
[5,1,6,2,5]
返回值：
[1,2,5,5,6]
方法一： 快速排序
class Solution:
def MySort(self , arr ):
# write code here
self.quick_sort(0, len(arr)-1, arr)
return arr
def quick_sort(self, start, end, arr):
if start >= end:
return
left, right = start, end
pivot = arr[(start + end)//2]
while left <= right:
while left <= right and arr[left] < pivot:
left += 1
while left <= right and arr[right] > pivot:
right -= 1
if left <= right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
self.quick_sort(start, right, arr)
self.quick_sort(left, end, arr)
方法二：归并排序
class Solution:
def MySort(self , arr ):
# write code here
temp = [0 for _ in range(len(arr))]
self.merge_sort(0, len(arr) - 1, arr, temp)
return arr
def merge_sort(self, start, end, arr, temp):
if start >= end:
return
mid = (start + end) // 2
self.merge_sort(start, mid, arr, temp)
self.merge_sort(mid + 1, end, arr, temp)
self.merge(start, mid, end, arr, temp)
def merge(self, start, mid, end, arr, temp):
left, right = start, mid + 1
index = start
while left <= mid and right <= end:
if arr[left] < arr[right]:
temp[index] = arr[left]
left += 1
else:
temp[index] = arr[right]
right += 1
index += 1
while left <= mid:
temp[index] = arr[left]
left += 1
index += 1
while right <= end:
temp[index] = arr[right]
right += 1
index += 1
for index in range(start, end+1):
arr[index] = temp[index]
xx