关于插入排序和选择排序的比较_选择排序与插入排序

作者：在线问答5 | 2024-07-24 23:43:43

踩

选择排序与插入排序

写这篇文章，是笔者在看面试题的时候，复习到了排序。各种排序名称想必让大家难以记忆，因此当我在对比插入排序和选择排序差异的时候，我发现二者结构非常相似，于是想对比一下二者排序的效率。

复杂度公式如下：

那么观察该复杂度公式得出已下结论：

从比较次数来看：序列越有序则插入排序所需比较次数越少；而选择排序比较次数恒为N*（N-1）/2次。

从赋值情况来看：在相同比较次数下(也就是最坏情况下)，选择排序比插入排序和改进插入排序赋值次数少。

因此，对于改进插入排序和选择排序的比较，不能笼统的说谁快，而是要根据具体情况的。取决于序列的有序程度。

<——(有序程度)

|——————————————————|

改进插入排序选择排序

下面附上java源码和测试情况：