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