算法-排序算法：选择排序O(n^2)【当遍历到第3个元素时，则排序后第3个元素肯定是全局排名第3的元素】、插入排序O(n^2)【当遍历到第3个元素时，则排序后第3个元素是前3个元素中排名第3的元素】

柔情只为你懂 2023-10-04 12:26 6阅读 0赞

#### **选择排序、插入排序虽然时间复杂度为 O ( n 2 ) O(n^2) O(n2)，在 “小规模数据集” 上速度比归并排序快**。 ####

## 一、选择排序（Selection Sort） O ( n 2 ) O(n^2) O(n2) ##

> **选择排序**（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

> 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

### 1、选择排序-算法描述： ###

*  先把最小的拿出来；
 *  剩下的，再把最小的拿出来；
 *  剩下的，再把最小的拿出来；
 *  …
 *  每次选择还没处理的所有元素里最小的元素

n n n 个记录的直接选择排序可经过  n − 1 n-1 n−1 趟直接选择排序得到有序结果。具体算法描述如下：

*  初始状态：无序区为 R \[ 1.. n \] R\[1..n\] R\[1..n\]，有序区为空；
 *  第  i i i 趟排序 ( i = 1 , 2 , 3 … n − 1 ) (i=1,2,3…n-1) (i=1,2,3…n−1)开始时，当前有序区和无序区分别为 R \[ 1.. i − 1 \] R\[1..i-1\] R\[1..i−1\]和 R ( i . . n ) R(i..n) R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录  R \[ k \] R\[k\] R\[k\]，将它与无序区的第  1 1 1 个记录  R R R 交换，使  R \[ 1.. i \] R\[1..i\] R\[1..i\] 和  R \[ i + 1.. n ) R\[i+1..n) R\[i\+1..n) 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
 *  n-1趟结束，数组有序化了。

### 2、选择排序-时间复杂度 ###

*  最优时间复杂度：  O ( n 2 ) O(n^2) O(n2)
 *  最坏时间复杂度：  O ( n 2 ) O(n^2) O(n2)
 *  稳定性：不稳定（考虑升序每次选择最大的情况）

### 3、选择排序-过程分析 ###

全部排序过程（原地排序）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]

### 4、选择排序-动图演示 ###

![在这里插入图片描述][2020102700130524.gif_pic_center]  
![在这里插入图片描述][20210430161458526.gif_pic_center]

### 5、选择排序-代码实现 ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201027000718345.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[2020102700130524.gif_pic_center]: https://img-blog.csdnimg.cn/2020102700130524.gif#pic_center
[20210430161458526.gif_pic_center]: https://img-blog.csdnimg.cn/20210430161458526.gif#pic_center