Java直接插入排序算法源码

package com.meritit.sortord.insertion; /** * Insertion sort order, time complexity is O(n2) * * @author ysjian * @version 1.0 * @email ysjian_pingcx@126.com * @QQ 646633781 * @telephone 18192235667 * @csdnBlog http://blog.csdn.net/ysjian_pingcx * @createTime 2013-12-31 * @copyRight Merit * @since 1.5 */ public class InsertionSortord { private static final InsertionSortord INSTANCE = new InsertionSortord(); private InsertionSortord() { } /** * Get the instance of InsertionSortord, only just one instance * * @return the only instance */ public static InsertionSortord getInstance() { return INSTANCE; } /** * Sort the array of <code>int</code> with insertion sort order * * @param array * the array of int */ public void doSort(int... array) { if (array != null && array.length > 0) { int length = array.length; // the circulation begin at 1,the value of index 0 is reference for (int i = 1; i < length; i++) { if (array[i] < array[i - 1]) { // if value at index i is lower than the value at index i-1 int vacancy = i; // record the vacancy as i // set a sentry as the value at index i int sentry = array[i]; // key circulation ,from index i-1 , for (int j = i - 1; j >= 0; j--) { if (array[j] > sentry) { /* * if the current index value exceeds the * sentry,then move backwards, set record the new * vacancy as j */ array[j + 1] = array[j]; vacancy = j; } } // set the sentry to the new vacancy array[vacancy] = sentry; } } } } /** * Sort the array of generic <code>T</code> with insertion sort order * * @param array * the array of generic */ public <T extends Comparable<T>> void doSortT(T[] array) { if (array != null && array.length > 0) { int length = array.length; for (int i = 1; i < length; i++) { if (array[i].compareTo(array[i - 1]) < 0) { T sentry = array[i]; int vacancy = i; for (int j = i - 1; j >= 0; j--) { if (array[j].compareTo(sentry) > 0) { array[j + 1] = array[j]; vacancy = j; } } array[vacancy] = sentry; } } } } }