排序算法 -- 插入排序

排序算法--插入排序

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

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));
		}
	}
}

 

 

评论

3 楼 xieyan30 2013-08-12  

gzzjsoft 写道

研究了一下，才明白为什么你死活都要使用List的原因，add(int,obj)确实很方便

是的，这个只是介绍下原理，具体问题就看自己如何解决了。
谢谢。

2 楼 gzzjsoft 2013-08-11  

研究了一下，才明白为什么你死活都要使用List的原因，add(int,obj)确实很方便

1 楼 gzzjsoft 2013-08-11  

package sort;


public class InsertionSort {

	public static int[] insertionSortAsc(int[] arr) {
		
		if (arr == null || arr.length == 0) {
			return null;
		}
		
		int[] targetArray = new int[arr.length];
		targetArray[0] = arr[0];
		
		for(int i = 1; i < arr.length; i++){
			int j = i - 1;
			while(j >= 0 && targetArray[j] > arr[i]){
				targetArray[j+1] = targetArray[j];
				j--;
			}
			targetArray[j+1] = arr[i];
		}
		
		return targetArray;
	}

	public static int[] insertionSortDesc(int[] arr) {
		
		if (arr == null || arr.length == 0) {
			return null;
		}
		
		int[] targetArray = new int[arr.length];
		targetArray[0] = arr[0];
		
		for(int i = 1; i < arr.length; i++){
			int j = i - 1;
			while(j >= 0 && targetArray[j] < arr[i]){
				targetArray[j+1] = targetArray[j];
				j--;
			}
			targetArray[j+1] = arr[i];
		}
		
		return targetArray;
	}

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

		int[] b = insertionSortAsc(a);
		for (int i = 0; i < b.length; i++) {
			System.out.print(b[i] + "  ");
		}
		System.out.println();
		b = insertionSortDesc(a);
		for (int i = 0; i < b.length; i++) {
			System.out.print(b[i] + "  ");
		}
	}
}