Searching and Sorting查找与排序

Pseudocode.伪代码。

INPUT data, target
FOR i FROM 0 TO length(data) - 1:
    IF data[i] == target THEN
        OUTPUT i
        STOP
OUTPUT -1   # not found

Code keywords above: FOR loop, IF condition, OUTPUT result, early STOP.以上代码关键字：FOR 循环，IF 条件，OUTPUT 输出，提前 STOP 停止。

Python implementation.Python 实现。

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1

temps = [14, 22, 8, 31, 19, 27, 5]
print(linear_search(temps, 27))  # Output: 5

Trace: index 0 (14≠27), index 1 (22≠27), index 2 (8≠27), index 3 (31≠27), index 4 (19≠27), index 5 (27==27) FOUND. Total: 6 comparisons. Worst case for 7 items would be 7.追踪：索引 0（14≠27），索引 1（22≠27），索引 2（8≠27），索引 3（31≠27），索引 4（19≠27），索引 5（27==27）找到。共 6 次比较。7 个元素的最坏情况为 7 次。

Pseudocode.伪代码。

INPUT data, target
SET low TO 0
SET high TO length(data) - 1
WHILE low <= high:
    SET mid TO (low + high) // 2
    IF data[mid] == target THEN
        OUTPUT mid
        STOP
    ELSE IF data[mid] < target THEN
        SET low TO mid + 1
    ELSE:
        SET high TO mid - 1
OUTPUT -1   # not found

Code keywords: // is integer division; low/high track the current search window.代码关键字：// 为整除；low/high 跟踪当前搜索窗口。

Step-by-step trace.逐步追踪。

Python implementation.Python 实现。

def binary_search(data, target):
    low, high = 0, len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [3, 8, 12, 17, 25, 34, 41, 55, 68, 77]
print(binary_search(nums, 34))  # Output: 5

3 comparisons to find 34 in a 10-element list. Linear search would need 6. The advantage grows dramatically for larger lists: a million items takes at most 20 binary-search comparisons vs up to 1,000,000 linear comparisons.在 10 个元素的列表中找到 34 只需 3 次比较；线性查找需要 6 次。对于更大的列表，优势急剧增加：100 万个元素最多需要 20 次二分比较，而线性查找最多需要 100 万次。

As n grows, the ratio between linear and binary search becomes enormous. This is the power of O(log n) vs O(n). The cost: binary search requires the list to be sorted first. Sorting itself takes time (O(n²) for simple sorts, O(n log n) for advanced sorts — see §7).随着 n 增大，线性与二分查找之间的比值变得极大。这就是 O(log n) 对比 O(n) 的威力。代价是：二分查找要求列表必须先排序。排序本身需要时间（简单排序 O(n²)，高级排序 O(n log n)——见 §7）。

Pseudocode.伪代码。

FOR pass FROM 0 TO length(data) - 2:
    FOR i FROM 0 TO length(data) - 2 - pass:
        IF data[i] > data[i+1] THEN
            SWAP data[i] AND data[i+1]

Inner loop compares adjacent pairs; outer loop repeats for each pass. After each pass, the boundary shrinks by 1 (the rightmost element is now sorted).内层循环比较相邻元素；外层循环对每遍重复。每遍后边界缩小 1（最右侧元素已排好）。

Pass-by-pass trace.逐遍追踪。

Python implementation.Python 实现。

def bubble_sort(data):
    n = len(data)
    for pass_num in range(n - 1):
        for i in range(n - 1 - pass_num):
            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]  # swap
    return data

print(bubble_sort([5, 3, 8, 1, 4]))  # Output: [1, 3, 4, 5, 8]

The data[i], data[i+1] = data[i+1], data[i] is the Python idiom for swapping two elements.data[i], data[i+1] = data[i+1], data[i] 是 Python 交换两个元素的惯用写法。

Pseudocode.伪代码。

FOR i FROM 0 TO length(data) - 2:
    SET min_idx TO i
    FOR j FROM i+1 TO length(data) - 1:
        IF data[j] < data[min_idx] THEN
            SET min_idx TO j
    SWAP data[i] AND data[min_idx]

