修改 QUICKSORT' 的代码，使最坏情况下的堆栈深度为 Θ（lg n）。保持算法的 O（nlgn） 预期运行时间。

QUICKSORT是一种基于分治策略的排序算法，它的基本思想是选择一个基准元素将数组分为两部分，一部分所有元素都小于基准，另一部分所有元素都大于基准，然后递归地对这两部分进行同样的操作。然而，原始的快速排序在最坏的情况下，例如输入已经完全有序或者逆序，每次划分只能减少一个元素，导致堆栈深度达到n，这并不是理想的O(lgn)。

为了优化这种情况，可以采用一种称为"随机化版本的快速排序"或者"三数取中法"（Median-of-Three Partitioning），它在选取基准值时不再固定选择第一个、最后一个或中间元素，而是从待分区的序列中随机选取三个元素，取其中的中位数作为基准。这种方法减少了最坏情况发生的概率，并且理论上平均每个元素需要比较log(n)次就能找到合适的分区点，因此在平均和期望情况下，堆栈深度能达到O(lgn)。

以下是简化后的随机化快速排序伪代码：

def randomized_quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]
    arr[pivot_index], arr[-1] = arr[-1], arr[pivot_index]  # 将最大元素放到最后，便于处理
    i, j = 0, len(arr) - 2

    while i < j:
        while i < j and arr[j] >= pivot:
            j -= 1
        if i < j:
            arr[i] = arr[j]
            i += 1
        
        while i < j and arr[i] < pivot:
            i += 1
        if i < j:
            arr[j] = arr[i]
            j -= 1
            
    arr[j+1] = pivot  # 最终把pivot放回正确位置
    randomized_quick_sort(arr[:j])  # 对左半部分递归排序
    randomized_quick_sort(arr[j+2:])  # 对右半部分递归排序

#