【快速排序】912--排序数组

错误做法

import random

class Solution:
    def sortArray(self, nums):
        # corner case
        if len(nums) == 0:
            return nums

        # 快速排序
        left = 0
        right = len(nums) - 1
        self.dnc(nums, left, right)

        return nums

    def dnc(self, nums, left, right):
        # 结束条件
        if left >= right:
            return

        # 递归拆解
        mid = self.get_mid(nums, left, right)
        self.dnc(nums, 0, mid - 1)
        self.dnc(nums, mid + 1, right)

    def get_mid(self, nums, left, right):
        r = random.randint(left, right)
        pivot = nums[r]
        nums[r], nums[left] = nums[left], nums[r]
        while left < right:
            while nums[right] >= pivot and left < right:
                right -= 1
            nums[left] = nums[right]
            while nums[left] <= pivot and left < right:
                left += 1
            nums[right] = nums[left]
            nums[left] = pivot

        return left

错误解析：
因为循环的每一轮，左右边界都会被当成给移动指针，于是左右边界不固定

正确写法

从这里看懂：https://www.bilibili.com/video/BV1mE411M7SH?from=search&seid=3750218521433931722
再边换成分治算法模板

import random


class Solution:
    def MySort(self , arr ):
        # corner case
        if len(arr) == 0:
            return arr
        
        # 边界设定
        left = 0
        right = len(arr) - 1
        # 放入dnc函数递归，快排是原地排序
        self.dnc(arr, left, right)
        # 返回
        return arr
    
    def dnc(self, arr, left, right):
        # 终止条件
        if left >= right:
            return
        
        # 递归拆解
        index = random.randint(left, right)
        pivot = arr[index]
        arr[index], arr[left] = arr[left], arr[index]
        i, j = left, right
        while i < j:
            while arr[j] > pivot and i < j:
                j -= 1
            arr[i] = arr[j]
            while arr[i] <= pivot and i < j:
                i += 1
            arr[j] = arr[i]
        arr[i] = pivot
        self.dnc(arr, left, i-1)
        self.dnc(arr, i+1, right)