MXMinglang Xie
All articles
八股文面试数据结构算法堆栈队列排序时间复杂度空间复杂度

堆栈队列与排序算法

系统整理栈、队列、堆和常见排序算法，并比较其时间与空间复杂度。

2025-10-26 · Updated 2025-11-19 · 28 分钟阅读

数据结构基础

什么是数据结构？

数据结构是计算机科学中组织和存储数据的方式，用于高效地访问和修改数据。

常见的数据结构：

  • 线性结构：数组、链表、栈、队列
  • 树形结构：二叉树、堆、B树
  • 图结构：有向图、无向图
  • 哈希结构：哈希表、哈希映射

栈（Stack）

什么是栈？

栈是一种后进先出（LIFO, Last In First Out）的线性数据结构，只能在栈顶进行插入和删除操作。

栈的特点：

  • 后进先出：最后入栈的元素最先出栈
  • 只能在栈顶操作：只能在栈顶进行插入（push）和删除（pop）
  • 有限大小：栈的大小通常是固定的

栈的操作：

  • **push(x)**：将元素 x 压入栈顶
  • **pop()**：删除并返回栈顶元素
  • **top()/peek()**：返回栈顶元素（不删除）
  • **empty()**：判断栈是否为空
  • **size()**：返回栈中元素的个数

栈的实现

使用数组实现栈

