算法系列之选择排序算法

作者: 能不写代码么 | 来源:发表于2021-09-14 11:36 被阅读0次

    概述

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

    参考

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

    相关文章

      网友评论

        本文标题:算法系列之选择排序算法

        本文链接:https://www.haomeiwen.com/subject/cazfgltx.html