算法基础 - 计算机基础

01. 排序算法

排序是将数据按特定顺序排列的过程。常见排序算法的时间复杂度和特点：冒泡排序：O(n²)，简单但效率低，稳定排序。选择排序：O(n²)，不稳定，交换次数少。插入排序：O(n²)，对几乎有序的数据效率高。快速排序：O(n log n) 平均，不稳定，实际应用最广泛。归并排序：O(n log n)，稳定，需要额外空间。堆排序：O(n log n)，不稳定，原地排序。

python

# 快速排序
def quick_sort(arr):
if len(arr) <= 1:
    return arr

pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

# 归并排序
def merge_sort(arr):
if len(arr) <= 1:
    return arr

mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])

return merge(left, right)

def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1
result.extend(left[i:])
result.extend(right[j:])
return result

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]

02. 搜索算法

搜索是在数据集合中查找特定元素的过程。线性搜索：逐个检查元素，时间复杂度 O(n)。适用于无序数据。二分搜索：在有序数据中反复折半查找，时间复杂度 O(log n)。效率极高。二分搜索的前提是数据必须有序。每次比较排除一半的搜索空间。

python

# 二分搜索（迭代版）
def binary_search(arr, target):
left, right = 0, len(arr) - 1

while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

return -1

# 二分搜索（递归版）
def binary_search_recursive(arr, target, left, right):
if left > right:
    return -1

mid = (left + right) // 2
if arr[mid] == target:
    return mid
elif arr[mid] < target:
    return binary_search_recursive(arr, target, mid + 1, right)
else:
    return binary_search_recursive(arr, target, left, mid - 1)

# 测试
sorted_arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(sorted_arr, 7))  # 6
print(binary_search(sorted_arr, 11)) # -1

知识测验

第 1/5 题正确 0

快速排序的平均时间复杂度是？

设计模式