Preface: The original idea of falling in love with Java has never been forgotten: "Sharing my learning results, no matter how deep the later technology is, it is important to lay a good foundation."
Tool class Swapper, this tool class will be used in later algorithms:
Copy the code code as follows:
package com.meritit.sortord.util;
/**
* One util to swap tow element of Array
*
* @author ysjian
* @version 1.0
* @email [email protected]
* @QQ 646633781
* @telephone 18192235667
* @csdnBlog http://blog.csdn.net/ysjian_pingcx
* @createTime 2013-12-20
* @copyRight Merit
*/
public class Swapper {
privateSwapper() {
}
/**
* Swap tow elements of the array
*
* @param oneIndex
* one index
* @param anotherIndex
* another index
* @param array
* the array to be swapped
* @exception NullPointerException
* if the array is null
*/
public static <T extends Comparable<T>> void swap(int oneIndex,
int anotherIndex, T[] array) {
if (array == null) {
throw new NullPointerException("null value input");
}
checkIndexs(oneIndex, anotherIndex, array.length);
T temp = array[oneIndex];
array[oneIndex] = array[anotherIndex];
array[anotherIndex] = temp;
}
/**
* Swap tow elements of the array
*
* @param oneIndex
* one index
* @param anotherIndex
* another index
* @param array
* the array to be swapped
* @exception NullPointerException
* if the array is null
*/
public static void swap(int oneIndex, int anotherIndex, int[] array) {
if (array == null) {
throw new NullPointerException("null value input");
}
checkIndexs(oneIndex, anotherIndex, array.length);
int temp = array[oneIndex];
array[oneIndex] = array[anotherIndex];
array[anotherIndex] = temp;
}
/**
* Check the index whether it is in the arrange
*
* @param oneIndex
* one index
* @param anotherIndex
* another index
* @param arrayLength
* the length of the Array
* @exception IllegalArgumentException
* if the index is out of the range
*/
private static void checkIndexs(int oneIndex, int anotherIndex,
int arrayLength) {
if (oneIndex < 0 || anotherIndex < 0 || oneIndex >= arrayLength
|| anotherIndex >= arrayLength) {
throw new IllegalArgumentException(
"illegalArguments for tow indexes [" + oneIndex + ","
+ oneIndex + "]");
}
}
}
Direct insertion sort, InsertionSortord:
Copy the code code as follows:
package com.meritit.sortord.insertion;
/**
* Insertion sort order, time complexity is O(n2)
*
* @author ysjian
* @version 1.0
* @email [email protected]
* @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 begins 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;
}
}
}
}
}
Test TestInsertionSortord:
Copy the code code as follows:
package com.meritit.sortord.insertion;
import java.util.Arrays;
/**
* Test insertion sort order
*
* @author ysjian
* @version 1.0
* @email [email protected]
* @QQ 646633781
* @telephone 18192235667
* @createTime 2013-12-31
* @copyRight Merit
*/
public class TestInsertionSortord {
public static void main(String[] args) {
InsertionSortord insertSort = InsertionSortord.getInstance();
int[] array = { 3, 5, 4, 2, 6 };
System.out.println(Arrays.toString(array));
insertSort.doSort(array);
System.out.println(Arrays.toString(array));
System.out.println("---------------");
Integer[] array1 = { 3, 5, 4, 2, 6 };
System.out.println(Arrays.toString(array1));
insertSort.doSortT(array1);
System.out.println(Arrays.toString(array1));
}
}