排序算法之插入排序

插入排序：
1.插入排序的复杂度是O(n^2)，四大基础排序算法之一，八大基本排序算法之一
2.插入排序的原理：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。

3.代码实现：

package cn.ycl.dataStructures.sort;
import java.util.Arrays;
public class insertSort {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[] = { 45, 1, 34, 23, 12, 90, -1 };
		insertSort.insert(array);
		System.out.println(Arrays.toString(array));
	}
	public static void insert(int array[]) {
		for (int i = 0; i < array.length; i++) {
			// 将要插入的值赋给一个不变的变量，使得后面可以改变array[i],而保留array[i]原来的值
			int insertVal = array[i];
			int insertIndex = i - 1;
                       //insertIndex>=0是为了让insertIndex不越界，不能出现array[-1]的情况
			while (insertIndex >= 0 && insertVal < array[insertIndex]) {
				array[insertIndex + 1] = array[insertIndex];
				insertIndex--;
			}
			if (insertIndex + 1 != i) {
				array[insertIndex + 1] = insertVal;
			}
		}
	}
}

我是“道祖且长”，一个在互联网苟且偷生的Java程序员