# 快速排序算法（quick sort）

下文简称“快排”。

快排算法的实现，在Python中有偷懒的做法，就是不对传入数组进行原地分区，show me the code:

# 快排实现之邀请面试官拷打版本
def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[-1]
    less = [x for x in arr[:-1] if x <= pivot]
    greater = [x for x in arr[:-1] if x > pivot]

    return quick_sort(less) + [pivot] + quick_sort(greater)

Ier：您这个实现看起来挺简洁嘛，说说看这么做有什么不足的地方？最差情况是什么？

Iee：嗯，您是指，啊，对了，嗯（笑容逐渐凝固.gif，磨磨叽叽假装思考...）

Ier: 我是指您代码里使用了额外的存储空间，`less` 和 `greater`，可以不用它们吗？

Iee：哦，您是指要对数组进行原地分区吗？（那些追求速度和基情的编程语言通常都是原地操作：应该是问这个吧？）

Ier: 对。

Iee：（心里嘀咕，就是怕那个 `partition()` 函数，怕啥来啥是吧:(，墨菲）

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    low, high = 0, len(arr)-1
    quick_sort_inplace(arr, low, high)

def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx-1)
        quick_sort_inplace(arr, pivot_idx+1, high)

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

Ier: 嗯，好。您的pivot是怎么选择的啊？

Iee：我是选了数组的最后一个元素。

Ier：嗯，那我有个问题请教一下，如果最后一个元素恰好是最大值或最小值的话，会怎么样？

Iee：（是啊，我也不太理解为什么这么草率地用最后一个元素呢？）嗯，啊，这个，应该是会导致分区效果不好吧。

Ier: 那还可以优化吗？

Iee：随机选择一个元素作为pivot？

好，要的就是这个“随机选择“。（顺便结束面试拷打模拟：)

我想你可能已经知道在快排里怎么引入随机pivot（不用怀疑，就是调用random.choice()）或选择 实现更好的pivot策略，比如三数取中法¹。

（更新：有时偷懒也不代表坏事，比如实现并行版本的快排）

（其实我是在看洗牌算法的时候看到random.randint()这个函数突然想起的快速排序算法里未完成 的故事，不过这个无关紧要，接着看看random这个令人好奇的玩具：）

# 伪随机数生成器 pseudo random number generator， PRNG

1946年, 冯.诺依曼首次给出了使用计算机程序产生随机数的方法, 但事实证明这种方法产生的数也 并非是随机的.一个普遍的观点是, 绝对随机的随机数只是一种理想的随机数, 计算机不会产生绝对 随机的随机数,它只能生成相对随机的随机数, 即伪随机数. 因此, 伪随机数并不是假随机数, 这里 的“伪”是有规律的意思, 就是产生的伪随机数既是随机的又是有规律的. 这样产生的数列虽然不是由真实的随机现象产生的, >但具有类似于随机数的统计性质, 可以作为随 机数来使用.

0-1均匀分布的伪随机数是最基本也是最简单的伪随机数, 它是生成一切其他分布的伪随机数的基础

好在统计学是学过一些皮毛的，这里说的随机数在DS哥们看来就是指从均匀分布生成样本（当然也可 以从其他随机分布获取）。这里有更详细的解释和内容：伪随机数与蒙特卡罗方法

但是大家知道，CS哥们从来都不是单单说出来，还要写出来。实际上用的随机数大多是随机数生成器 生的，又因为可以通过设定种子来使得每次都生成一样的随机数序列，因此又被蔑称为“伪随机数”。 而如果想知道具体代码实现中是怎么一回事，还得去源码丛林探险一番才行。

如果你的IDE不是很差，应该有功能支持直接跳转到randint()这个函数的实现代码处，然后一睹芳 容。我反正是看到了，但看不懂。有意思的是在浏览过程，看到了大佬的留言：

# Translated by Guido van Rossum from C source provided by
# Adrian Baddeley.  Adapted by Raymond Hettinger for use with
# the Mersenne Twister  and os.urandom() core generators.

以及doc-string里的：（对的，如果你也到了这个地方，你就不会惊讶，我是倒着往回读的）

* It is one of the most extensively tested generators in existence.
* The random() method is implemented in C, executes in a single Python step,
  and is, therefore, threadsafe.

这两段话其实信息量挺大（对我来说，巨大），比如random()由大佬翻译自另一大佬的C源码云云， 比如 Mersenne Twister（梅森旋转算法，用于提高随机数生成器性能），随便哪一个都足够喝上 一壶的了。

然后就被“threadsafe"击中，一来这个概念在我确实是一知半解，二来关于线程的问题确实被面试官 问过，三来相比其他概念，这个可能更接近我能够实际接触的概念范围。所以，这时我已经无暇顾及 random到底如何伪random起来了（内容太多时间太紧不能DFS²这些东西），而是想知道什么是线 程安全，它跟所谓的GIL有什么关系。

# 线程安全（thread-safty）与全局解释器锁（GIL）

## 线程安全

线程安全（thread-safety）是指在多线程环境中，某段代码能够被多个线程安全地访问和修改，而 不会引发数据竞争或不可预期的结果。如果代码不是线程安全的，在多个线程同时执行时可能会出现 问题，如数据不一致或程序崩溃。

