自己动手写算法之插入排序

插入排序

算法步骤：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素a，在已经排序的元素序列中从后向前扫描
3.如果已排序中的元素b大于a，则将元素b后移一个位置
4.重复步骤3，直到找到已排序的元素x小于或者等于元素a
5.将元素a插入到x的后面
6.重复步骤2~5

public static void insertionSort(Integer[] array){
		for(int i=1;i<array.length;i++){
			//待插入的数据
			Integer toBeInsertedValue = array[i];
			int j;
			for(j=i;j>0;j--){
				if(array[j-1]>toBeInsertedValue){
					//将比toBeInsertedValue大的元素全部后移
					array[j]=array[j-1];
					continue;
				}
				break;
			}
			//插入新元素
			array[j]=toBeInsertedValue;
		}
	}

你这个感觉像冒泡排序法

这个跟冒泡排序有很大的不同，插入排序是用一个新元素插入一个已经排好序的序列中，
比较次数跟移动次数都是看具体情况的，在好的情况下该算法的时间复杂度是很低的，而冒泡排序的时间复杂度是n的平方级。

如：假设要插入的数总是大于已排序的序列，或者比较大，那么该算法的比较次数和移动次数就很低，只有在最坏的情况下才是n平方级

穿个马甲就不再是冒泡了
是全新的中国人的新发明,
伟大

你这个算法是很有没效率的，
尤其是插入小值，效率牺牲更大（原因比这个小值大得要移位，移位就发生按值拷贝，按值拷贝完后，虚拟机还要担负起待回收旧数据内存的工作）

一个比较好的做法是，将已排序好的数据集合，放到List中。
然后用二分找法分析已排序的集合（不是指List，在List中查找效率一样不高，因为不是连续内存的访问）定位并记录你要插入值的index（位置）。
例如：你将 arr[5]={43,553,4,23,5},作为参数传给二分查找，然后返回一组对应的index位置信息。
最后在List.inset();

这里是举例说明插入法的思想，当然真正应用插入法肯定要做优化，可以在如下两个方面进行优化：
1. 定位到要插入元素的位置
2. 进行移位操作

你说的二分查找只是优化了步骤1，当你执行步骤2的时候仍然要移位（数据结构为线性表实现插入排序的方式，移位操作是比较多的）

如果想减少移位操作，可以将排序集合设置成树形
一个比较好的实现是堆插入排序，有兴趣你可以去看看

感觉不错，最差是时间消耗是n*n，空间是多少呢，都忘记啦。
这个优化到底怎么优化呢，对于【移位操作】，链性表行不行？

链性表对移位操作来说效率是很高的，但是对于查询来说就很慢了，排序需要比较，那么查找的时候效率就低了，
而树是最好的解决这种问题的数据结构，我们对查找速度和移位效率都很在乎的话，就应该采用树结构

稍后我会写一个优化后的插入算法发布上来，大家一起讨论

减少空间移动是好的