注：代码及讲解参考：https://leetcode.cn/problems/sort-an-array/solution/duo-chong-pai-xu-yi-wang-da-jin-kuai-pai-wgz4/

一、基于最大堆的排序方法

1. 什么是最小堆，最大堆，以及堆的插入和删除操作，可以参考该博文，讲的非常好

class Solution:def sortArray(self, nums):def max_heap(nums,temp_root,end):child=temp_root*2+1while child<=end:if child<end and nums[child+1]>nums[child]:child+=1 if nums[temp_root]<nums[child]:nums[temp_root],nums[child]=nums[child],nums[temp_root]temp_root=childchild=temp_root*2+1else:break  n=len(nums)for i in range(n//2-1,-1,-1):max_heap(nums,i,n-1)nums[0],nums[n-1]=nums[n-1],nums[0]for i in range(n-1,1,-1):max_heap(nums,0,i-1)nums[0],nums[i-1]=nums[i-1],nums[0]return nums

二、基于快速排序方法

import random
class Solution(object):def sortArray(self,nums):def partition(nums,low,high):pivot=nums[low]left=lowright=high while left<right:while left<right and nums[right]>=pivot:right-=1 nums[left],nums[right]=nums[right],nums[left]while left<right and nums[left]<=pivot:left+=1nums[left],nums[right]=nums[right],nums[left]return leftdef quick_sort(nums,low,high):if low>=high:return# 决定pivot,mid pivot_num=random.randint(low,high)nums[pivot_num],nums[low]=nums[low],nums[pivot_num]mid=partition(nums,low,high)quick_sort(nums,low,mid-1)quick_sort(nums,mid+1,high)quick_sort(nums,0,len(nums)-1)    return nums 

三、归并排序（效率最高，内存占用最少）

class Solution:# 归并排序def sortArray(self, nums):def mergeArray(arr,low,high):mid=low+(high-low)//2if not (low==mid):mergeArray(arr,low,mid)mergeArray(arr,mid+1,high)left=lowright=mid+1 temp=[]while left<=mid and right<=high:if arr[left]<=arr[right]:temp.append(arr[left])left+=1else:temp.append(arr[right])right+=1while left<=mid:temp.append(arr[left])left+=1while  right<=high:temp.append(arr[right])right+=1arr[low:high+1]=temp mergeArray(nums,0,len(nums)-1)return nums