为什么我的选择排序算法总是比插入排序快？

Question

“排序”是一个随机生成的、最初未排序的整数数组。

private void insertion_Click(object sender, EventArgs e)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for(int i = 1; i < Sorted.Length; i++)
    {
        int j = i;
        while(j>0 && Sorted[j-1] > Sorted[j])
        {
            swap(Sorted, j - 1, j);
            j -= 1;
        }
    }
    sw.Stop();

    IsSorted = true;
    UpdateButtons(IsSorted);
    MessageBox.Show($"Insertion sort took {(sw.ElapsedMilliseconds).ToString()} milliseconds", "Insertion sort");
}


//Selection sort
private void selection_Click(object sender, EventArgs e)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for(int i = 0; i < Sorted.Length-1; i++)
    {
        int CurrMinIndex = i;
        for(int j = i; j < Sorted.Length; j++)
        {
            if(Sorted[j] < Sorted[CurrMinIndex])
            {
                CurrMinIndex = j;
            }
        }

        if(CurrMinIndex != i)
        {
            swap(Sorted, CurrMinIndex, i);
        }
    }
    sw.Stop();

    IsSorted = true;
    UpdateButtons(IsSorted);
    MessageBox.Show($"Selection sort took {(sw.ElapsedMilliseconds).ToString()} milliseconds", "Selection Sort");
}

我正在设计一个C# WPF应用程序，它对随机生成的列表进行排序，然后以毫秒为单位输出完成所需的时间。我知道插入排序应该比选择排序更好，但我的结果告诉我并非如此。我甚至一次都没有看到插入排序的时间接近选择排序。事实上，我的选择排序算法似乎始终是速度的两倍！有人看到这里的问题了吗？我以为我已经完成了这两种算法的一些相当通用的形式，但是我是不是不小心优化了呢？

编辑:下面是我用来填充列表的算法：

Sorted = new int[ListSize];  //initialize/populate unsorted array
Random Rand = new Random();
for (int i = 0; i < ListSize; i++)
{
     Sorted[i] = Rand.Next(-1000, 1000);
}

Answer 1

插入排序实现不够好。在寻找元素P的位置时进行完全交换，但只需记住P，将较大的元素向上移动(半交换？)，然后插入P。

     int j = i;
     int P = Sorted[j];
     while(j>0 && Sorted[j-1] > P)
        {
            Sorted[j] = Sorted [j-1];
            j--;
        };
    Sorted[j] = P;