跳转至

选择排序

概述

选择排序每次从未排序部分选择最小元素，放到已排序部分的末尾。

算法思想

  1. 在未排序序列中找到最小元素
  2. 将其放到已排序序列末尾
  3. 重复直到所有元素排序完成

算法演示

Text Only
1
2
3
4
5
6
初始: 5  3  8  4  2

[2] 3  8  4  5  -> 选择最小2，与5交换
[2] [3] 8  4  5  -> 选择最小3，已在位置
[2] [3] [4] 8  5  -> 选择最小4，与8交换
[2] [3] [4] [5] 8  -> 选择最小5，与8交换

基本实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
template<typename T>
void selectionSort(std::vector<T>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        if (minIndex != i) {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        
        if minIndex != i {
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
        }
    }
}
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n-1 {
        let mut min_index = i;
        
        for j in i+1..n {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        
        if min_index != i {
            arr.swap(i, min_index);
        }
    }
}

双向选择排序（鸡尾酒选择排序）

同时找到最小值和最大值,减少排序轮数。

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void doubleSelectionSort(int arr[], int n) {
    int left = 0, right = n - 1;
    
    while (left < right) {
        int minIndex = left, maxIndex = left;
        
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
            if (arr[i] > arr[maxIndex]) maxIndex = i;
        }
        
        int temp = arr[left];
        arr[left] = arr[minIndex];
        arr[minIndex] = temp;
        
        if (maxIndex == left) maxIndex = minIndex;
        
        temp = arr[right];
        arr[right] = arr[maxIndex];
        arr[maxIndex] = temp;
        
        left++;
        right--;
    }
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
template<typename T>
void doubleSelectionSort(std::vector<T>& arr) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int minIndex = left, maxIndex = left;
        
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
            if (arr[i] > arr[maxIndex]) maxIndex = i;
        }
        
        std::swap(arr[left], arr[minIndex]);
        if (maxIndex == left) maxIndex = minIndex;
        std::swap(arr[right], arr[maxIndex]);
        
        left++;
        right--;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def double_selection_sort(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        min_index, max_index = left, left
        
        for i in range(left, right + 1):
            if arr[i] < arr[min_index]:
                min_index = i
            if arr[i] > arr[max_index]:
                max_index = i
        
        arr[left], arr[min_index] = arr[min_index], arr[left]
        if max_index == left:
            max_index = min_index
        arr[right], arr[max_index] = arr[max_index], arr[right]
        
        left += 1
        right -= 1
    
    return arr
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void doubleSelectionSort(int[] arr) {
    int left = 0, right = arr.length - 1;
    
    while (left < right) {
        int minIndex = left, maxIndex = left;
        
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) minIndex = i;
            if (arr[i] > arr[maxIndex]) maxIndex = i;
        }
        
        int temp = arr[left];
        arr[left] = arr[minIndex];
        arr[minIndex] = temp;
        
        if (maxIndex == left) maxIndex = minIndex;
        
        temp = arr[right];
        arr[right] = arr[maxIndex];
        arr[maxIndex] = temp;
        
        left++;
        right--;
    }
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func doubleSelectionSort(arr []int) {
    left, right := 0, len(arr)-1
    
    for left < right {
        minIndex, maxIndex := left, left
        
        for i := left; i <= right; i++ {
            if arr[i] < arr[minIndex] {
                minIndex = i
            }
            if arr[i] > arr[maxIndex] {
                maxIndex = i
            }
        }
        
        arr[left], arr[minIndex] = arr[minIndex], arr[left]
        if maxIndex == left {
            maxIndex = minIndex
        }
        arr[right], arr[maxIndex] = arr[maxIndex], arr[right]
        
        left++
        right--
    }
}
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
fn double_selection_sort(arr: &mut [i32]) {
    let mut left = 0;
    let mut right = arr.len() - 1;
    
    while left < right {
        let mut min_index = left;
        let mut max_index = left;
        
        for i in left..=right {
            if arr[i] < arr[min_index] {
                min_index = i;
            }
            if arr[i] > arr[max_index] {
                max_index = i;
            }
        }
        
        arr.swap(left, min_index);
        if max_index == left {
            max_index = min_index;
        }
        arr.swap(right, max_index);
        
        left += 1;
        right -= 1;
    }
}

复杂度分析

情况 时间复杂度 比较次数 交换次数
最好 O(n²) n(n-1)/2 0
平均 O(n²) n(n-1)/2 n-1
最坏 O(n²) n(n-1)/2 n-1

空间复杂度：O(1)

稳定性

选择排序是**不稳定排序**：

Text Only
1
2
3
原序列: 3A  3B  2  1
选择最小1: 1  3B  2  3A
选择最小2: 1  2  3B  3A  (3A和3B顺序改变)

稳定选择排序

通过移动元素而不是交换来保持稳定性。

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void stableSelectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 移动元素而不是交换
        int key = arr[minIndex];
        for (int j = minIndex; j > i; j--) {
            arr[j] = arr[j - 1];
        }
        arr[i] = key;
    }
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
template<typename T>
void stableSelectionSort(std::vector<T>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        T key = arr[minIndex];
        for (int j = minIndex; j > i; j--) {
            arr[j] = arr[j - 1];
        }
        arr[i] = key;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def stable_selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 移动元素而不是交换
        key = arr[min_index]
        for j in range(min_index, i, -1):
            arr[j] = arr[j - 1]
        arr[i] = key
    
    return arr
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public static void stableSelectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        int key = arr[minIndex];
        for (int j = minIndex; j > i; j--) {
            arr[j] = arr[j - 1];
        }
        arr[i] = key;
    }
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func stableSelectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        
        key := arr[minIndex]
        for j := minIndex; j > i; j-- {
            arr[j] = arr[j-1]
        }
        arr[i] = key
    }
}
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
fn stable_selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n-1 {
        let mut min_index = i;
        
        for j in i+1..n {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        
        let key = arr[min_index];
        for j in (i+1..=min_index).rev() {
            arr[j] = arr[j-1];
        }
        arr[i] = key;
    }
}

适用场景

  1. 小规模数据：n较小时可接受
  2. 交换代价高：交换次数最少（最多n-1次）
  3. 内存写入敏感：减少写入操作

选择排序 vs 插入排序

特性 选择排序 插入排序
比较次数 固定n(n-1)/2 依赖输入
交换次数 最多n-1 可能n(n-1)/2
稳定性 不稳定 稳定
有序输入 仍需完整比较 O(n)

参考资料

  • 《算法导论》第2章
  • 《数据结构与算法分析》第7章