跳转到内容

选择排序:修订间差异

来自代码酷
Admin留言 | 贡献
Page creation by admin bot
 
Admin留言 | 贡献
Page update by admin bot
 
第1行: 第1行:
{{Note|本条目介绍的是基础的比较排序算法——'''选择排序'''(Selection Sort)。本文将从算法思想、实现步骤、复杂度分析及实际应用等方面展开说明,适合初学者和需要复习的程序员。}}
{{Note|本条目讲解'''选择排序'''(Selection Sort)的基本原理、实现方法、复杂度分析及实际应用场景,适合编程初学者和需要复习基础算法的开发者。}}


== 概述 ==
== 概述 ==
'''选择排序'''是一种简单直观的排序算法,其核心思想是:'''每次从未排序部分选择最小(或最大)元素,放到已排序部分的末尾'''。该算法通过重复这一过程直到所有元素有序。由于其在最坏和平均情况下的时间复杂度均为<math>O(n^2)</math>,适用于小规模数据排序,但对大规模数据效率较低。
'''选择排序'''是一种简单直观的[[比较排序]]算法,其核心思想是:每次从未排序部分中选出最小(或最大)的元素,将其与未排序部分的起始位置交换,直到所有元素有序。该算法的时间复杂度为<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个元素开始,遍历未排序部分,找到最小元素的索引。
# 第<math>i</math>轮(<math>i</math>从0开始):
# 将最小元素与当前未排序部分的起始位置交换。
## 遍历未排序区,找到最小元素的索引<math>min\_index</math>。
# 重复上述过程,每次未排序部分起始位置后移一位,直到数组完全有序。
## 将未排序区的第一个元素与<math>min\_index</math>位置的元素交换。
## 此时前<math>i+1</math>个元素构成已排序区。
# 重复上述步骤,直到未排序区只剩一个元素。


=== 动态示例 ===
<mermaid>
<mermaid>
graph TD
flowchart TD
     A[初始数组: 64 25 12 22 11] --> B[第1轮: 选择11与64交换]
     A[开始] --> B[初始化 i = 0]
     B --> C[结果: 11 | 25 12 22 64]
     B --> C{i < n-1?}
     C --> D[第2轮: 选择12与25交换]
     C -->|是| D[设置 min_idx = i]
     D --> E[结果: 11 12 | 25 22 64]
     D --> E[初始化 j = i+1]
     E --> F[第3轮: 选择22与25交换]
     E --> F{j < n?}
     F --> G[结果: 11 12 22 | 25 64]
     F -->|是| G{arr[j] < arr[min_idx]?}
     G --> H[第4轮: 选择25(已在正确位置)]
    G -->|是| H[更新 min_idx = j]
     H --> I[最终排序结果: 11 12 22 25 64]
     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的实现示例:
以下是[[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_index = i
         min_idx = i
         for j in range(i+1, n):
         for j in range(i + 1, n):
             if arr[j] < arr[min_index]:
             if arr[j] < arr[min_idx]:
                 min_index = j
                 min_idx = j
        # 交换元素
         arr[i], arr[min_idx] = arr[min_idx], arr[i]
         arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


# 示例
# 示例
input_array = [64, 25, 12, 22, 11]
data = [64, 25, 12, 22, 11]
print("排序前:", input_array)
selection_sort(data)
output_array = selection_sort(input_array)
print("排序结果:", data) # 输出: [11, 12, 22, 25, 64]
print("排序后:", output_array)
</syntaxhighlight>
</syntaxhighlight>


'''输出结果:'''
=== Java ===
<pre>
<syntaxhighlight lang="java">
排序前: [64, 25, 12, 22, 11]
public class SelectionSort {
排序后: [11, 12, 22, 25, 64]
    void sort(int[] arr) {
</pre>
        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]);
* 每次交换后,已排序区长度增加1。
    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(n^2)</math> || 无论输入是否有序都需要完整比较
|-
| 最差情况 || <math>O(n^2)</math> ||
|-
| 平均情况 || <math>O(n^2)</math> ||
|-
| 空间复杂度 || <math>O(1)</math> || 原地排序
|}


=== 空间复杂度 ===
== 实际应用场景 ==
* 原地排序,仅需常数级额外空间:<math>O(1)</math>
虽然选择排序效率不高,但在以下场景仍有应用价值:
* '''嵌入式系统''':内存受限环境需要简单算法时。
* '''教学演示''':作为排序算法的入门示例。
* '''小规模数据''':当<math>n < 1000</math>时性能差异可忽略。
* '''交换成本高'''的场景(如对存储在磁盘的大对象排序)。


== 稳定性问题 ==
{{Warning|在需要'''稳定排序'''或处理大规模数据时,应优先考虑[[归并排序]]或[[快速排序]]。}}
选择排序是'''不稳定'''的排序算法。例如对数组<code>[3a, 2, 3b, 1]</code>(其中3a和3b值相同)排序时:
# 第1轮:1与3a交换 → <code>[1, 2, 3b, 3a]</code>
# 第2轮:2已在正确位置
# 第3轮:3b与自身交换
最终结果中3a和3b的相对顺序改变。


== 优化方向 ==
== 变体与优化 ==
* '''双向选择排序''':同时查找最小值和最大值,减少交换次数。
=== 双向选择排序 ===
* '''堆排序''':利用堆结构优化选择过程,时间复杂度可降至<math>O(n \log n)</math>
同时查找最小和最大元素,减少一半迭代次数:
<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>
# '''小规模数据''':代码简单,常数项小。
# '''内存受限环境''':原地排序特性。
# '''需要最少交换次数''':严格最多<math>n-1</math>次交换(优于冒泡排序)。


{{Note|与其他排序算法的对比:}}
== 常见问题 ==
* 比'''冒泡排序'''更高效(减少交换次数)。
=== 为什么选择排序不稳定? ===
* 比'''插入排序'''更适用于元素移动成本高的场景(如链表排序)。
当最小元素与前方元素交换时,可能跨越中间相同元素。例如对<code>[3, 4, 3<sub>a</sub>, 2]</code>:
# 第一轮交换3和2 → <code>[2, 4, 3<sub>a</sub>, 3]</code>
# 此时两个3的相对顺序已改变。


== 练习建议 ==
=== 选择排序和冒泡排序哪个更快? ===
1. 尝试用选择排序降序排列数组。
虽然两者时间复杂度相同,但选择排序的交换次数恒为<math>O(n)</math>,而冒泡排序在最差情况下需要<math>O(n^2)</math>次交换。因此选择排序通常实际运行更快。
2. 实现双向选择排序版本。
3. 分析选择排序在链表结构上的适用性。


[[Category:计算机科学]]
[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:面试技巧]]
[[Category:排序算法]]
[[Category:排序算法]]

