排序算法

快速排序

# 快排精简版
def quickSort(arr, low, high):
    if low >= high:
        return
    l, r = low, high
    mid = random.randint(l, r)
    pivot = arr[mid]  # 保存基数 ****
    arr[l], arr[mid] = arr[mid], arr[l]  #  交换随机数到头部
    while l < r:  #  l和r 相遇时退出
        while l < r and pivot <= arr[r]:  #  寻找第一个小于基数的坐标
            r -= 1
        arr[l] = arr[r]
        while l < r and pivot > arr[l]:  #  寻找第一个大于基数的坐标
            l += 1
        arr[r] = arr[l]
    arr[l] = pivot
    quickSort(arr, low, l-1)
    quickSort(arr, l+1, high)
def partion(nums, left, right):
    # 随机选择mid节点
    mid = random.randint(left, right)
    pivot = nums[mid]
    # 交换随机数到头部
    nums[left], nums[mid] = nums[mid], nums[left]
    # left和right 相遇时退出
    while left < right: ############ 先从右边找
        # 寻找第一个小于基数的坐标
        while left < right and pivot <= nums[right]:
            right -= 1
        nums[left] = nums[right]
        # 寻找第一个大于基数的坐标
        while left < right and pivot > nums[left]:
            left += 1
        nums[right] = nums[left]
    nums[left] = pivot
    return left
def quickSort(nums, start, end):
    if start >= end:
        return
    mid = partion(nums, start, end)
    quickSort(nums, start, mid-1)
    quickSort(nums, mid+1, end)

快排应用：求最小的k个数

最小的k个数，利用快排提前终止，时间复杂度为On

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def quickSort(arr, low, high):
            if low >= high:
                return
            l, r = low, high
            mid = random.randint(l, r)
            pivot = arr[mid]  # 保存基数 ****
            arr[l], arr[mid] = arr[mid], arr[l]  #  交换随机数到头部
            while l < r:  #  l和r 相遇时退出
                while l < r and pivot <= arr[r]:  #  寻找第一个小于基数的坐标
                    r -= 1
                arr[l] = arr[r]
                while l < r and pivot > arr[l]:  #  寻找第一个大于基数的坐标
                    l += 1
                arr[r] = arr[l]
            arr[l] = pivot
            if k<l:quickSort(arr, low, l-1)
            if k>l:quickSort(arr, l+1, high)
            return
        quickSort(arr,0,len(arr)-1)
        return arr[:k]

归并排序

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    l = mergeSort(arr[:mid])
    r = mergeSort(arr[mid:])
    return merge(l, r)
def merge(left, right):
    tmp = []
    l, r = 0, 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            tmp.append(left[l])
            l += 1
        else:
            tmp.append(right[r])
            r += 1
    if l < len(left):
        tmp += left[l:]
    if r < len(right):
        tmp += right[r:]
    return tmp

归并的应用: 求逆序对

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        count=0
        def merge(left: list, right: list):
            l, r = 0, 0
            tmp = []
            nonlocal count
            while l < len(left) and r < len(right):
                if left[l] <= right[r]:
                    tmp.append(left[l])
                    l += 1
                else:                 
                    count+=(len(left)-l) # 只此一行
                    tmp.append(right[r])
                    r += 1
            tmp += left[l:]
            tmp += right[r:]
            return tmp

        def mergeSort(nums: list):
            if len(nums) <= 1:
                return nums
            mid = len(nums)//2
            leftL = mergeSort(nums[:mid])
            rightL = mergeSort(nums[mid:])
            return merge(leftL, rightL)


        res=mergeSort(nums)
        return count