插入排序（Java实现）

package unit_2;

/**
 * 插入排序算法采用增量模式，每次把第j个数插入有序的A[0...j-1]中 生成另外一个有序的数组。
 * 最佳情况复杂度：O(n)
 * 最坏情况复杂度：O(n^2)
 * @author WuNanliang
 *
 */
public class InsertSorted {

    public static void main(String[] args) {

        int arr[] = { 12, 33, 22, 1, 23, 2, 4, 5, 6, 77, 66, 55, 890 };
        insert_sort(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.print("\n");
        insert_sort_desc(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");

    }

    /**
     * 排序算法 降序
     * 
     * @param arr
     */
    private static void insert_sort_desc(int arr[]) {
        if (arr == null || arr.length == 0)
            return;
        int len = arr.length;
        int cursor = -1;
        int key = 0;
        for (int i = 1; i < len; i++) {
            cursor = i - 1;
            key = arr[i];
            while (cursor >= 0 && arr[cursor] < key) {
                arr[cursor + 1] = arr[cursor];
                cursor = cursor - 1;
            }
            arr[cursor + 1] = key;
        }
    }

    /**
     * 插入排序算法
     * 
     * @param arr
     */
    private static void insert_sort(int[] arr) {

        if (arr == null || arr.length == 0)
            return;
        int len = arr.length;
        int cursor = -1;
        for (int i = 1; i < len; i++) {
            int key = arr[i];
            cursor = i - 1;
            while (cursor >= 0 && arr[cursor] > key) {
                arr[cursor + 1] = arr[cursor];
                cursor = cursor - 1;
            }
            arr[cursor + 1] = key;
        }

    }

}