插入排序：

之前在学习插入排序时，在网上看到了一个直观的图解：

基本原理解释：

利用插入法对无序数组排序时，我们其实是将数组R划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。

插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区

增加1个记录，通常称增量法。

稳定 
空间复杂度O(1) 
时间复杂度O(n²) 
最差情况：反序，需要移动n*(n-1)/2个元素 
最好情况：正序，不需要移动元素

数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；

插入排序最坏情况运行时间和平均情况运行时间都为O(n²)。

根据自己的理解写了两个代码：

执行代码：

（1）

package sdx;
import java.util.Arrays;
public class Main8c {
public static void Main(int a[]){
int i,j,t,index;
for(i=1;i<a.length;i++){
index=a[i];
for(j=i-1;j>=0&&a[j]>index;j–){
a[j+1]=a[j];
a[j]=index;
}
}
}

public static void main(String[] args) {
Main8c ss=new Main8c();
int a[]={2,4,6,78,4,3,54,7,78,2,234234,6534,6,7,568,9,7354,635,8,56,};
ss.Main(a);
System.out.print(Arrays.toString(a)+” “);

}

}

理解：

1.写了一个静态方法，有一个数组作为参数

2.定义四个参数，其中index作为索引，

3.数组从a[1]开始，将a[0]设为左边的有序数组，所以i从1开始，此时默认左边的数组已经有序。

4.将右边数组的值赋值给index，用index去和左边的数组去比较。

5.因为i=数组下标1，所以，j的值是i左边的一位，所以j=i-1,但是j要在数组的长度之内，不能取左边小于0，所以j的下标要j>=0。
如果j的值比索引的值大，就将这个值向右移，然后将索引值重新赋值给a[j].这样就实现了数组的右移，将新的数据添加到左边的数组中去。

6.开始循环执行。。。。

7.测试类传值。

（2）

public void doInsertSort(){
for(int index = 1; index<length; index++){//外层向右的index，即作为比较对象的数据的index
int temp = array[index];//用作比较的数据
int leftindex = index-1;
while(leftindex>=0 && array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
array[leftindex+1] = array[leftindex];
leftindex–;
}
array[leftindex+1] = temp;//把temp放到空位上
}
}

public static void main(String[] args){
int[] array = {38,65,97,76,13,27,49};
InsertSort is = new InsertSort(array);
System.out.println(“排序前的数据为：”);
is.display();
is.doInsertSort();
System.out.println(“排序后的数据为：”);
is.display();
}
}