优化的快速排序可以写出来吗

优化的快速排序可以通过以下几种方式实现：

1. 三数取中法
在选取基准元素时，不使用第一个或最后一个元素，而是使用数组中间位置和两端位置的元素中值作为基准元素。这样可以避免最坏情况的发生。

2. 插入排序
当待排序序列的长度小于等于一定阈值时，使用插入排序算法进行排序。因为在小规模数据时，插入排序的效率比快速排序高。

3. 随机化
在选取基准元素时，随机选取一个元素作为基准元素。这样可以避免最坏情况的发生，并且可以减少数据集中在一侧的可能性。

4. 尾递归优化
在划分过程中，将较小的子序列递归排序，较大的子序列则采用迭代的方式进行排序。这样可以避免递归深度过大，导致栈溢出的问题。

下面是一个示例代码：

def quick_sort(arr, left=None, right=None):
    if left is None:
        left = 0
    if right is None:
        right = len(arr) - 1
    if right - left <= 10:
        # 当待排序序列的长度小于等于10时，使用插入排序
        insertion_sort(arr, left, right)
    else:
        # 三数取中法选取基准元素
        median = median_of_three(arr, left, right)
        # 将基准元素放到序列末尾
        arr[median], arr[right] = arr[right], arr[median]
        # 划分
        partition_index = partition(arr, left, right)
        # 尾递归优化
        if partition_index - left < right - partition_index:
            quick_sort(arr, left, partition_index - 1)
            left = partition_index + 1
        else:
            quick_sort(arr, partition_index + 1, right)
            right = partition_index - 1

def partition(arr, left, right):
    pivot = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i+1

def median_of_three(arr, left, right):
    mid = (left + right) // 2
    if arr[left] > arr[mid]:
        arr[left], arr[mid] = arr[mid], arr[left]
    if arr[left] > arr[right]:
        arr[left], arr[right] = arr[right], arr[left]
    if arr[mid] > arr[right]:
        arr[mid], arr[right] = arr[right], arr[mid]
    return mid

def insertion_sort(arr, left, right):
    for i in range(left+1, right+1):
        temp = arr[i]
        j = i - 1
        while j >= left and arr[j] > temp:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = temp