Python快排和归并排序

一、快速排序（分治法）

基本思想：每次将基准匹配对正确的位置；保证对应子list中，左侧都小于基准，右侧都大于基准。
时间复杂度O(nlogn)
空间复杂度O(1)
最坏时间复杂度O（n*2）

快排代码

class Solution:
    def quickS(self,nums):
        # 获得数组长度
        n=len(nums)
        
        # 快拍  [0,n-1]
        return self.quickSort(nums,0,n-1)
    
    def quickSort(self,nums,l,r):
        
        # 如果左>=右，则停止递归
        if l>=r:
            return 0
        
        # 获得首位标志位
        left = l
        right = r
        # 获得基准mid
        mid = nums[left]
        
        # 左至右遍历，目的是找到基准真正的位置
        while left<right:
            
            # 从右往左遍历，找到小于mid的索引right
            while left<right and nums[right]>=mid:
                right-=1
            
            # 将小于mid的索引值与li[left]替换，使左侧都小于mid,右侧都大于mid
            nums[left] = nums[right]
            
            # 从左往右遍历，找到大于mid的索引left
            while left<right and nums[left]<mid:
                left+=1
            
            # 将大于mid的索引值与li[right]替换，使右侧都大于mid，左侧都小于mid
            nums[right] = nums[left]
            
        # 把覆盖的值替换回来
        nums[left] = mid
        
        # 继续递归
        self.quickSort(nums,l,left-1)
        self.quickSort(nums,left+1,r)
        
        return nums

二、归并排序(分治法思路）

基本思想：每次都对半切割，然后排序合并。
时间复杂度O(nlogn)
空间复杂度O(n)

归并排序

class Solution:
    def mergeS(self,num):
        
        # 获得数组长度
        n = len(num)
        # 临时创建一个存储空间
        tmp = [0]*n
        
        # 从[0,n-1]遍历
        return self.mergeSort(num,tmp,0,n-1)
    
    def mergeSort(self,num,tmp,l,r):
        
        # 如果左边界大于等于右边界，取消
        if l>=r: 
            return 0
        
        # 获得中间值
        mid = l + (r-l)//2
        
        # 继续分治，左边[l,mid],右边[mid+1,r]
        self.mergeSort(num,tmp,l,mid)
        self.mergeSort(num,tmp,mid+1,r)
        
        # 分治结束，归并
        # 设置两个数组的头指针i,j = l, mid+1
        # 设置tmp的标志位pos=l
        i,j,pos = l,mid+1,l
        
        
        # 遍历直至两个数组达到顶 i<=mid 和 j<=r
        while i<=mid and j<=r:
            
            # 如果num[i]>num[j]，说明小的值在第二个数组，将其复制到tmp中,j+=1,
            if num[i]>num[j]:
                tmp[pos] = num[j]
                j+=1
            
            # 如果num[i]<num[j]，说明小的值在第一个数组,将其复制到tmp中，i+=1
            else:
                tmp[pos] = num[i]
                i+=1
            
            # tmp标志位++
            pos+=1
        
        # 把为处理完的有序数组添加在后方
        for k in range(i,mid+1):
            tmp[pos]= num[k]
            pos+=1
        
        for k in range(j,r+1):
            tmp[pos] = num[k]
            pos+=1
        
        # 把tmp中排序好的赋值回num中
        num[l:r+1] = tmp[l:r+1]
        
        return num