插入排序算法

插入排序算法

思想

• 我们以从小到大的排序进行讲解
• 插入排序就是将一个元素插入到一个已经是有序的序列中， 通过遍历比较这个待插入元素和有序的序列元素之间的大小，来比较需要插入的位置，使其仍然是一个有序的数组。
• 数组插入的算法：向后移动元素给待插入的数据位置

详解

• 第一趟：假设我们需要排序的数组大小为n，一般的思想是先假设第一个元素是有序的，即是已经排序好的，那么第二个元素此时就是待插入的元素，我们拿这个待插入的元素和第一个元素比较大小，如果小的话，那么就将其插入到第一个元素的前面，此时待插入元素就变成了第一个，如果大于的话，就不需要改变位置。那么此时这个数组的前两个元素就是有序的
• 第二趟： 经过第一趟的，前面两个元素已经是有序的，那么此时的第三个元素就是待插入元素，这个待插入元素先和第二个元素进行比较，如果大于的话，那么就不需要再和第一个元素比较了，当前位置不用改变就可以维持前面三个元素是有序的。如果是小于的话，此时的第二个元素就需要向后移动位置，因为这里可以肯定的是这个待插入元素一定是在其前面插入的，具体的位置没有确定而已。第二个元素向后移动之后，那么此时就需要和第一个元素比较，如果大于的话，那么就插在第一个和第二个元素之间成为当前数组的第二个元素即可，如果小于的话，那么就插入到第一个元素之前，同样的是第一个元素要向后移动为其腾出位置。
• 第三趟…………………………………第n-1趟

算法分析

• 平均时间复杂度：O(n2)
• 空间复杂度：O(1) (用于记录需要插入的数据)
• 稳定性：稳定

算法实现 — java

• 需要注意的是判断条件一定是j>=0&&insertNode<array[j]，因为如果调换顺序的话，那么会造成数组下标越界

/*
* 这个是从小到大的插入排序
* @Param array  待排序的数组
*/
public static void insertSort(int[] array){
	//我们假设第一个元素已经是有序的，因此从第二个开始遍历，总共需要遍历n-1次
	for (int i = 1; i < array.length; i++) {
		
		int insertNode=array[i];  //这个就是待插入的数，需要和在之前的元素比较
		
		int j=i-1;   //这个的初始值是待插入数字的前一个数字
		
		//如果待插入的数字比前面的元素小并且此时的j没有到达第一个元素(j>=0)
		//循环结束的条件是insertNode>=array[j],那么此时的insertNode需要插入的位置就是array[j+1]这个位置了
		//需要注意的是&&是短路与的判断，因此需要将j>=0放在前面，否则如果是insertNode<array[j]&&j>=0的形式，那么当j=-1的时候就会造成下标数组越界
		while(j>=0&&insertNode<array[j]){
			array[j+1]=array[j];  //元素后移，以便插入   
			j--;   //比较的元素的下标此时需要前移，和待插入的数据进行比较
		}
		array[j+1]=insertNode;  //这个位置就是待插入元素需要插入的位置
	}
}