概述
工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序是一种灵巧的算法,但其速度不是很快:O(n²)
代码详解
- 找到最小的值,存放到循环中 i 索引所处的位置
- 重复上一个步骤 即可完成排序
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 转载请注明唯一出处 - 简书
/// 简书地址:https://www.jianshu.com/u/ab8f5ab027bd
/// 简书作者:SunnyShao
/// 创作时间:2021年9月14号
/// </summary>
public class SelectSortTest : MonoBehaviour
{
public List<int> arrays;
private void Awake()
{
SelectSort();
}
private void SelectSort()
{
int temp;
int smallestIndex = 0; //存储最小元素的索引
for (int i = 0; i < arrays.Count - 1; i++) //最后一个值不需要再进行比较,因为不存在 i+1 了
{
smallestIndex = i;
for (int j = i + 1; j < arrays.Count; j++) // i+1 代表索引之前是排序好的值,不用再次检测一遍了
{
if (arrays[j] < arrays[smallestIndex])
{
smallestIndex = j; //判断是否有更小的值,有的话赋值到索引上
}
}
temp = arrays[i];
arrays[i] = arrays[smallestIndex];
arrays[smallestIndex] = temp;
}
}
}
排序前
排序后
选择排序速度 O(n²) 的理解
随着选择排序的进行,每次需要检查的元素数(i+1)在逐渐减少,最后一次需要检查的元素都只有一个。既然如此,运行时间怎么还是O(n²)呢?这与大O表示法中的常数相关
确实并非每次都需要检查n个元素。第一次需要检查n个元素,但随后检查的元素数依次为n -1, n – 2, …, 2..,1。平均每次检查的元素数为1/2 × n,因此运行时间为O(n × 1/2 × n)。但大O表示法省略诸如1/2这样的常数,因此简单地写作O(n × n)或O(n²)
参考
《算法图解》(确实像小说一样有趣的算法书)
网友评论