算法起步之插入排序

原文:算法起步之插入排序

        趁着过年这段时间，我将算法导论这本书看了一遍，感觉受益匪浅。着这里也根据算法导论中所涉及到的算法用java实现了一遍。

        第一篇我们就从排序开始，插入排序的原理很简单，就像我们玩扑克牌时一样。如果手里拿的牌比他前一张小，就继续向前比较，知道这张牌比他前面的牌打时候就可以插在他的后面。当然在计算机中我们相应的也需要将对比过的牌向后移一位才可以。

        这里直接给出算法，相信很多程序员都感觉有些程序比我们的自然语言都要好理解。

public class Sort {
	public void sort(int[] s){
		if(s.length<1){
			return ;
		}
		for (int i = 1; i < s.length; i++) {
			int key =s[i];
			int j=i-1;
			while(j>=0&&s[j]>key){
				s[j+1]=s[j];
				j--;
			}
			s[j+1]=key;
		}
	}
	public static void main(String[] args) {
		Sort s=new Sort();
		int[] st =new int[]{7,5,3,4,2,1};
		s.sort(st);
		for (int i = 0; i < st.length; i++) {
			System.out.println(st[i]);
		}
	}
}

          他的时间复杂度是o（n*n），是原址的（任何时候都需要常数个二外的元素空间存储数据而归并排序就是非原址的）

         友情提示：转载请注明出处【作者：idlear  博客：http://blog.csdn.net/idlear】