type
status
date
slug
summary
tags
category
icon
password
整理定义
出处 | 定义 |
一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素有序。 | |
复述展开
选择排序(selection sort)
- 稳定性:不稳定
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
- 排序方式:in-place
选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选择最小(或最大)的元素,放到已排序序列的末尾,直到所有元素都排序完成。
选择排序的步骤如下:
- 遍历待排序序列,将第一个元素设为当前最小(或最大)元素。
- 从剩余的未排序元素中找到最小(或最大)的元素,与当前最小(或最大)元素进行交换。
- 将当前最小(或最大)元素放到已排序序列的末尾。
- 重复步骤2和步骤3,直到所有元素都排序完成。
选择排序的特点是每次选择最小(或最大)元素放到已排序序列的末尾,因此每一轮选择排序都会确定一个元素的最终位置。选择排序的时间复杂度为O(n^2),其中n是待排序序列的长度。尽管选择排序的时间复杂度较高,但它的实现简单,对于小规模的数据集仍然是一个有效的排序算法。
需要注意的是,选择排序是一种不稳定的排序算法,即相等元素的相对顺序可能会发生改变。如果需要稳定的排序算法,可以考虑其他算法,如插入排序或归并排序。
动态图展示
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fdea38628-64dc-40fd-8d17-2efa87e3d554%2Fa7b6d6e6-20ca-443d-9ddb-822e6dc636ab%2F%25E9%2580%2589%25E6%258B%25A9%25E6%258E%2592%25E5%25BA%258F_%25E5%258E%258B%25E7%25BC%25A9.gif?table=block&id=18721969-0723-4514-b5fc-b1993cc3c111&t=18721969-0723-4514-b5fc-b1993cc3c111&width=419&cache=v2)
代码演示
理解体会
首先,选择排序是一种简单但有效的排序算法。它的基本思想是每次从待排序的元素中选择最小(或最大)的元素,将其放置在已排序序列的末尾,逐步构建有序序列。选择排序的过程可以分为两个子操作:选择和交换。
选择排序的优点是实现简单,代码量少,不需要额外的空间。它适用于小规模的数据集,对于简单的排序任务是一个有效的选择。此外,选择排序是一种不稳定的排序算法。当存在相等元素时,选择排序可能会改变它们的相对顺序。这是因为选择排序每次选择最小(或最大)元素进行交换,可能会导致相等元素的位置发生变化。
总结来说,选择排序是一种简单但有效的排序算法。它通过选择和交换操作逐步构建有序序列。尽管选择排序的时间复杂度较高且不稳定,但在小规模数据集上仍然是一个可行的排序算法。对于理解排序算法的基本原理和实现细节,选择排序是一个很好的起点。
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/industry-day19
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。