算法系列之选择排序算法

概述

工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序是一种灵巧的算法，但其速度不是很快：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²)

参考

《算法图解》（确实像小说一样有趣的算法书）