选择排序：简单选择排序（不稳定）

【 选择排序的基本思想】 ：每一趟在 n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第 i 个记录。

【 算法思想】
第 1 趟简单选择排序时，从第 1 个记录开始，通过 n-1 次关键字的比较，从
n 个记录中选出关键字最小的记录，并和第 1 个记录进行交换。
第 2 趟简单选择排序时，从第 2 个记录开始，通过 n-2 次关键字的比较，从
n-1 个记录中选出关键字最小的记录，并和第 2 个记录进行交换。
……
第 i 趟简单选择排序时，从第 i 个记录开始，通过 n-i 次关键字的比较，从
n-i+1 个记录中选出关键字最小的记录，并和第 i 个记录进行交换。
如此反复，经过 n-1 趟简单选择排序，将把 n-1 个记录排到位，剩下一个最
小记录直接在最后，所以共需进行 n-1 趟简单选择排序。

图示：

简单选择排序

自定义工具类：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 自定义工具类
/// </summary>
public static class Utilit
{
    /// <summary>
    /// 辅助输出排序结果：
    /// </summary>
    /// <param name="a"></param>
    /// <param name="t"></param>
    public static void Print(int[] a, int t)
    {
        string str = null;
        for (int i = 0; i < a.Length; i++)
        {
            str += a[i].ToString() + " ";
        }
        Debug.Log("第" + t + "趟排序结果：" + str);
    }

    /// <summary>
    /// 辅助生成排序结果
    /// </summary>
    /// <param name="max"></param>
    /// <param name="length"></param>
    /// <returns></returns>
    public static int[] RandArray(int max, int length)
    {
        string str = null;
        int[] a = new int[length];
        for (int i = 0; i < a.Length; ++i)
        {
            a[i] = Random.Range(0, max);
            str += a[i].ToString() + " ";
        }
        Debug.Log("随机生成的数组：" + str);
        return a;
    }
}

简单选择排序：

// <summary>
/// 选择类排序
/// </summary>
public class SelectSort
{
    /// <summary>
    ///1、 简单选择排序
    /// </summary>
    /// <param name="a"></param>
    public static void SampleSelectSort(int[] a)
    {
        int len = a.Length;//获得数组长度
        
        for(int i=0;i<len-1;i++)
        {

            int minIndex = i;
            int minValue = a[i];
            for (int j = i + 1; j < len; j++) //找后方最小值的位置与值
            {
                if (a[j] < minValue) //(改为 > 则为降序)
                {
                    minValue = a[j];
                    minIndex = j;
                }
            }

            if (minIndex != i)
            {
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
            
            Utilit.Print(a, i);
        }
    }


    /// <summary>
    /// 错误的简单选择排序
    /// </summary>
    /// <param name="a"></param>
    public static void ErrorSampleSelectSort(int[] a)
    {
        int len = a.Length;//获得数组长度

        for (int i = 0; i < len - 1; i++)
        {

            for (int j = i + 1; j < len; j++) 
            {
                if (a[j] < a[i]) //每次把比较小的放到了最前方，并非把最小的找到，而且是不稳定排序
                {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
            
            Utilit.Print(a, i);
        }
    }
}

测试用例：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class _013_SelectSort : MonoBehaviour {

    
    void Start ()
    {
        int[] a = Utilit.RandArray(20, 10);

        int[] b = (int[])a.Clone();

        Debug.Log("-------------正确简单选择排序--------------");
        SelectSort.SampleSelectSort(a);
        
        Debug.Log("-------------错误简单选择排序--------------");
        SelectSort.ErrorSampleSelectSort(b);

    }
    
}

输出结果：

img.jpg

注：

【 算法分析 】 在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序
记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即第一个记录最大，其余记录从小到大有序排列，此时移动记录的次数最多，为 3（n-1）次。
简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当 i=1 时，需进行 n-1 次比较；当 i=2 时，需进行 n-2 次比较；依次类推，共需要进行的比较次数是 n(n-1)/2，即进行比较操作的时间复杂度为O(n ^2 )。

image.png