2025年5月12日 (一) 00:27的最新版本

模板:Note

概述[编辑 | 编辑源代码]

选择排序是一种简单直观的比较排序算法,其核心思想是:每次从未排序部分中选出最小(或最大)的元素,将其与未排序部分的起始位置交换,直到所有元素有序。该算法的时间复杂度为O(n2),适用于小规模数据或教学演示,但在实际应用中效率低于快速排序归并排序等高级算法。

算法特点[编辑 | 编辑源代码]

  • 不稳定排序:相同元素的相对位置可能改变(例如对[5a, 2, 5b, 1]排序后可能变为[1, 2, 5b, 5a])。
  • 原地排序:仅需O(1)额外空间。
  • 交换次数少:最多进行n1次交换,优于冒泡排序O(n2)次交换。

算法步骤[编辑 | 编辑源代码]

选择排序的流程可分为以下步骤:

  1. 从数组第1个元素开始,遍历未排序部分,找到最小元素的索引。
  2. 将最小元素与当前未排序部分的起始位置交换。
  3. 重复上述过程,每次未排序部分起始位置后移一位,直到数组完全有序。

flowchart TD A[开始] --> B[初始化 i = 0] B --> C{i < n-1?} C -->|是| D[设置 min_idx = i] D --> E[初始化 j = i+1] E --> F{j < n?} F -->|是| G{arr[j] < arr[min_idx]?} G -->|是| H[更新 min_idx = j] G -->|否| I[无操作] H --> J[j++] I --> J J --> F F -->|否| K[交换 arr[i] 和 arr[min_idx]] K --> L[i++] L --> C C -->|否| M[结束]

代码实现[编辑 | 编辑源代码]

以下是PythonJavaC语言的实现示例:

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;
}

复杂度分析[编辑 | 编辑源代码]

选择排序的复杂度
情况 时间复杂度 说明
最优情况 O(n2) 无论输入是否有序都需要完整比较
最差情况 O(n2)
平均情况 O(n2)
空间复杂度 O(1) 原地排序

实际应用场景[编辑 | 编辑源代码]

虽然选择排序效率不高,但在以下场景仍有应用价值:

  • 嵌入式系统:内存受限环境需要简单算法时。
  • 教学演示:作为排序算法的入门示例。
  • 小规模数据:当n<1000时性能差异可忽略。
  • 交换成本高的场景(如对存储在磁盘的大对象排序)。

页面模块: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

使用堆结构优化[编辑 | 编辑源代码]

通过结构可将选择最小元素的时间从O(n)优化到O(logn),此时算法变为堆排序,时间复杂度提升至O(nlogn)

常见问题[编辑 | 编辑源代码]

为什么选择排序不稳定?[编辑 | 编辑源代码]

当最小元素与前方元素交换时,可能跨越中间相同元素。例如对[3, 4, 3a, 2]

  1. 第一轮交换3和2 → [2, 4, 3a, 3]
  2. 此时两个3的相对顺序已改变。

选择排序和冒泡排序哪个更快?[编辑 | 编辑源代码]

虽然两者时间复杂度相同,但选择排序的交换次数恒为O(n),而冒泡排序在最差情况下需要O(n2)次交换。因此选择排序通常实际运行更快。