如何使用 Python 实现快速排序算法中每次随机选择基值？

python 快速排序中每次随机选择基值的实现

在 python 的快速排序算法中，使用随机基值可以提升算法效率，避免最坏情况下的平方时间复杂度。本文将重点讨论如何在快速排序中实现每次排序随机选取基值。

问题：

如何在 python 的快速排序算法中每次排序随机选取基值？

立即学习“Python免费学习笔记（深入）”；

解答：

为了在快速排序中实现每次随机选择基值，需要使用 python 的内置函数 random.randint。此函数可生成指定范围内的随机整数。

具体实现方式如下：

1. 导入 random 库：

import random

1. 将原本固定选择第一个元素作为基值的代码：

pivot = array[0]

修改为：

pivot = array[random.randint(0, len(array) - 1)]

这样，每次排序时都会从数组中随机选择一个元素作为基值。

通过这种方式，可以有效提高快速排序算法的平均时间复杂度，使其接近 o(n log n)。