【数据结构与算法】插入排序

记录一下插入排序。

public class InsertionSort {

    public static void sort(Integer[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        Integer value = null;
        Integer tempIndex = null;
        for (int i = 1; i < array.length; i++) {
            value = array[i];
            tempIndex = i - 1;

            while (tempIndex >= 0) {
                if (value < array[tempIndex]) {
                    /* 遍历有序序列，遇到比要插入的元素大的元素，则后移一位 */
                    array[tempIndex + 1] = array[tempIndex];
                    tempIndex--;
                } else {
                    /* 遍历有序序列，遇到比要插入的元素小的元素，可以停止了 */
                    break;
                }
            }

            array[tempIndex + 1] = value;
        }
    }

}

import org.junit.Test;


public class HowToTest {

    @Test
    public void c1() {
        Integer[] array = {3,16,1,5,2,18,0,9,20,11};
        InsertionSort.sort(array);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println();
    }

    @Test
    public void c2() {
        Integer[] array = {99,98,97,96,95,94,93,92,91,101,90,89,88,87,86,85};
        InsertionSort.sort(array);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println();
    }

}