class ArrayStack:
    def __init__(self, capacity=100):
        self._stack = []
        self._capacity = capacity
    
    def push(self, item):
        if len(self._stack) >= self._capacity:
            raise OverflowError("Stack is full")
        self._stack.append(item)
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack.pop()
    
    def top(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack[-1]
    
    def is_empty(self):
        return len(self._stack) == 0
    
    def size(self):
        return len(self._stack)

使用链表实现栈

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedStack:
    def __init__(self):
        self._head = None
        self._size = 0
    
    def push(self, item):
        new_node = ListNode(item)
        new_node.next = self._head
        self._head = new_node
        self._size += 1
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        val = self._head.val
        self._head = self._head.next
        self._size -= 1
        return val
    
    def top(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._head.val
    
    def is_empty(self):
        return self._head is None
    
    def size(self):
        return self._size

Python 内置的栈

# Python 中可以使用 list 作为栈
stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop
top = stack.pop()  # 返回 3

# top
top = stack[-1]  # 返回 2，不删除

# empty
is_empty = len(stack) == 0

栈的应用

1. 表达式求值

def evaluate_expression(expression):
    """使用栈计算中缀表达式"""
    def precedence(op):
        if op in '+-':
            return 1
        if op in '*/':
            return 2
        return 0
    
    def apply_operator(values, operators):
        right = values.pop()
        left = values.pop()
        op = operators.pop()
        if op == '+':
            values.append(left + right)
        elif op == '-':
            values.append(left - right)
        elif op == '*':
            values.append(left * right)
        elif op == '/':
            values.append(left / right)
    
    values = []
    operators = []
    i = 0
    
    while i < len(expression):
        if expression[i] == ' ':
            i += 1
            continue
        
        if expression[i].isdigit():
            num = 0
            while i < len(expression) and expression[i].isdigit():
                num = num * 10 + int(expression[i])
                i += 1
            values.append(num)
            continue
        
        if expression[i] == '(':
            operators.append(expression[i])
        elif expression[i] == ')':
            while operators and operators[-1] != '(':
                apply_operator(values, operators)
            operators.pop()
        else:
            while operators and precedence(operators[-1]) >= precedence(expression[i]):
                apply_operator(values, operators)
            operators.append(expression[i])
        
        i += 1
    
    while operators:
        apply_operator(values, operators)
    
    return values[0] if values else 0

2. 括号匹配

def is_valid_parentheses(s):
    """判断括号是否匹配"""
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    
    return len(stack) == 0

3. 中缀转后缀表达式

def infix_to_postfix(expression):
    """将中缀表达式转换为后缀表达式"""
    def precedence(op):
        if op in '+-':
            return 1
        if op in '*/':
            return 2
        return 0
    
    result = []
    stack = []
    
    for char in expression:
        if char.isdigit() or char.isalpha():
            result.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                result.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and precedence(stack[-1]) >= precedence(char):
                result.append(stack.pop())
            stack.append(char)
    
    while stack:
        result.append(stack.pop())
    
    return ''.join(result)

4. 单调栈

单调栈是一种特殊的栈，栈中的元素保持单调性（递增或递减）。

def next_greater_element(nums):
    """找出每个元素右边第一个比它大的元素"""
    result = [-1] * len(nums)
    stack = []  # 存储索引，保持单调递减
    
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            index = stack.pop()
            result[index] = nums[i]
        stack.append(i)
    
    return result

def next_smaller_element(nums):
    """找出每个元素右边第一个比它小的元素"""
    result = [-1] * len(nums)
    stack = []  # 存储索引，保持单调递增
    
    for i in range(len(nums)):
        while stack and nums[stack[-1]] > nums[i]:
            index = stack.pop()
            result[index] = nums[i]
        stack.append(i)
    
    return result

最小栈（Min Stack）

最小栈是一种特殊的栈，可以在 O(1) 时间复杂度内返回栈中的最小元素。

实现方式 1：辅助栈

class MinStack:
    def __init__(self):
        self._stack = []
        self._min_stack = []  # 辅助栈，存储每个状态下的最小值
    
    def push(self, val):
        self._stack.append(val)
        if not self._min_stack or val <= self._min_stack[-1]:
            self._min_stack.append(val)
        else:
            self._min_stack.append(self._min_stack[-1])
    
    def pop(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        self._stack.pop()
        self._min_stack.pop()
    
    def top(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        return self._stack[-1]
    
    def get_min(self):
        if not self._min_stack:
            raise IndexError("Stack is empty")
        return self._min_stack[-1]

实现方式 2：存储差值

class MinStackOptimized:
    def __init__(self):
        self._stack = []
        self._min = None
    
    def push(self, val):
        if not self._stack:
            self._stack.append(0)
            self._min = val
        else:
            diff = val - self._min
            self._stack.append(diff)
            if diff < 0:
                self._min = val
    
    def pop(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        diff = self._stack.pop()
        if diff < 0:
            self._min = self._min - diff
    
    def top(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        diff = self._stack[-1]
        if diff < 0:
            return self._min
        else:
            return self._min + diff
    
    def get_min(self):
        if self._min is None:
            raise IndexError("Stack is empty")
        return self._min

实现方式 3：节点存储最小值

class StackNode:
    def __init__(self, val, min_val):
        self.val = val
        self.min_val = min_val

class MinStackNode:
    def __init__(self):
        self._stack = []
    
    def push(self, val):
        if not self._stack:
            min_val = val
        else:
            min_val = min(val, self._stack[-1].min_val)
        self._stack.append(StackNode(val, min_val))
    
    def pop(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        return self._stack.pop().val
    
    def top(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        return self._stack[-1].val
    
    def get_min(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        return self._stack[-1].min_val

队列（Queue）

什么是队列？

队列是一种先进先出（FIFO, First In First Out）的线性数据结构，在一端插入（队尾），在另一端删除（队首）。

队列的特点：

  • 先进先出：最先入队的元素最先出队
  • 两端操作：在队尾插入（enqueue），在队首删除（dequeue）
  • 有限大小：队列的大小通常是固定的

队列的操作：

  • **enqueue(x)**：将元素 x 插入队尾
  • **dequeue()**：删除并返回队首元素
  • **front()/peek()**：返回队首元素（不删除）
  • **empty()**：判断队列是否为空
  • **size()**：返回队列中元素的个数

队列的实现

使用数组实现队列

class ArrayQueue:
    def __init__(self, capacity=100):
        self._queue = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._rear = 0
        self._size = 0
    
    def enqueue(self, item):
        if self._size >= self._capacity:
            raise OverflowError("Queue is full")
        self._queue[self._rear] = item
        self._rear = (self._rear + 1) % self._capacity
        self._size += 1
    
    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self._queue[self._front]
        self._queue[self._front] = None
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return item
    
    def front(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._queue[self._front]
    
    def is_empty(self):
        return self._size == 0
    
    def size(self):
        return self._size

使用链表实现队列

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedQueue:
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
    
    def enqueue(self, item):
        new_node = ListNode(item)
        if self._tail is None:
            self._head = self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1
    
    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        val = self._head.val
        self._head = self._head.next
        if self._head is None:
            self._tail = None
        self._size -= 1
        return val
    
    def front(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._head.val
    
    def is_empty(self):
        return self._head is None
    
    def size(self):
        return self._size

Python 内置的队列

from collections import deque

# 使用 deque 作为队列（双端队列）
queue = deque()

# enqueue
queue.append(1)
queue.append(2)
queue.append(3)

# dequeue
front = queue.popleft()  # 返回 1

# front
front = queue[0]  # 返回 2，不删除

# empty
is_empty = len(queue) == 0

双端队列（Deque）

双端队列允许在两端进行插入和删除操作。

from collections import deque

deque_obj = deque()

# 在队首插入
deque_obj.appendleft(1)

# 在队尾插入
deque_obj.append(2)

# 在队首删除
left = deque_obj.popleft()

# 在队尾删除
right = deque_obj.pop()

优先队列（Priority Queue）

优先队列是一种特殊的队列，元素按优先级出队。

使用堆实现优先队列

import heapq

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._index = 0  # 用于处理优先级相同时的比较
    
    def push(self, item, priority):
        heapq.heappush(self._heap, (priority, self._index, item))
        self._index += 1
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        _, _, item = heapq.heappop(self._heap)
        return item
    
    def is_empty(self):
        return len(self._heap) == 0
    
    def size(self):
        return len(self._heap)

队列的应用

1. 层序遍历二叉树

def level_order_traversal(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        level = []
        size = len(queue)
        
        for _ in range(size):
            node = queue.pop(0)
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

2. BFS（广度优先搜索）

def bfs(graph, start):
    """图的广度优先搜索"""
    visited = set()
    queue = [start]
    result = []
    
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    
    return result

3. 滑动窗口最大值

def max_sliding_window(nums, k):
    """使用双端队列实现滑动窗口最大值"""
    if not nums or k == 0:
        return []
    
    deque_obj = []
    result = []
    
    for i in range(len(nums)):
        # 移除窗口外的元素
        while deque_obj and deque_obj[0] < i - k + 1:
            deque_obj.pop(0)
        
        # 移除小于当前元素的元素（保持单调递减）
        while deque_obj and nums[deque_obj[-1]] < nums[i]:
            deque_obj.pop()
        
        deque_obj.append(i)
        
        # 窗口形成后，记录最大值
        if i >= k - 1:
            result.append(nums[deque_obj[0]])
    
    return result

排序算法

排序算法分类

按稳定性分类：

  • 稳定排序：相同元素在排序后的相对位置不变（冒泡、插入、归并、计数、基数）
  • 不稳定排序：相同元素在排序后的相对位置可能改变（选择、快速、堆）

按时间复杂度分类：

  • **O(n²)**：冒泡、选择、插入
  • **O(n log n)**：快速、归并、堆
  • **O(n)**：计数、基数、桶

按空间复杂度分类：

  • 原地排序：O(1)（冒泡、选择、插入、快速、堆）
  • 非原地排序：O(n)（归并、计数、基数、桶）

冒泡排序（Bubble Sort）

原理： 重复遍历数组，比较相邻元素，如果顺序错误就交换。

时间复杂度： O(n²)
空间复杂度： O(1)
稳定性： 稳定

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 如果没有交换，说明已经有序
        if not swapped:
            break
    return arr

优化版本：

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        last_swap = n - 1
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                last_swap = j
        if not swapped:
            break
        n = last_swap + 1
    return arr

选择排序（Selection Sort）

原理： 每次找到未排序部分的最小元素，放到已排序部分的末尾。

时间复杂度： O(n²)
空间复杂度： O(1)
稳定性： 不稳定

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

插入排序（Insertion Sort）

原理： 将元素逐个插入到已排序部分的正确位置。

时间复杂度： O(n²)，最好情况 O(n)
空间复杂度： O(1)
稳定性： 稳定

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

二分插入排序：

def binary_insertion_sort(arr):
    def binary_search(arr, val, start, end):
        while start < end:
            mid = (start + end) // 2
            if arr[mid] < val:
                start = mid + 1
            else:
                end = mid
        return start
    
    for i in range(1, len(arr)):
        key = arr[i]
        pos = binary_search(arr, key, 0, i)
        arr[pos + 1:i + 1] = arr[pos:i]
        arr[pos] = key
    return arr

快速排序（Quick Sort）

原理： 选择一个基准元素，将数组分成两部分，小于基准的放左边，大于基准的放右边，递归处理两部分。

时间复杂度： 平均 O(n log n)，最坏 O(n²)
空间复杂度： 平均 O(log n)，最坏 O(n)
稳定性： 不稳定

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    return arr

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

三路快排（处理重复元素）：

def quick_sort_3way(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low >= high:
        return
    
    lt, i, gt = low, low, high
    pivot = arr[low]
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    quick_sort_3way(arr, low, lt - 1)
    quick_sort_3way(arr, gt + 1, high)
    return arr

归并排序（Merge Sort）

原理： 将数组分成两半，递归排序，然后合并两个有序数组。

时间复杂度： O(n log n)
空间复杂度： O(n)
稳定性： 稳定

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, 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

原地归并排序（优化空间）：

def merge_sort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        mid = (low + high) // 2
        merge_sort_inplace(arr, low, mid)
        merge_sort_inplace(arr, mid + 1, high)
        merge_inplace(arr, low, mid, high)
    return arr

def merge_inplace(arr, low, mid, high):
    left = arr[low:mid + 1]
    right = arr[mid + 1:high + 1]
    
    i, j, k = 0, 0, low
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1
    
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

堆排序（Heap Sort）

原理： 构建最大堆，然后将堆顶元素（最大值）与末尾元素交换，调整堆，重复此过程。

时间复杂度： O(n log n)
空间复杂度： O(1)
稳定性： 不稳定

def heap_sort(arr):
    n = len(arr)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个取出堆顶元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

使用 heapq 模块：

import heapq

def heap_sort_builtin(arr):
    heap = arr[:]
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]

计数排序（Counting Sort）

原理： 统计每个元素出现的次数，然后按照计数结果输出。

时间复杂度： O(n + k)，k 是数据范围
空间复杂度： O(k)
稳定性： 稳定

def counting_sort(arr, max_val=None):
    if max_val is None:
        max_val = max(arr) if arr else 0
    
    count = [0] * (max_val + 1)
    
    # 计数
    for num in arr:
        count[num] += 1
    
    # 累计计数
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 输出
    result = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        count[arr[i]] -= 1
        result[count[arr[i]]] = arr[i]
    
    return result

基数排序（Radix Sort）

原理： 按照低位到高位的顺序，依次对每一位进行计数排序。

时间复杂度： O(d × (n + k))，d 是位数，k 是基数
空间复杂度： O(n + k)
稳定性： 稳定

def radix_sort(arr):
    if not arr:
        return arr
    
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        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 i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # 累计计数
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 输出
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    for i in range(n):
        arr[i] = output[i]

桶排序（Bucket Sort）

原理： 将数据分成若干个桶，对每个桶进行排序，然后合并。

时间复杂度： 平均 O(n + k)，最坏 O(n²)
空间复杂度： O(n + k)
稳定性： 稳定

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return arr
    
    min_val = min(arr)
    max_val = max(arr)
    bucket_size = (max_val - min_val) / bucket_count + 1
    
    buckets = [[] for _ in range(bucket_count)]
    
    # 将元素分配到桶中
    for num in arr:
        index = int((num - min_val) / bucket_size)
        buckets[index].append(num)
    
    # 对每个桶进行排序
    for bucket in buckets:
        bucket.sort()  # 可以使用其他排序算法
    
    # 合并结果
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

希尔排序（Shell Sort）

原理： 改进的插入排序，通过分组进行插入排序，逐步缩小间隔。

时间复杂度： 平均 O(n^1.3)，最坏 O(n²)
空间复杂度： O(1)
稳定性： 不稳定

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    
    return arr

排序算法总结

算法平均时间最坏时间空间复杂度稳定性
冒泡排序O(n²)O(n²)O(1)稳定
选择排序O(n²)O(n²)O(1)不稳定
插入排序O(n²)O(n²)O(1)稳定
快速排序O(n log n)O(n²)O(log n)不稳定
归并排序O(n log n)O(n log n)O(n)稳定
堆排序O(n log n)O(n log n)O(1)不稳定
计数排序O(n + k)O(n + k)O(k)稳定
基数排序O(d × n)O(d × n)O(n + k)稳定
桶排序O(n + k)O(n²)O(n + k)稳定
希尔排序O(n^1.3)O(n²)O(1)不稳定

时间复杂度与空间复杂度

时间复杂度（Time Complexity）

时间复杂度是算法执行时间随输入规模增长的增长率。

常见的时间复杂度

1. O(1) - 常数时间复杂度

def get_first_element(arr):
    return arr[0]  # 无论数组多大，都是常数时间

2. O(log n) - 对数时间复杂度

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

3. O(n) - 线性时间复杂度

def linear_search(arr, target):
    for i, num in enumerate(arr):
        if num == target:
            return i
    return -1

4. O(n log n) - 线性对数时间复杂度

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)  # 归并排序

5. O(n²) - 平方时间复杂度

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

6. O(n³) - 立方时间复杂度

def matrix_multiplication(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

7. O(2ⁿ) - 指数时间复杂度

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

8. O(n!) - 阶乘时间复杂度

def generate_permutations(arr):
    if len(arr) <= 1:
        return [arr]
    result = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for perm in generate_permutations(rest):
            result.append([arr[i]] + perm)
    return result

时间复杂度的计算方法

1. 单个循环

# O(n)
for i in range(n):
    # 常数时间操作
    pass

2. 嵌套循环

# O(n²)
for i in range(n):
    for j in range(n):
        # 常数时间操作
        pass

3. 循环中的循环

# O(n²)
for i in range(n):
    for j in range(i, n):
        # 常数时间操作
        pass
# 总次数：n + (n-1) + ... + 1 = n(n+1)/2 = O(n²)

4. 递归调用

# O(2ⁿ)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
# T(n) = T(n-1) + T(n-2) + O(1) ≈ O(2ⁿ)

5. 分治算法

# O(n log n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # T(n/2)
    right = merge_sort(arr[mid:])     # T(n/2)
    return merge(left, right)          # O(n)
# T(n) = 2T(n/2) + O(n) = O(n log n)

最好、平均、最坏时间复杂度

1. 最好情况时间复杂度（Best Case）

  • 算法在最理想情况下的时间复杂度
  • 例如：冒泡排序最好情况 O(n)（已经有序）

2. 平均情况时间复杂度（Average Case）

  • 算法在所有可能输入情况下的平均时间复杂度
  • 例如：快速排序平均情况 O(n log n)

3. 最坏情况时间复杂度（Worst Case）

  • 算法在最坏情况下的时间复杂度
  • 例如：快速排序最坏情况 O(n²)（每次都选到最大或最小元素）

空间复杂度（Space Complexity）

空间复杂度是算法使用的额外内存空间随输入规模增长的增长率。

常见的空间复杂度

1. O(1) - 常数空间复杂度

def swap(a, b):
    a, b = b, a  # 只使用常数个额外变量

2. O(n) - 线性空间复杂度

def copy_array(arr):
    result = [0] * len(arr)  # 创建长度为 n 的数组
    for i in range(len(arr)):
        result[i] = arr[i]
    return result

3. O(n²) - 平方空间复杂度

def create_matrix(n):
    return [[0] * n for _ in range(n)]  # n × n 的矩阵

4. O(log n) - 对数空间复杂度

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)
# 递归深度为 log n，栈空间为 O(log n)

空间复杂度的计算方法

1. 变量空间

# O(1)
def sum_array(arr):
    total = 0  # 1 个变量
    for num in arr:
        total += num
    return total

2. 数组空间

# O(n)
def reverse_array(arr):
    result = [0] * len(arr)  # 长度为 n 的数组
    for i in range(len(arr)):
        result[i] = arr[len(arr) - 1 - i]
    return result

3. 递归栈空间

# O(n)
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)
# 递归深度为 n，栈空间为 O(n)

4. 哈希表空间

# O(n)
def count_frequency(arr):
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq
# 最坏情况下，所有元素都不同，需要 O(n) 空间

复杂度分析示例

示例 1：数组求和

def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total
# 时间复杂度：O(n)
# 空间复杂度：O(1)

示例 2：冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
# 时间复杂度：O(n²)
# 空间复杂度：O(1)

示例 3：归并排序

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, 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
# 时间复杂度：O(n log n)
# 空间复杂度：O(n)

示例 4：快速排序

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    return arr

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
# 时间复杂度：平均 O(n log n)，最坏 O(n²)
# 空间复杂度：平均 O(log n)，最坏 O(n)

常见面试题

栈相关面试题

1. 实现一个栈，支持 O(1) 时间复杂度的 getMin() 操作

class MinStack:
    def __init__(self):
        self._stack = []
        self._min_stack = []
    
    def push(self, val):
        self._stack.append(val)
        if not self._min_stack or val <= self._min_stack[-1]:
            self._min_stack.append(val)
        else:
            self._min_stack.append(self._min_stack[-1])
    
    def pop(self):
        if not self._stack:
            raise IndexError("Stack is empty")
        self._stack.pop()
        self._min_stack.pop()
    
    def top(self):
        return self._stack[-1] if self._stack else None
    
    def get_min(self):
        return self._min_stack[-1] if self._min_stack else None

2. 用两个栈实现队列

class QueueWithStacks:
    def __init__(self):
        self._stack1 = []
        self._stack2 = []
    
    def enqueue(self, x):
        self._stack1.append(x)
    
    def dequeue(self):
        if not self._stack2:
            while self._stack1:
                self._stack2.append(self._stack1.pop())
        if not self._stack2:
            raise IndexError("Queue is empty")
        return self._stack2.pop()
    
    def front(self):
        if not self._stack2:
            while self._stack1:
                self._stack2.append(self._stack1.pop())
        if not self._stack2:
            raise IndexError("Queue is empty")
        return self._stack2[-1]

3. 用两个队列实现栈

from collections import deque

class StackWithQueues:
    def __init__(self):
        self._queue1 = deque()
        self._queue2 = deque()
    
    def push(self, x):
        self._queue1.append(x)
    
    def pop(self):
        if not self._queue1:
            raise IndexError("Stack is empty")
        while len(self._queue1) > 1:
            self._queue2.append(self._queue1.popleft())
        result = self._queue1.popleft()
        self._queue1, self._queue2 = self._queue2, self._queue1
        return result
    
    def top(self):
        if not self._queue1:
            raise IndexError("Stack is empty")
        return self._queue1[-1]
    
    def empty(self):
        return len(self._queue1) == 0

4. 有效的括号

def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    
    return len(stack) == 0

5. 每日温度（下一个更大元素）

def daily_temperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []  # 存储索引
    
    for i in range(len(temperatures)):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            index = stack.pop()
            result[index] = i - index
        stack.append(i)
    
    return result

队列相关面试题

1. 滑动窗口最大值

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k == 0:
        return []
    
    deque_obj = deque()
    result = []
    
    for i in range(len(nums)):
        # 移除窗口外的元素
        while deque_obj and deque_obj[0] < i - k + 1:
            deque_obj.popleft()
        
        # 移除小于当前元素的元素（保持单调递减）
        while deque_obj and nums[deque_obj[-1]] < nums[i]:
            deque_obj.pop()
        
        deque_obj.append(i)
        
        # 窗口形成后，记录最大值
        if i >= k - 1:
            result.append(nums[deque_obj[0]])
    
    return result

2. 设计循环队列

class CircularQueue:
    def __init__(self, k):
        self._queue = [None] * k
        self._capacity = k
        self._front = 0
        self._rear = 0
        self._size = 0
    
    def enqueue(self, value):
        if self.is_full():
            return False
        self._queue[self._rear] = value
        self._rear = (self._rear + 1) % self._capacity
        self._size += 1
        return True
    
    def dequeue(self):
        if self.is_empty():
            return False
        self._queue[self._front] = None
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return True
    
    def front(self):
        if self.is_empty():
            return -1
        return self._queue[self._front]
    
    def rear(self):
        if self.is_empty():
            return -1
        return self._queue[(self._rear - 1) % self._capacity]
    
    def is_empty(self):
        return self._size == 0
    
    def is_full(self):
        return self._size == self._capacity

排序算法面试题

1. 排序算法的稳定性是什么？为什么重要？

答案：

  • 稳定性：相同元素在排序后的相对位置不变
  • 重要性：
    • 多关键字排序：先按一个关键字排序，再按另一个关键字排序
    • 保持原有顺序：对于相同元素，保持它们在原数组中的顺序
    • 例如：按姓名排序后再按年龄排序，年龄相同时保持姓名顺序

2. 快速排序和归并排序的区别？

答案：

特性快速排序归并排序
时间复杂度平均 O(n log n)，最坏 O(n²)始终 O(n log n)
空间复杂度平均 O(log n)，最坏 O(n)O(n)
稳定性不稳定稳定
实现方式原地排序（in-place）需要额外空间
最坏情况已经有序或逆序始终相同
适用场景大数据量，随机数据需要稳定性，小数据量

3. 什么情况下使用计数排序？

答案：

  • 数据范围小：数据范围远小于数据个数（如年龄、成绩）
  • 非负整数：数据是非负整数
  • 需要稳定性：需要稳定排序
  • 时间复杂度：需要 O(n + k) 的时间复杂度

示例：

# 适合计数排序：0-100 的年龄数据
ages = [25, 30, 25, 28, 30, 25]

# 不适合计数排序：数据范围太大（如 ID）
ids = [1000000, 2000000, 3000000, ...]

4. 如何选择排序算法？

答案：

场景推荐算法原因
小数据量（< 50）插入排序简单、常数因子小
大数据量，随机数据快速排序平均性能最好
需要稳定性归并排序稳定且时间复杂度稳定
数据范围小计数排序O(n + k) 时间复杂度
需要原地排序堆排序O(1) 空间复杂度
部分有序插入排序最好情况 O(n)

5. 如何优化快速排序？

答案：

  1. 随机选择基准：避免最坏情况
  2. 三路快排：处理重复元素
  3. 插入排序优化：小数组使用插入排序
  4. 尾递归优化：减少栈空间
def quick_sort_optimized(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    # 小数组使用插入排序
    if high - low < 10:
        return insertion_sort(arr[low:high+1])
    
    # 随机选择基准
    import random
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_optimized(arr, low, pi - 1)
        quick_sort_optimized(arr, pi + 1, high)
    
    return arr

复杂度分析面试题

1. 如何计算递归算法的时间复杂度？

答案：
使用递推公式或主定理（Master Theorem）。

示例 1：归并排序

T(n) = 2T(n/2) + O(n)
使用主定理：a = 2, b = 2, f(n) = O(n)
log_b(a) = log_2(2) = 1
f(n) = O(n^1)
所以 T(n) = O(n log n)

示例 2：二分查找

T(n) = T(n/2) + O(1)
使用主定理：a = 1, b = 2, f(n) = O(1)
log_b(a) = log_2(1) = 0
f(n) = O(n^0)
所以 T(n) = O(log n)

2. 如何计算递归算法的空间复杂度？

答案：
空间复杂度 = 递归深度 × 每次递归的空间复杂度

示例：

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# 递归深度：O(n)
# 每次递归空间：O(1)
# 总空间复杂度：O(n)

3. 时间复杂度 O(n) 和 O(n log n) 哪个更好？

答案：

  • O(n) 更好：线性时间比线性对数时间快
  • 但是：考虑常数因子，O(n log n) 的常数可能更小
  • 实际场景：当 n 很大时，O(n log n) 和 O(n) 的差距很明显

总结

核心要点：

  1. 栈（Stack）：

    • LIFO 结构，后进先出
    • 应用：表达式求值、括号匹配、递归调用
    • 最小栈可以在 O(1) 时间内获取最小值

  2. 队列（Queue）：

    • FIFO 结构，先进先出
    • 应用：BFS、层序遍历、任务调度
    • 双端队列和优先队列是重要变体

  3. 排序算法：

    • 稳定排序：冒泡、插入、归并、计数、基数
    • O(n log n)：快速、归并、堆
    • O(n)：计数、基数、桶（特定条件下）

  4. 复杂度分析：

    • 时间复杂度：算法执行时间的增长率
    • 空间复杂度：算法使用内存的增长率
    • 需要分析最好、平均、最坏情况

面试重点：

  • 栈和队列的实现和应用
  • 最小栈的实现（多种方法）
  • 各种排序算法的特点、时间空间复杂度
  • 排序算法的稳定性
  • 如何选择排序算法
  • 时间复杂度和空间复杂度的计算

实际应用：

在实际项目中：

  • 栈：用于表达式解析、函数调用、撤销操作
  • 队列：用于任务调度、消息队列、BFS 算法
  • 排序：根据数据特点选择最合适的排序算法
  • 复杂度分析：评估算法性能，优化代码

参考资料：

  • 《算法导论》（Introduction to Algorithms）
  • 《数据结构与算法分析》（Data Structures and Algorithm Analysis）
  • 《编程珠玑》（Programming Pearls）
  • LeetCode 算法专题

Originally published on mlangTse's Blog. View source