选择排序:修订间差异
外观
Page creation by admin bot |
Page update by admin bot |
||
第1行: | 第1行: | ||
{{Note| | {{Note|本条目讲解'''选择排序'''(Selection Sort)的基本原理、实现方法、复杂度分析及实际应用场景,适合编程初学者和需要复习基础算法的开发者。}} | ||
== 概述 == | == 概述 == | ||
'''选择排序''' | '''选择排序'''是一种简单直观的[[比较排序]]算法,其核心思想是:每次从未排序部分中选出最小(或最大)的元素,将其与未排序部分的起始位置交换,直到所有元素有序。该算法的时间复杂度为<math>O(n^2)</math>,适用于小规模数据或教学演示,但在实际应用中效率低于[[快速排序]]或[[归并排序]]等高级算法。 | ||
=== 算法特点 === | |||
* '''不稳定排序''':相同元素的相对位置可能改变(例如对<code>[5<sub>a</sub>, 2, 5<sub>b</sub>, 1]</code>排序后可能变为<code>[1, 2, 5<sub>b</sub>, 5<sub>a</sub>]</code>)。 | |||
* '''原地排序''':仅需<math>O(1)</math>额外空间。 | |||
* '''交换次数少''':最多进行<math>n-1</math>次交换,优于[[冒泡排序]]的<math>O(n^2)</math>次交换。 | |||
== 算法步骤 == | == 算法步骤 == | ||
选择排序的流程可分为以下步骤: | |||
# | # 从数组第1个元素开始,遍历未排序部分,找到最小元素的索引。 | ||
# | # 将最小元素与当前未排序部分的起始位置交换。 | ||
# | # 重复上述过程,每次未排序部分起始位置后移一位,直到数组完全有序。 | ||
<mermaid> | <mermaid> | ||
flowchart TD | |||
A[ | A[开始] --> B[初始化 i = 0] | ||
B --> C | B --> C{i < n-1?} | ||
C --> D[ | C -->|是| D[设置 min_idx = i] | ||
D --> E[ | D --> E[初始化 j = i+1] | ||
E --> F | E --> F{j < n?} | ||
F --> G[ | F -->|是| G{arr[j] < arr[min_idx]?} | ||
G --> | G -->|是| H[更新 min_idx = j] | ||
H --> I[ | G -->|否| I[无操作] | ||
H --> J[j++] | |||
I --> J | |||
J --> F | |||
F -->|否| K[交换 arr[i] 和 arr[min_idx]] | |||
K --> L[i++] | |||
L --> C | |||
C -->|否| M[结束] | |||
</mermaid> | </mermaid> | ||
== 代码实现 == | == 代码实现 == | ||
以下是[[Python]]、[[Java]]和[[C语言]]的实现示例: | |||
=== Python === | |||
<syntaxhighlight lang="python"> | <syntaxhighlight lang="python"> | ||
def selection_sort(arr): | def selection_sort(arr): | ||
n = len(arr) | n = len(arr) | ||
for i in range(n): | for i in range(n - 1): | ||
min_idx = i | |||
for j in range(i+1, n): | for j in range(i + 1, n): | ||
if arr[j] < arr[ | if arr[j] < arr[min_idx]: | ||
min_idx = j | |||
arr[i], arr[min_idx] = arr[min_idx], arr[i] | |||
arr[i], arr[ | |||
# 示例 | # 示例 | ||
data = [64, 25, 12, 22, 11] | |||
selection_sort(data) | |||
print("排序结果:", data) # 输出: [11, 12, 22, 25, 64] | |||
print(" | |||
</syntaxhighlight> | </syntaxhighlight> | ||
=== Java === | |||
< | <syntaxhighlight lang="java"> | ||
public class SelectionSort { | |||
void sort(int[] arr) { | |||
</ | int n = arr.length; | ||
for (int i = 0; i < n - 1; i++) { | |||
int minIdx = i; | |||
for (int j = i + 1; j < n; j++) { | |||
if (arr[j] < arr[minIdx]) { | |||
minIdx = j; | |||
} | |||
} | |||
int temp = arr[minIdx]; | |||
arr[minIdx] = arr[i]; | |||
arr[i] = temp; | |||
} | |||
} | |||
public static void main(String[] args) { | |||
int[] data = {64, 25, 12, 22, 11}; | |||
new SelectionSort().sort(data); | |||
System.out.println(Arrays.toString(data)); // 输出: [11, 12, 22, 25, 64] | |||
} | |||
} | |||
</syntaxhighlight> | |||
=== C语言 === | |||
<syntaxhighlight lang="c"> | |||
#include <stdio.h> | |||
void selectionSort(int arr[], int n) { | |||
for (int i = 0; i < n - 1; i++) { | |||
int min_idx = i; | |||
for (int j = i + 1; j < n; j++) { | |||
if (arr[j] < arr[min_idx]) { | |||
min_idx = j; | |||
} | |||
} | |||
int temp = arr[min_idx]; | |||
arr[min_idx] = arr[i]; | |||
arr[i] = temp; | |||
} | |||
} | |||
=== | int main() { | ||
int data[] = {64, 25, 12, 22, 11}; | |||
int size = sizeof(data) / sizeof(data[0]); | |||
selectionSort(data, size); | |||
for (int i = 0; i < size; i++) { | |||
printf("%d ", data[i]); // 输出: 11 12 22 25 64 | |||
} | |||
return 0; | |||
} | |||
</syntaxhighlight> | |||
== 复杂度分析 == | == 复杂度分析 == | ||
= | {| class="wikitable" | ||
|+ 选择排序的复杂度 | |||
! 情况 !! 时间复杂度 !! 说明 | |||
|- | |||
| 最优情况 || <math>O(n^2)</math> || 无论输入是否有序都需要完整比较 | |||
|- | |||
| 最差情况 || <math>O(n^2)</math> || | |||
|- | |||
| 平均情况 || <math>O(n^2)</math> || | |||
|- | |||
| 空间复杂度 || <math>O(1)</math> || 原地排序 | |||
|} | |||
== | == 实际应用场景 == | ||
* | 虽然选择排序效率不高,但在以下场景仍有应用价值: | ||
* '''嵌入式系统''':内存受限环境需要简单算法时。 | |||
* '''教学演示''':作为排序算法的入门示例。 | |||
* '''小规模数据''':当<math>n < 1000</math>时性能差异可忽略。 | |||
* '''交换成本高'''的场景(如对存储在磁盘的大对象排序)。 | |||
{{Warning|在需要'''稳定排序'''或处理大规模数据时,应优先考虑[[归并排序]]或[[快速排序]]。}} | |||
== | == 变体与优化 == | ||
=== 双向选择排序 === | |||
同时查找最小和最大元素,减少一半迭代次数: | |||
<syntaxhighlight lang="python"> | |||
def bidirectional_selection_sort(arr): | |||
left, right = 0, len(arr) - 1 | |||
while left < right: | |||
min_idx, max_idx = left, right | |||
for i in range(left, right + 1): | |||
if arr[i] < arr[min_idx]: | |||
min_idx = i | |||
elif arr[i] > arr[max_idx]: | |||
max_idx = i | |||
arr[left], arr[min_idx] = arr[min_idx], arr[left] | |||
if max_idx == left: # 防止最大值被交换到min_idx位置 | |||
max_idx = min_idx | |||
arr[right], arr[max_idx] = arr[max_idx], arr[right] | |||
left += 1 | |||
right -= 1 | |||
</syntaxhighlight> | |||
== | === 使用堆结构优化 === | ||
通过[[堆]]结构可将选择最小元素的时间从<math>O(n)</math>优化到<math>O(\log n)</math>,此时算法变为[[堆排序]],时间复杂度提升至<math>O(n \log n)</math>。 | |||
== 常见问题 == | |||
=== 为什么选择排序不稳定? === | |||
当最小元素与前方元素交换时,可能跨越中间相同元素。例如对<code>[3, 4, 3<sub>a</sub>, 2]</code>: | |||
# 第一轮交换3和2 → <code>[2, 4, 3<sub>a</sub>, 3]</code> | |||
# 此时两个3的相对顺序已改变。 | |||
== | === 选择排序和冒泡排序哪个更快? === | ||
虽然两者时间复杂度相同,但选择排序的交换次数恒为<math>O(n)</math>,而冒泡排序在最差情况下需要<math>O(n^2)</math>次交换。因此选择排序通常实际运行更快。 | |||
2 | |||
[[Category:计算机科学]] | [[Category:计算机科学]] | ||
[[Category: | [[Category:面试技巧]] | ||
[[Category:排序算法]] | [[Category:排序算法]] |
2025年5月12日 (一) 00:27的最新版本
概述[编辑 | 编辑源代码]
选择排序是一种简单直观的比较排序算法,其核心思想是:每次从未排序部分中选出最小(或最大)的元素,将其与未排序部分的起始位置交换,直到所有元素有序。该算法的时间复杂度为,适用于小规模数据或教学演示,但在实际应用中效率低于快速排序或归并排序等高级算法。
算法特点[编辑 | 编辑源代码]
- 不稳定排序:相同元素的相对位置可能改变(例如对
[5a, 2, 5b, 1]
排序后可能变为[1, 2, 5b, 5a]
)。 - 原地排序:仅需额外空间。
- 交换次数少:最多进行次交换,优于冒泡排序的次交换。
算法步骤[编辑 | 编辑源代码]
选择排序的流程可分为以下步骤:
- 从数组第1个元素开始,遍历未排序部分,找到最小元素的索引。
- 将最小元素与当前未排序部分的起始位置交换。
- 重复上述过程,每次未排序部分起始位置后移一位,直到数组完全有序。
代码实现[编辑 | 编辑源代码]
Python[编辑 | 编辑源代码]
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
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]
# 示例
data = [64, 25, 12, 22, 11]
selection_sort(data)
print("排序结果:", data) # 输出: [11, 12, 22, 25, 64]
Java[编辑 | 编辑源代码]
public class SelectionSort {
void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] data = {64, 25, 12, 22, 11};
new SelectionSort().sort(data);
System.out.println(Arrays.toString(data)); // 输出: [11, 12, 22, 25, 64]
}
}
C语言[编辑 | 编辑源代码]
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int data[] = {64, 25, 12, 22, 11};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
for (int i = 0; i < size; i++) {
printf("%d ", data[i]); // 输出: 11 12 22 25 64
}
return 0;
}
复杂度分析[编辑 | 编辑源代码]
情况 | 时间复杂度 | 说明 |
---|---|---|
最优情况 | 无论输入是否有序都需要完整比较 | |
最差情况 | ||
平均情况 | ||
空间复杂度 | 原地排序 |
实际应用场景[编辑 | 编辑源代码]
虽然选择排序效率不高,但在以下场景仍有应用价值:
- 嵌入式系统:内存受限环境需要简单算法时。
- 教学演示:作为排序算法的入门示例。
- 小规模数据:当时性能差异可忽略。
- 交换成本高的场景(如对存储在磁盘的大对象排序)。
页面模块:Message box/ambox.css没有内容。
变体与优化[编辑 | 编辑源代码]
双向选择排序[编辑 | 编辑源代码]
同时查找最小和最大元素,减少一半迭代次数:
def bidirectional_selection_sort(arr):
left, right = 0, len(arr) - 1
while left < right:
min_idx, max_idx = left, right
for i in range(left, right + 1):
if arr[i] < arr[min_idx]:
min_idx = i
elif arr[i] > arr[max_idx]:
max_idx = i
arr[left], arr[min_idx] = arr[min_idx], arr[left]
if max_idx == left: # 防止最大值被交换到min_idx位置
max_idx = min_idx
arr[right], arr[max_idx] = arr[max_idx], arr[right]
left += 1
right -= 1
使用堆结构优化[编辑 | 编辑源代码]
通过堆结构可将选择最小元素的时间从优化到,此时算法变为堆排序,时间复杂度提升至。
常见问题[编辑 | 编辑源代码]
为什么选择排序不稳定?[编辑 | 编辑源代码]
当最小元素与前方元素交换时,可能跨越中间相同元素。例如对[3, 4, 3a, 2]
:
- 第一轮交换3和2 →
[2, 4, 3a, 3]
- 此时两个3的相对顺序已改变。
选择排序和冒泡排序哪个更快?[编辑 | 编辑源代码]
虽然两者时间复杂度相同,但选择排序的交换次数恒为,而冒泡排序在最差情况下需要次交换。因此选择排序通常实际运行更快。