排序数组

1、题目

图1

2、题解

快速排序

• 挑选基准值
• 分割数组
• 递归排序子数组

class Solution:
    def quickSort(self,nums,low,high):
        pivot = nums[low]
        left,right=low,high
        while left<right:

            while left<right and nums[right]>=pivot:
                right -= 1            
            nums[left] = nums[right]

            while left<right and nums[left]<=pivot:
                left += 1
            nums[right] = nums[left]
        
        nums[left] = pivot

        return left
    
    def random_init(self,nums,low,high):
        pivot_idx = random.randint(low,high)
        nums[low],nums[pivot_idx] = nums[pivot_idx],nums[low]

        return self.quickSort(nums,low,high)

    def quick_sort(self,nums,low,high):
        if low >= high:
            return
        mid = self.random_init(nums,low,high)

        self.quick_sort(nums,low,mid-1)
        self.quick_sort(nums,mid+1,high)

    def sortArray(self, num1: List[int]) -> List[int]:

        self.quick_sort(num1,0,len(num1)-1)

        return num1

堆排序

class Solution:
    def heapify(self,nums,n,i):
        largest = i
        while largest*2 + 1 < n :
            l,r = 2*largest+1, 2*largest+2

            if n<= r or nums[r]<nums[l]:
                tmp = l
            else:
                tmp = r
            
            if nums[largest]< nums[tmp]:
                nums[largest],nums[tmp] = nums[tmp], nums[largest]
                largest = tmp
            else:
                break
    
    def build_heap(self,nums):
        for i in range(len(nums)-1,-1,-1):
            self.heapify(nums,len(nums),i)
    
    def heap_sort(self,nums):
        self.build_heap(nums)
        for i in range(len(nums)-1,-1,-1):
            nums[i],nums[0] = nums[0],nums[i]
            self.heapify(nums,i,0)    
    def sortArray(self, nums: List[int]) -> List[int]:
        self.heap_sort(nums)
        return nums