×
文章路径: Java > 算法 > 排序

插入排序InsertionSort

发表于3年前(Dec 24, 2014 9:56:10 AM)  阅读 479  评论 0

分类: Java 算法 排序

标签: insertionsort sort 排序 插入排序

插入排序是排序算法中很简单的一种排序,适用于少量元素排序。对他的描述,《算法导论》一书中的例子我觉得很形象。插入排序的算法原理类似于打牌中的摸牌:没摸牌时,我们手中是空的,接着,一次摸一张牌,每次摸起时,我们按照大小把它排列,无论什么时候,我们手中的牌都是已排好序的。

在实现时,我们使用两个数组,数组A用来模拟待摸的牌,数组B用来模拟我们自己手上抓的牌,每次我们从A中取一张牌插到B中,不管什么时候,B中的牌都是排好序的。

package sort;

/**
 * 插入排序
 * @author lihui
 *
 */
public class InsertionSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		int[] a = {2,5,3,4,1,0};
		int[] a = {5,3,1,1,3,0,2};
		sorted(a);
		for(int i=0;i<a.length;i++) {
			System.out.println(a[i]);
		}
	}

	public static void sorted(int[] a) {
		//从数组第二个元素开始做排序
		for(int i=1;i<a.length;i++) {
			//当前要插入的数作为key
			int key = a[i];
			int j = i;
			//如果当前要插入大于已排序的数组的最后一个,则直接插在后面,
			//否则跟数组最后一个数字比较,直到找到比key小的,或到数组最前
			if(key>=a[j-1]) {
				a[j] = key;
			} else {
				while(j>0&&key<a[j-1]) {
					int temp = a[j-1];
					a[j-1] = key;
					a[j] = temp;
					j--;
				}
			}
		}
	}

}
插入排序是可以在原数组上实现的,时间复杂度为O(n2)。

发表评论