为什么我的选择排序算法始终比我的插入排序更快？

“划分”是整数的一个随机生成的，最初是无序排列为什么我的选择排序算法始终比我的插入排序更快？

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); 
}

来源

2017-04-12 Dj Yoop

列表要排序多长时间？初始排序也会有所不同（反转排列看起来像是复杂性的一个特例，例如，在这种情况下纯粹的快速排序非常糟糕）。 – Richard

这完全是随机的。系统会提示用户输入他们想要的大小的整数值，例如2000或22399等，然后生成并存储一个随机列表，然后按照他们想要的算法进行排序。我更新了我的帖子，以显示我如何填充列表。 –

@Evk：选择排序在已经排序的数组上不会明显更快，因为它仍然必须进行所有的'（n^2 -n）/ 2'比较。它不做任何掉期交易，但没有早日退出。 –

你插入排序执行不够好。您在寻找元素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;

来源

2017-04-12 07:56:57 MBo

嗯。该代码给我一个OutOfBounds异常 –

我的错误，应该'排序[j] = P;' – MBo

啊，非常感谢。这似乎是诀窍。尽管如此，我仍然有点不确定。如果我必须为我的程序优化插入排序，这是否意味着我的选择排序算法已经优化？我认为我已经使用了这些算法的基本版本，所以我不确定为什么时间有这样的差异。 –

为什么我的选择排序算法始终比我的插入排序更快？

回答

相关问题