简单介绍简单插入排序

简单插入排序：整个排序过程为n-1趟，第一个默认有序，从第二个开始逐个插入，直到整个序列有序。

1.简单实现代码

public class SimpleInsertSort {

    public static void main(String[] args){
        int[] a = {4,1,8,9,5};
        simpleInsertSort(a,a.length);

    }

    public static void simpleInsertSort(int a[], int len){
        int i;
        //i-1的位置
        int j;
        int curr;
        //1.默认第一个元素有序，从第二个开始
        for (i=1;i=0&&curr 
 
2.时间复杂度和空间复杂度
 

 T(n)=O(n²)
 

 S(n)=O(1)
 
 
 

 (1)如果是从小到大排序：那么比较次数为n-1次，移动次数2(n- 1) 
 

 (2)如果是从大到小排序，那么比较次数为（n+2）*（n-1）/2；移动次数：（n+4）*(n-1)/2
 

 (3)如果是乱序排序，随机排序，那么比较次数n*n/4;移动次数：n*n/4
 
 
 
  S(n)S(n)=O(1) =OS(n)=O(1) (1)