选择排序 - 元素码农

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

↑

# 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从未排序区域中找到最小（或最大）元素，将其放到已排序区域的末尾。这个过程会不断重复，直到所有元素都被排序。

## 基本原理

1. 将数组分为已排序区域和未排序区域
2. 在未排序区域中找到最小元素
3. 将该最小元素与未排序区域的第一个元素交换
4. 已排序区域增加一个元素，未排序区域减少一个元素
5. 重复步骤2-4，直到所有元素都被排序

## 动画演示

```
初始数组：[ 64 34 25 12 22 11 90 ]

第一轮：
[ 64 34 25 12 22 11 90 ]  // 找到最小值11
[ 11 34 25 12 22 64 90 ]  // 交换11和64

第二轮：
[ 11 34 25 12 22 64 90 ]  // 找到最小值12
[ 11 12 25 34 22 64 90 ]  // 交换12和34

第三轮：
[ 11 12 25 34 22 64 90 ]  // 找到最小值22
[ 11 12 22 34 25 64 90 ]  // 交换22和25

第四轮：
[ 11 12 22 34 25 64 90 ]  // 找到最小值25
[ 11 12 22 25 34 64 90 ]  // 交换25和34

第五轮：
[ 11 12 22 25 34 64 90 ]  // 找到最小值34
[ 11 12 22 25 34 64 90 ]  // 34已在正确位置

第六轮：
[ 11 12 22 25 34 64 90 ]  // 找到最小值64
[ 11 12 22 25 34 64 90 ]  // 64已在正确位置

排序完成：[ 11 12 22 25 34 64 90 ]
```

## 代码实现

### 基本实现

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

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

### 双向选择排序

```python
def bidirectional_selection_sort(arr):
    left = 0
    right = len(arr) - 1
    
    while left < right:
        # 记录最小值和最大值的位置
        min_idx = left
        max_idx = left
        
        # 在当前范围内寻找最小值和最大值
        for i in range(left, right + 1):
            if arr[i] < arr[min_idx]:
                min_idx = i
            if arr[i] > arr[max_idx]:
                max_idx = i
        
        # 将最小值放到左边
        if min_idx != left:
            arr[left], arr[min_idx] = arr[min_idx], arr[left]
            # 如果最大值是left，需要更新max_idx
            if max_idx == left:
                max_idx = min_idx
        
        # 将最大值放到右边
        if max_idx != right:
            arr[right], arr[max_idx] = arr[max_idx], arr[right]
        
        left += 1
        right -= 1
    
    return arr

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

### 递归版本

```python
def recursive_selection_sort(arr, start=0):
    if start >= len(arr) - 1:
        return arr
    
    # 找到未排序部分的最小值
    min_idx = start
    for i in range(start + 1, len(arr)):
        if arr[i] < arr[min_idx]:
            min_idx = i
    
    # 交换最小值到当前位置
    if min_idx != start:
        arr[start], arr[min_idx] = arr[min_idx], arr[start]
    
    # 递归处理剩余部分
    return recursive_selection_sort(arr, start + 1)

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

## 性能分析

### 时间复杂度

- 最好情况：O(n²)
- 最坏情况：O(n²)
- 平均情况：O(n²)

### 空间复杂度

- O(1)，只需要一个临时变量用于交换

### 稳定性

- 不稳定排序算法
- 相等元素的相对位置可能改变

## 优缺点

### 优点

1. 实现简单，容易理解
2. 交换次数少于冒泡排序
3. 对于小规模数据效率尚可
4. 原地排序，空间复杂度低

### 缺点

1. 时间复杂度固定为O(n²)
2. 不适合大规模数据排序
3. 不稳定排序

## 应用场景

1. 小规模数据排序
2. 对交换操作成本较高的场景
3. 辅助性排序算法
4. 教学演示

## 实际应用示例

### 1. 运动员排名

```python
class Athlete:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    
    def __str__(self):
        return f"{self.name}: {self.score}"

def rank_athletes(athletes):
    n = len(athletes)
    
    for i in range(n):
        max_idx = i
        for j in range(i + 1, n):
            if athletes[j].score > athletes[max_idx].score:
                max_idx = j
        
        if max_idx != i:
            athletes[i], athletes[max_idx] = athletes[max_idx], athletes[i]
    
    return athletes

# 使用示例
athletes = [
    Athlete("Alice", 95),
    Athlete("Bob", 88),
    Athlete("Charlie", 92),
    Athlete("David", 85),
    Athlete("Eve", 90)
]

print("排序前:")
for athlete in athletes:
    print(athlete)

rank_athletes(athletes)

print("\n按成绩降序排序后:")
for i, athlete in enumerate(athletes, 1):
    print(f"第{i}名: {athlete}")
```

### 2. 卡片排序

```python
class Card:
    SUITS = ['♠', '♥', '♣', '♦']
    VALUES = ['2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K', 'A']
    
    def __init__(self, suit, value):
        self.suit = suit
        self.value = value
    
    def __str__(self):
        return f"{self.suit}{self.value}"
    
    def get_rank(self):
        return self.SUITS.index(self.suit) * 13 + self.VALUES.index(self.value)

def sort_cards(cards):
    n = len(cards)
    
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if cards[j].get_rank() < cards[min_idx].get_rank():
                min_idx = j
        
        if min_idx != i:
            cards[i], cards[min_idx] = cards[min_idx], cards[i]
    
    return cards

# 使用示例
cards = [
    Card('♥', '7'),
    Card('♠', 'A'),
    Card('♦', '3'),
    Card('♣', 'K'),
    Card('♥', 'Q')
]

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

sort_cards(cards)

print("\n按花色和大小排序后:")
for card in cards:
    print(card)
```

## 总结

选择排序是一种基础的排序算法，它的主要特点是：

1. 实现简单，思路清晰
2. 交换次数较少
3. 时间复杂度固定为O(n²)
4. 不稳定排序

虽然选择排序的性能不如一些高级排序算法，但它在某些特定场景下仍然有其价值：

1. 作为其他算法的辅助排序
2. 处理小规模数据
3. 对交换操作成本较高的场景
4. 教学和演示用途

在实际应用中，可以根据具体需求选择基本实现、双向选择排序或递归版本，也可以针对特定场景进行优化。