簡單排序算法之插入排序

插入排序

        插入排序的代碼實作雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易了解的了，因為隻要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直覺的排序算法，它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。

1. 算法步驟

        将第一待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。從頭到尾依次掃描未排序序列，将掃描到的每個元素插入有序序列的适當位置中（如果待插入的元素與有序序列中的某個元素相等，則将待插入元素插入到相等元素的後面）。

// 插入排序
    //-----------------------------------------------------------
    public static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1] > temp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
    
    //-----------------------------------------------------------
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            E temp = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }