深圳尚学堂Java培训:排序方法小结-插入排序

插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就是将数组第一个值看做有序的，从后每一个值放进来的时候，找放的位置。这里边就需要一些已经排好的数据可能会整体左移或者右移，所以用插入排序的算法也可以找到新数据存放到有序数组中的位置

用java代码实现：

public static void insertSort(int[] arr) {

//定义循环控制变量

int i, j;

//定义哨兵

int guard;

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

if (arr[i] < arr[i - 1]) {

guard = arr[i];

j = i - 1;

do {

arr[j + 1] = arr[j];

j--;

} while (j != -1 && guard < arr[j]);

arr[j + 1] = guard;

}

}

}