Inner loop finds the minimum in the unsorted portion (indices i to end). Outer loop places it at position i.内层循环在未排序部分（索引 i 到末尾）中找最小值；外层循环将其放到位置 i。

Pass-by-pass trace.逐遍追踪。

Python implementation.Python 实现。

def selection_sort(data):
    n = len(data)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if data[j] < data[min_idx]:
                min_idx = j
        data[i], data[min_idx] = data[min_idx], data[i]  # swap
    return data

print(selection_sort([5, 3, 8, 1, 4]))  # Output: [1, 3, 4, 5, 8]

Selection sort made exactly 4 swaps for 5 elements (n-1 = 4). Bubble sort on the same list made 3+2+1+0 = 6 swaps. Fewer swaps is better when writes to memory are expensive.选择排序对 5 个元素恰好进行了 4 次交换（n-1 = 4）。相同列表的冒泡排序进行了 3+2+1+0 = 6 次交换。当内存写入代价高时，更少交换更好。

Pseudocode.伪代码。

FOR i FROM 1 TO length(data) - 1:
    SET key TO data[i]
    SET j TO i - 1
    WHILE j >= 0 AND data[j] > key:
        SET data[j+1] TO data[j]  # shift right
        SET j TO j - 1
    SET data[j+1] TO key          # insert key

key holds the element being inserted; the WHILE loop shifts larger elements one position right to make room.key 保存待插入元素；WHILE 循环将较大元素向右移一位腾出空间。

Step-by-step trace.逐步追踪。

Python implementation.Python 实现。

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]  # shift element right
            j -= 1
        data[j + 1] = key          # place key in correct position
    return data

print(insertion_sort([5, 3, 8, 1, 4]))  # Output: [1, 3, 4, 5, 8]

When key=8 (i=2), no shifts were needed because 8 > 5. This means nearly-sorted data has very few shifts, giving O(n) best-case performance — a property bubble sort and selection sort do not have.当 key=8（i=2）时，无需移位，因为 8 > 5。这意味着近乎有序数据的移位极少，达到 O(n) 最好情况性能——这是冒泡排序和选择排序所不具备的特性。

Python built-in sort examples.Python 内置排序示例。

# sorted() returns a NEW sorted list; original unchanged
nums = [5, 3, 8, 1, 4]
sorted_nums = sorted(nums)
print(sorted_nums)   # [1, 3, 4, 5, 8]
print(nums)          # [5, 3, 8, 1, 4]  -- unchanged

# .sort() sorts IN PLACE; modifies the original list
nums.sort()
print(nums)          # [1, 3, 4, 5, 8]

# Sort descending
nums.sort(reverse=True)
print(nums)          # [8, 5, 4, 3, 1]

# Sort strings or tuples by a key
students = [("Ana", 85), ("Bob", 72), ("Cara", 91)]
students.sort(key=lambda s: s[1])  # sort by score
print(students)  # [('Bob', 72), ('Ana', 85), ('Cara', 91)]

The key=lambda s: s[1] tells Python to sort by the second element (the score). Use sorted() when you need to keep the original; use .sort() when you want to modify in place.key=lambda s: s[1] 告知 Python 按第二个元素（分数）排序。需要保留原列表时用 sorted()；想原地修改时用 .sort()。

Combining sort + binary search in practice.实践中结合排序与二分查找。

import bisect  # Python standard library for binary search on sorted lists

data = [14, 2, 31, 8, 25, 17]
data.sort()                     # sort first: [2, 8, 14, 17, 25, 31]
pos = bisect.bisect_left(data, 17)  # binary search for 17
print(data[pos] == 17)          # True  (found at index 3)

The pattern: sort once with O(n log n), then use binary search O(log n) for every lookup. Far faster than repeated linear searches on large data.模式：用 O(n log n) 排序一次，再用 O(log n) 的二分查找进行每次查找。对大数据远快于重复线性查找。