插入排序 - 元素码农

发布时间: 2025-03-21 18:48

↑

# 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

## 基本原理

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

## 动画演示

```
初始数组：[ 5 2 4 6 1 3 ]

第一轮：
[ 5 | 2 4 6 1 3 ]  // 5已排序
[ 2 5 | 4 6 1 3 ]  // 插入2

第二轮：
[ 2 5 | 4 6 1 3 ]  // 2,5已排序
[ 2 4 5 | 6 1 3 ]  // 插入4

第三轮：
[ 2 4 5 | 6 1 3 ]  // 2,4,5已排序
[ 2 4 5 6 | 1 3 ]  // 插入6

第四轮：
[ 2 4 5 6 | 1 3 ]  // 2,4,5,6已排序
[ 1 2 4 5 6 | 3 ]  // 插入1

第五轮：
[ 1 2 4 5 6 | 3 ]  // 1,2,4,5,6已排序
[ 1 2 3 4 5 6 ]    // 插入3
```

## 代码实现

### 基本实现

```python
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

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
insertion_sort(arr)
print("排序后:", arr)
```

### 二分查找优化版本

```python
def binary_search(arr, key, start, end):
    # 使用二分查找找到插入位置
    while start < end:
        mid = (start + end) // 2
        if arr[mid] <= key:
            start = mid + 1
        else:
            end = mid
    return start

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用二分查找找到插入位置
        j = binary_search(arr, key, 0, i)
        
        # 将元素插入到正确位置
        arr[j+1:i+1] = arr[j:i]
        arr[j] = key
    
    return arr

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
binary_insertion_sort(arr)
print("排序后:", arr)
```

### 递归版本

```python
def recursive_insertion_sort(arr, n=None):
    if n is None:
        n = len(arr)
    
    # 基本情况：只有一个元素时已经排序
    if n <= 1:
        return
    
    # 递归排序前n-1个元素
    recursive_insertion_sort(arr, n - 1)
    
    # 将第n个元素插入到已排序的数组中
    key = arr[n - 1]
    j = n - 2
    
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    
    arr[j + 1] = key
    
    return arr

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
recursive_insertion_sort(arr)
print("排序后:", arr)
```

## 性能分析

### 时间复杂度

- 最好情况：O(n)，当数组已经排序时
- 最坏情况：O(n²)，当数组逆序时
- 平均情况：O(n²)

### 空间复杂度

- O(1)，只需要一个临时变量

### 稳定性

- 稳定排序算法
- 相等元素的相对位置保持不变

## 优缺点

### 优点

1. 实现简单
2. 稳定排序
3. 原地排序，空间复杂度低
4. 对于小规模数据或基本有序的数据效率高
5. 可以在排序过程中插入新元素

### 缺点

1. 对于大规模数据效率较低
2. 平均时间复杂度较高

## 应用场景

1. 小规模数据排序
2. 基本有序的数据排序
3. 实时排序（边插入边排序）
4. 嵌入式系统或低内存环境

## 实际应用示例

### 1. 扑克牌排序

```python
class Card:
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
    def __str__(self):
        return f"{self.suit}{self.value}"
    
    def __lt__(self, other):
        # 先按花色排序，再按数值排序
        if self.suit != other.suit:
            return self.suit < other.suit
        return self.value < other.value

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

# 使用示例
cards = [
    Card("♠", "A"), Card("♥", "5"),
    Card("♣", "10"), Card("♦", "K"),
    Card("♠", "3"), Card("♥", "2")
]

print("排序前:")
for card in cards:
    print(card)

sort_cards(cards)

print("\n排序后:")
for card in cards:
    print(card)
```

### 2. 实时数据排序

```python
class RealTimeSort:
    def __init__(self):
        self.data = []
    
    def insert(self, value):
        # 找到插入位置
        i = len(self.data)
        self.data.append(value)
        
        # 将元素插入到正确位置
        while i > 0 and self.data[i - 1] > value:
            self.data[i] = self.data[i - 1]
            i -= 1
        self.data[i] = value
    
    def get_sorted_data(self):
        return self.data

# 使用示例
sorter = RealTimeSort()

# 模拟实时数据输入
data_stream = [64, 34, 25, 12, 22, 11, 90]
for value in data_stream:
    print(f"\n插入数据 {value}:")
    sorter.insert(value)
    print("当前排序结果:", sorter.get_sorted_data())
```

### 3. 日志记录排序

```python
from datetime import datetime

class LogEntry:
    def __init__(self, timestamp, message):
        self.timestamp = timestamp
        self.message = message
    
    def __str__(self):
        return f"[{self.timestamp.strftime('%Y-%m-%d %H:%M:%S')}] {self.message}"

class LogSorter:
    def __init__(self):
        self.logs = []
    
    def add_log(self, log_entry):
        # 使用二分查找找到插入位置
        start = 0
        end = len(self.logs)
        
        while start < end:
            mid = (start + end) // 2
            if self.logs[mid].timestamp <= log_entry.timestamp:
                start = mid + 1
            else:
                end = mid
        
        # 插入日志
        self.logs.insert(start, log_entry)
    
    def get_sorted_logs(self):
        return self.logs

# 使用示例
sorter = LogSorter()

# 添加一些日志
logs = [
    LogEntry(datetime(2023, 5, 1, 10, 30), "系统启动"),
    LogEntry(datetime(2023, 5, 1, 10, 15), "配置加载"),
    LogEntry(datetime(2023, 5, 1, 10, 45), "用户登录"),
    LogEntry(datetime(2023, 5, 1, 10, 20), "数据库连接"),
    LogEntry(datetime(2023, 5, 1, 10, 35), "缓存初始化")
]

for log in logs:
    sorter.add_log(log)

print("按时间排序的日志:")
for log in sorter.get_sorted_logs():
    print(log)
```

## 总结

插入排序是一种简单但实用的排序算法，它的主要特点是：

1. 实现简单，容易理解
2. 对小规模数据效率高
3. 稳定排序
4. 原地排序，空间复杂度低
5. 适合实时排序场景

虽然它的平均时间复杂度为O(n²)，但在特定场景下（如小规模数据、基本有序的数据）仍然是一个很好的选择。它的工作原理也为其他更复杂的排序算法（如希尔排序）提供了基础。在实际应用中，插入排序常用于：

1. 作为其他排序算法的子过程
2. 处理小规模数据
3. 实时数据排序
4. 基本有序数据的排序优化