非比较排序与 Python 的 sort()

比较排序的 O(n log n) 下界

import math

for n in [5, 10, 100, 1000]:
    lower_bound = n * math.log2(n)
    factorial_log = sum(math.log2(i) for i in range(1, n+1))
    print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')

# n log n is a tight bound on comparison-based sorting

计数排序：按频次排序

def counting_sort(arr, k=None):
    if not arr: return []
    if k is None: k = max(arr) + 1
    count = [0] * k
    for n in arr:
        count[n] += 1
    result = []
    for val, freq in enumerate(count):
        result.extend([val] * freq)
    return result

arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))  # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)

使用累积计数的稳定计数排序

def counting_sort_stable(arr, k):
    count = [0] * k
    for n in arr: count[n] += 1
    # Cumulative counts: count[v] = first position for value v
    for i in range(1, k): count[i] += count[i-1]
    output = [0] * len(arr)
    # Fill from right to maintain stability
    for n in reversed(arr):
        count[n] -= 1
        output[count[n]] = n
    return output

print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]

基数排序：逐位排序

def radix_sort(arr):
    if not arr: return []
    max_val = max(arr)
    exp = 1  # current digit position (1, 10, 100, ...)
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for n_ in arr: count[(n_ // exp) % 10] += 1
    for i in range(1, 10): count[i] += count[i-1]
    for n_ in reversed(arr):
        d = (n_ // exp) % 10
        count[d] -= 1
        output[count[d]] = n_
    return output

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

桶排序：分配到各个桶

def bucket_sort(arr):
    if not arr: return []
    n = len(arr)
    min_v, max_v = min(arr), max(arr)
    if min_v == max_v: return arr[:]
    buckets = [[] for _ in range(n)]
    # Map each value to a bucket index
    for v in arr:
        idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
        idx = min(idx, n - 1)
        buckets[idx].append(v)
    result = []
    for bucket in buckets:
        bucket.sort()  # insertion sort for small buckets
        result.extend(bucket)
    return result

print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted list

Python 的 Timsort 原理

# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs

import time

# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0  # one mis-placed element

t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')

Python 的 sort() 与 sorted()：关键区别

nums = [3, 1, 4, 1, 5, 9]

# in-place: returns None
result = nums.sort()
print(result)  # None  (common bug!)
print(nums)    # [1, 1, 3, 4, 5, 9]  (modified)

nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2)  # [1, 1, 3, 4, 5, 9]
print(nums2)    # [3, 1, 4, 1, 5, 9]  (unchanged)

面试中的自定义排序键

# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']

# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30']  => '9534330'

# Descending sort
print(sorted([3,1,4,1,5], reverse=True))  # [5,4,3,1,1]

面试中何时使用各种排序

# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space  (k=3 is tiny)

def sort_012(arr):
    count = [0, 0, 0]
    for n in arr:
        count[n] += 1
    i = 0
    for val in range(3):
        for _ in range(count[val]):
            arr[i] = val; i += 1

arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr)  # [0, 0, 1, 1, 2, 2]

不使用排序实现排序：用堆查找前 k 个元素

import heapq

# Top-k with heap: O(n log k)
def top_k(nums, k):
    return heapq.nlargest(k, nums)  # uses heap of size k internally

print(top_k([3,2,1,5,6,4], 2))    # [6, 5]

# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
    def _select(lo, hi, target):
        if lo >= hi: return nums[lo]
        rand_i = random.randint(lo, hi)
        nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
        pivot = nums[hi]; i = lo - 1
        for j in range(lo, hi):
            if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
        nums[i+1],nums[hi]=nums[hi],nums[i+1]
        p = i + 1
        if p == target: return nums[p]
        return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
    return _select(0, len(nums)-1, k-1)

print(kth_largest([3,2,1,5,6,4], 2))  # 5

多关键字排序中的排序稳定性

data = [
    ('Alice', 'Math',    90),
    ('Bob',   'Science', 85),
    ('Carol', 'Math',    90),
    ('Dave',  'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
    print(row)
# All score=90 rows: Math before Science (preserved from step 1)

快速检查

课程回顾