题解 | #排序#

冒泡排序：

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

选择排序：

class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        #选择排序
        for i in range(len(arr)):
            min_index=i
            for j in range(i+1,len(arr)):
                if arr[j]<arr[min_index]:
                    min_index=j
            arr[i],arr[min_index]=arr[min_index],arr[i]
        return arr

插入排序：

class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        #插入排序
        for i in range(1,len(arr)):
            pre_index=i-1
            cur=arr[i]
            while pre_index>=0 and arr[pre_index]>cur:
                arr[pre_index + 1] = arr[pre_index]
                pre_index-=1
            arr[pre_index + 1] = cur;
        return arr

希尔排序：

class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        #希尔排序
        import math
        gap=1
        while(gap < len(arr)/3):
            gap = gap*3+1
        while gap > 0:
            for i in range(gap,len(arr)):
                temp = arr[i]
                j = i-gap
                while j >=0 and arr[j] > temp:
                    arr[j+gap]=arr[j]
                    j-=gap
                arr[j+gap] = temp
            gap = math.floor(gap/3)
        return arr

归并排序

class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        #归并排序
        import math
        if len(arr)<2:
            return arr
        mid=math.floor(len(arr)/2)
        left,right=arr[0:mid],arr[mid:]
        return merge(self.MySort(left),self.MySort(right))
def merge(left,right):
    result=[]
    while left and right:
        if left[0]<right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result