Java直接插入排序算法实现

序：一个爱上java最初的想法一直没有磨灭：”分享我的学习成果，不管后期技术有多深，打好基础很重要“。

工具类swapper，后期算法会使用这个工具类：

package com.meritit.sortord.util;

/**
 * one util to swap tow element of array
 *
 * @author ysjian
 * @version 1.0
 * @email [e-mail]
 * @qq 646633781
 * @telephone [phone]
 * @csdnblog http://blog.csdn.net/ysjian_pingcx
 * @createtime 2013-12-20
 * @copyright merit
 */
public class swapper {

 private swapper() {

 }

 /**
  * 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 indexs [" + oneindex + ","
       + oneindex + "]");
  }
 }
}

直接插入排序，insertionsortord：

package com.meritit.sortord.insertion;

/**
 * insertion sort order, time complexity is o(n2)
 *
 * @author ysjian
 * @version 1.0
 * @email [e-mail]
 * @qq 646633781
 * @telephone [phone]
 * @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;
    }
   }
  }
 }
}

测试testinsertionsortord：

package com.meritit.sortord.insertion;

import java.util.arrays;

/**
 * test insertion sort order
 *
 * @author ysjian
 * @version 1.0
 * @email [e-mail]
 * @qq 646633781
 * @telephone [phone]
 * @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));
 }
}