线程安全的含义在这里可以理解为：即使多个线程同时调用 random() 函数，也不会引起冲突或者产 生错误结果。

The random() method is implemented in C, executes in a single Python step, and is, therefore, threadsafe.

这段话可以分成几个部分来理解：

Implemented in C： random() 函数的具体实现是在 Python 的 C 库中编写的，而不是直接用 Python 实现的。 这通常可以提高性能，因为 C 语言比 Python 更高效。

Executes in a single Python step： random() 方法在 Python 中是一个不可分割的单步操作。这意味着当你调用 random() 时， 整个生成随机数的过程是一个原子操作。即使有多个线程同时调用 random()，它们彼此之 间不会影响，因为它们每次都执行完全独立的一步。

Threadsafe： 由于 random() 的实现是原子的，意味着它在多线程环境下也是安全的。即使多个线程在同 一时间调用 random() 函数，它们不会互相干扰。每个线程调用 random() 时，都会生成一 个独立的随机数，而不会因为并发问题产生冲突。

## 非线程安全的情形

如果某个函数不是线程安全的，你可能需要手动加锁或同步线程，确保同时只有一个线程在执行该函 数。比如，对于一些状态共享的函数或对象（如累加器），需要用线程锁来确保不会产生竞态条件。

手动加锁？

手动加锁（manual locking）是指在多线程编程中，开发者通过显式加锁来控制线程访问共享资源的 过程，确保同一时间只有一个线程能访问该资源。这种机制主要用于解决竞态条件（race condition） 的问题。

为什么需要加锁？ 当多个线程同时访问共享数据时，可能会出现线程间的竞争。如果一个线程正在修改共享数据，另一 个线程同时访问它，可能会导致不一致或不可预测的行为。加锁可以确保同一时间只有一个线程可以 访问或修改共享资源，从而避免并发问题。

import threading

lock = threading.Lock()  # 创建一个锁对象
counter = 0

def increment():
    global counter
    for _ in range(100000):
        with lock:  # 加锁，确保同一时间只有一个线程修改 counter
            counter += 1

# 创建两个线程
t1 = threading.Thread(target=increment)
t2 = threading.Thread(target=increment)

# 启动线程
t1.start()
t2.start()

# 等待线程执行完毕
t1.join()
t2.join()

print(f"Final counter value: {counter}")

## 全局解释器锁 (GIL)

GIL（Global Interpreter Lock） 是 Python 解释器中的一个全局锁，存在于CPython实现中。它的 主要作用是确保在同一时刻只有一个线程可以执行 Python 字节码，避免多线程间对 Python 内部对 象的竞争访问。GIL 的作用:

• 保证线程安全：GIL 主要用于保护 Python 解释器中的内部数据结构，防止多个线程同时执行时， 出现数据竞争或不可预测的行为。GIL 通过限制同一时间只有一个线程执行，来确保这些数据结构 的线程安全。

• Python 对象的引用计数：Python 使用引用计数来管理内存，而引用计数的修改并不是线程安全的。 GIL 确保引用计数在多线程环境下不会出错。

老生长谈：虽然 Python 允许使用多线程，但由于 GIL 的存在，在CPU 密集型任务（如大量数 值计算）中，GIL 会成为性能瓶颈，因为无论有多少个线程同时执行，CPU 也只能真正地处理一个线 程。GIL 会在多个线程之间不断切换，导致无法真正利用多核 CPU 的性能。

import threading

def cpu_bound_task():
    x = 0
    for _ in range(10000000):
        x += 1

# 创建多个线程
threads = [threading.Thread(target=cpu_bound_task) for _ in range(4)]

for t in threads:
    t.start()

for t in threads:
    t.join()

即使创建了多个线程，这个任务由于是CPU 密集型任务，GIL 会导致在单核 CPU 上运行没有并发的 优势，甚至可能比单线程执行更慢，因为线程间不断切换会带来额外开销。

## 正确认识 GIL 的局限:

• CPU 密集型任务：由于 GIL 的存在，Python 的多线程无法充分利用多核 CPU 的性能，对于 CPU 密 集型任务，使用多线程并不能有效提高性能。

• I/O 密集型任务：对于 I/O 密集型任务（如文件读取、网络请求等），GIL 的影响较小，因为在 等待 I/O 操作完成时，GIL 可以释放，允许其他线程继续执行。因此，多线程仍然可以在 I/O 密 集型任务中提供显著的性能提升。

• GIL 是 Python 解释器的全局锁，自动确保 Python 的内部数据结构（如引用计数）是线程安全的。 虽然提供了线程安全，但会影响多线程在 CPU 密集型任务中的表现。对于性能敏感的任务，可能 需要考虑其他实现（如多进程或使用不受 GIL 限制的库）。

好了，学海无涯，让我们荡起双桨:)

后记：补一个三数取中法的实现：

def median_of_three(arr, low, high):
  mid = (low + high) // 2
  pivot_candidates = [arr[low], arr[mid], arr[high]]
  pivot_candidates.sort()
  return pivot_candidates[1]