C#实现选择排序与插入排序：代码、原理与性能对比

using System;

public class Selection : BaseSort
{
    public static long usedTimes = 0;
    public Selection()
    {
    }

    public static void Sort(IComparable[] a)
    {
        Stopwatch timer = new Stopwatch();
        timer.Start();

        // 外层循环控制已排序区的边界
        for (var i = 0; i < a.Length - 1; i++)
        {
            int minIndex = i;
            // 内层循环寻找未排序区中的最小值索引
            for (var j = i + 1; j < a.Length; j++)
            {
                if (Less(a[j], a[minIndex]))
                {
                    minIndex = j;
                }
            }

            // 如果找到的最小值不是当前起始位置，则交换
            if (minIndex != i)
            {
                Exch(a, minIndex, i);
            }
        }

        timer.Stop();
        usedTimes = timer.ElapsedMilliseconds;
    }

    // 辅助方法：比较大小
    private static bool Less(IComparable v, IComparable w)
    {
        return v.CompareTo(w) < 0;
    }

    // 辅助方法：交换元素
    private static void Exch(IComparable[] a, int i, int j)
    {
        IComparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

// 假设 BaseSort 包含基础工具类，此处仅为结构示意
public abstract class BaseSort
{
    protected static bool Less(IComparable v, IComparable w) { throw new NotImplementedException(); }
    protected static void Exch(IComparable[] a, int i, int j) { throw new NotImplementedException(); }
}

using System;

public class Insertion : BaseSort
{
    public static long usedTimes = 0;

    public static void Sort(IComparable[] a)
    {
        Stopwatch timer = new Stopwatch();
        timer.Start();

        /*
         * 方式一：直接交换法
         * 逻辑简单，类似冒泡排序的思想，但只向右移动一步。
         * 缺点是频繁访问数组，开销较大。
         */
        for (var i = 1; i < a.Length; i++)
        {
            for (var j = i; j > 0 && Less(a[j], a[j - 1]); j--)
            {
                Exch(a, j, j - 1);
            }
        }

        /*
         * 方式二：位移优化法（推荐）
         * 将当前元素暂存到临时变量 temp，然后将其左侧较大的元素全部右移一位，
         * 最后将 temp 放入正确位置。减少了大量的数组写入操作。
         */
        // int N = a.Length;
        // for (int i = 1; i < N; i++)
        // {
        //     IComparable temp = a[i];
        //     int j;
        //     // 寻找插入位置并右移元素
        //     for (j = i - 1; j >= 0 && Less(temp, a[j]); j--)
        //     {
        //         a[j + 1] = a[j];
        //     }
        //     // 放置临时变量到正确位置
        //     a[j + 1] = temp;
        // }

        timer.Stop();
        usedTimes = timer.ElapsedMilliseconds;
    }
}

// 同样需要 Less 和 Exch 辅助方法，若选用方式二可省略 Exch