排序算法 -- 插入排序

排序算法--插入排序

这个是我对插入排序的理解写的一个简单例子，可能和其他人的理解看法不同。
插入排序：

1，创建一个空的列表，用来保存排序后的列表，代号"有序列表"
2，从原列表中取出一个数，将其插入到"有序列表"，并使"有序列表"保持有序状态
3，重复第2步直到原列表末尾

这种排序的平均时间复杂度是平方级的，效率不高，容易实现

/**
 * InsertionSort.java
 * 
 * @author   xieyan
 * @date     2013/06/20
 * @version  1.0
 */
package sort;

import java.util.ArrayList;
import java.util.List;

/**
 * InsertionSort.java
 */
public class InsertionSort {

	/*
	 * 插入排序： 1，创建一个空的列表，用来保存排序后的列表，代号"有序列表"
	 * 2，从原列表中取出一个数，将其插入到"有序列表"，并使"有序列表"保持有序状态
	 * 3，重复第2步直到原列表末尾
	 * 
	 * 这种排序的平均时间复杂度是平方级的，效率不高，容易实现
	 */

	/**
	 * insertionSortAsc
	 * 
	 * <PRE>
	 * 升序
	 * </PRE>
	 * 
	 * @param arr
	 */
	public static List<Integer> insertionSortAsc(int[] arr) {
		if (arr == null) {
			return null;
		}

		List<Integer> result = new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			int obj = arr[i];
			if (i == 0) {
				result.add(obj);

			} else {
				for (int j = 0; j < result.size(); j++) {
					if (obj <= result.get(j)) {
						result.add(j, obj);
						break;
					}

					if (j == result.size() - 1) {
						result.add(obj);
						break;
					}
				}
			}
		}
		return result;
	}

	/**
	 * insertionSortAsc
	 * 
	 * <PRE>
	 * 降序
	 * </PRE>
	 * 
	 * @param arr
	 */
	public static List<Integer> insertionSortDesc(int[] arr) {
		if (arr == null) {
			return null;
		}

		List<Integer> result = new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			int obj = arr[i];
			if (i == 0) {
				result.add(obj);

			} else {
				for (int j = 0; j < result.size(); j++) {
					if (obj >= result.get(j)) {
						result.add(j, obj);
						break;
					}

					if (j == result.size() - 1) {
						result.add(obj);
						break;
					}
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 5, 7, 8, 3, 4, 2, 9, 1, 6 };

		List<Integer> b = insertionSortAsc(a);
		for (int i = 0; i < b.size(); i++) {
			System.out.println(b.get(i));
		}

		b = insertionSortDesc(a);
		for (int i = 0; i < b.size(); i++) {
			System.out.println(b.get(i));
		}
	}
}