题解 | 排序 快速排序

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组

 题解 ： 
 https://leetcode.cn/discuss/post/3690844/0x11-pai-xu-by-zengjx-mqc4/
#
class Solution:
    def partition(self,arr,left,right):
        i,j=left,right 
        while i<j:
            # 从右到左找第一个小于哨兵的元素
            while i<j and arr[left]<=arr[j]:
                j-=1
            # 从左到右找第一个大于哨兵devil元素
            while i<j and arr[i]<=arr[left]:
                i+=1
            #交换
            arr[i],arr[j] =arr[j],arr[i]
        # 将哨兵元素放在应该的分割位置
        arr[left],arr[i]=arr[i],arr[left]
        return i # 分割位置
    
    def quck_sort(self,arr,left ,right):
        if left >=right:
            return 
        poivt=self.partition(arr,left,right)
        self.quck_sort(arr,left,poivt-1)
        self.quck_sort(arr,poivt+1,right)

    def MySort(self , arr: List[int]) -> List[int]:
        self.quck_sort(arr,0,len(arr)-1)
        return  arr



    def MySort1(self , arr: List[int]) -> List[int]:
        # write code here
        n=len(arr)
        for i in range(n):
            for j in range(n-1):
                if arr[j]>arr[j +1]:
                    temp =arr[j]
                    arr[j]=arr[j+1]
                    arr[j+1]=temp 
        return arr