直接插入排序算法（java）

直接插入排序是将未排序的数据插入至已排好序序列的合适位置。

　　具体流程如下：

　　1、首先比较数组的前两个数据，并排序；

　　2、比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；

　　3、比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；

　　 ......

　　4、直至把最后一个元素放入适当的位置。

空间效率：使用了常数个辅助单元，空间复杂度为O（1）

时间效率：最好情况下：表中元素已经有序，都只需比较一次而不用移动元素，时间复杂度情况是O（n）

最坏情况下：表中元素逆序，时间复杂度为n的平方。

稳定性：直接插入排序是一个稳定的算法。

适用性：直接插入算法适合顺序存储和链式存储。

public  int[] sort(int[] A){

   int tmp;

   int j;

   for(int i=1; i<A.length; i++){

        tmp = A[i];

        for(j=i-1; j>0; i--){

          if(tmp >=A[j]){

              break;

           }

           else{

              A[j+1] = A[j];           //注意：容易误写成A[j+1]=A[i];

           }

       }

       A[j+1] = tmp;

   }

    return A;

}

巴特西

直接插入排序算法（java）

最新文章

热门文章