详细总结各种排序算法(Java实现)-创新互联

一、插入类排序

1.直接插入排序

思想：将第i个插入到前i-1个中的适当位置

时间复杂度：T(n) = O(n²)。

空间复杂度：S(n) = O(1)。

稳定性：稳定排序。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定

哨兵有两个作用：

① 进人查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容；

② 它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")

public void insertSort(int[] array){
  for(int i=1;i=0 && temp            

            网站标题：详细总结各种排序算法(Java实现)-创新互联            

            链接地址：http://cxhlcq.com/article/ddsodo.html