插入排序

       排序算法是我们在编程过程中经常遇到的算法，所以，掌握常用的几种排序算法是非常必要的。今天我们看一下插入排序。

       所谓插入排序，就是将一个元素，按照相应的排列规则，插入到一个已经排好序的数组中，从而使这个新的数组也是排好序的。

       我们看一下插入排序的基本流程，如下面所示：

       初始数组：    [3]  8  5  6  7  4  9  2  1

       第一次插入： [3  8]  5  6  7  4  9  2  1

       第二次插入： [3  5  8]  6  7  4  9  2  1

       第三次插入： [3  5  6  8]  7  4  9  2  1

       第四次插入： [3  5  6  7  8]  4  9  2  1 

       第五次插入： [3  4  5  6  7  8]  9  2  1

       第六次插入： [3  4  5  6  7  8  9]  2  1

       第七次插入： [2  3  4  5  6  7  8  9]  1 

       第八次插入： [1  2  3  4  5  6  7  8  9]

       至此，排序过程完毕，数组已经成为一个排好序的数组。

       从上面的流程，大家可以看出，插入排序就是将前面的一个或者几个元素看成是一个排好序的数组，然后用后面的一个元素跟排好序数组中的元素进行比较，从而将元素插入到一个合适的位置。直到将所有的元素都插入排好序的数组中，排序过程完成。

       插入排序的java实现：
      

public class SortUtil {
	
	/**
	 * <p>
	 * 方法名:插入排序
	 * 方法说明：利用插入排序法，对数组进行排序，并返回排好序的数组。
	 * </p>
	 * @param array 待排序的数组
	 * @return 排好序的数组
	 */
    public static <T extends Comparable<T>> T[] insertionSort(T[] array) {
    	for (int i = 1; i < array.length; i++) {
    		T key = array[i];
    		int location = i;
    		for (int j = i - 1; j >= 0; j--) {
    			if (key.compareTo(array[j]) < 0) {
    				array[j + 1] = array[j];
    				location = j;
    			} else {
    				break;
    			}
    		}
    		
    		array[location] = key;    		
    	}
    	
    	return array;
    }
}

 
       测试代码：

   public static void main(String[] args) {
      Integer[] array1 = {3,8,5,6,7,4,9,2,1};
      Integer[] array2 = {1,2,3,4,5,6,7,8,9};
      Integer[] array3 = {9,8,7,6,5,4,3,2,1};
   
      System.out.println(Arrays.toString(SortUtil.insertionSort(array1)));
      System.out.println(Arrays.toString(SortUtil.insertionSort(array2)));
      System.out.println(Arrays.toString(SortUtil.insertionSort(array3)));
   }

 
       测试结果：

 

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]