2022-12-20

针对快速排序的 尾递归 空间优化，，以及左右当参考值
我个人喜欢右侧当参考值
普通快速排序在某些输入下的空间效率变差。 仍然以完全倒序的输入数组为例，由于每轮哨兵划分后右子数组长度为 0 ，那么将形成一个高度为 的递归树，此时使用的栈帧空间大小劣化至 。

为了避免栈帧空间的累积，我们可以在每轮哨兵排序完成后，判断两个子数组的长度大小，仅递归排序较短的子数组。
由于较短的子数组长度不会超过 一半，，空间复用，要思考

，因此这样做能保证递归深度不超过 log n，即最差空间复杂度被优化至 log n。

""" 哨兵划分 """
def partition(self, nums, left, right):
    # 以 nums[left] 作为基准数
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1  # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i  # 返回基准数的索引


class Solution:
    """ 哨兵划分 """
    def partition(self, nums, left, right):
        # 以 nums[left] 作为基准数
        i, j = left, right
        while i < j:
            while i < j and nums[i] <= nums[right]:
                i += 1  # 从左向右找首个大于基准数的元素
            while i < j and nums[j] >= nums[right]:
                j-= 1  # 从右向左找首个小于基准数的元素 

            # 元素交换
            nums[i], nums[j] = nums[j], nums[i]
        # 将基准数交换至两子数组的分界线
        #print(i==j)
        nums[i], nums[right] = nums[right], nums[i]
        return i  # 返回基准数的索引
    
    def quick_sort(self, nums, left, right):
        # 子数组长度为 1 时终止
        global aa ,bb
        aa+=1 
        if aa>bb:
            bb=aa
        print(aa)
        while left < right:
            # 哨兵划分操作
            pivot = self.partition(nums, left, right)
            # 对两个子数组中较短的那个执行快排
            if pivot - left < right - pivot:
                self.quick_sort(nums, left, pivot - 1)  # 递归排序左子数组
                left = pivot + 1     # 剩余待排序区间为 [pivot + 1, right]
            else:
                self.quick_sort(nums, pivot + 1, right)  # 递归排序右子数组
                right = pivot - 1    # 剩余待排序区间为 [left, pivot - 1]
        aa-=1 
        print(aa)

# def kk(la2,a,b):
#     if a>=b:
#         return
#     p=partition(la2,a,b)
#     kk(la2,a,p-1)
#     kk(la2,p+1,b)

# kk(la,0,len(la)-1)
# print(la)
import random
la=[random.randint(33,77) for i in range(64,0,-1)]

aa=0
bb=0
""" 快速排序（尾递归优化） """
cc=Solution()
cc.quick_sort(la,0,len(la)-1) 
print(bb,len(la))