快速排序的随机化版本

快速排序的随机化版本是一种改进的快速排序算法，它通过随机选择基准元素来避免最坏情况的发生，从而提高算法的效率。

下面是快速排序的随机化版本的示例代码：

import random

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = random.choice(arr) # 随机选择基准元素
        smaller = [x for x in arr if x < pivot]
        equal = [x for x in arr if x == pivot]
        larger = [x for x in arr if x > pivot]
        return quicksort(smaller) + equal + quicksort(larger)

# 示例
arr = [5, 2, 8, 6, 1, 9]
sorted_arr = quicksort(arr)
print(sorted_arr) # 输出：[1, 2, 5, 6, 8, 9]

在这个示例中，我们使用`random.choice()`函数来随机选择基准元素。然后，我们将数组分成三个部分：小于基准元素的部分、等于基准元素的部分和大于基准元素的部分。最后，我们递归地对小于和大于部分进行快速排序，并将它们与等于部分合并起来。

快速排序的随机化版本的时间复杂度仍然是O(nlogn)，但是由于随机选择基准元素，它避免了最坏情况的发生，因此在实际应用中通常比普通的快速排序更加高效。