排序算法 - 插入排序

排序算法 -- 插入排序

排序算法--插入排序

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

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

?

?