概念及介紹

插入排序(InsertionSort)，一般也被稱(chēng)為直接插入排序。
對(duì)于少量元素的排序，它是一個(gè)有效的算法。插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增 1 的有序表
。在其實(shí)現(xiàn)過(guò)程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)。

適用說(shuō)明

插入排序的平均時(shí)間復(fù)雜度也是 O(n^2)，空間復(fù)雜度為常數(shù)階 O(1)，具體時(shí)間復(fù)雜度和數(shù)組的有序性也是有關(guān)聯(lián)的。
插入排序中，當(dāng)待排序數(shù)組是有序時(shí)，是最優(yōu)的情況，只需當(dāng)前數(shù)跟前一個(gè)數(shù)比較一下就可以了，這時(shí)一共需要比較 N-1 次，時(shí)間復(fù)雜度為 O(N)。最壞的情況是待排序數(shù)組是逆序的，此時(shí)需要比較次數(shù)最多，最壞的情況是 O(n^2)。

算法思想

假設(shè)前面 n-1(其中 n>=2)個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)將第 n 個(gè)數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個(gè)數(shù)的這個(gè)序列也是排好順序的。
按照此法對(duì)所有元素進(jìn)行插入，直到整個(gè)序列排為有序的過(guò)程，稱(chēng)為插入排序。

我個(gè)人的理解的算法思想

前提：從前到后升序排列
1.選定第一個(gè)元素為最小元素
2.從最小元素的后邊相鄰的一個(gè)元素開(kāi)始往前遍歷元素，兩兩比較，如果后邊的元素小于前邊的元素，則相互交換位置，直到前邊的元素小于后邊的元素為止，停止內(nèi)層遍歷
3.外層遍歷重復(fù)步驟2，直到外層遍歷完成
（強(qiáng)烈建議學(xué)習(xí)的同學(xué)自己動(dòng)手畫(huà)圖，更易于理解）

分析流程圖

插入排序.png

java實(shí)現(xiàn)的代碼

/**
 * Author: 編程的貓 iCat
 * Emil: 15827348069@163.com
 * Date: 3/29/21 3:45 PM
 * Desc: 插入排序
 */
public class InsertSort {
    private static final String TAG = "InsertSort====>  ";

    public static void insertSort(int[] array) {

        for (int i = 0; i < array.length - 1; ++i) {
            for (int j = (i + 1); j > 0; --j) {
                if (array[j] < array[j - 1]) {
                    //后邊元素小于前邊的元素，交換位置
                    swap(array, (j - 1), j);
                } else {
                    //如果后邊的元素大于前邊的元素，跳出內(nèi)層循環(huán)
                    break;
                }
            }
        }
    }

    /**
     * 交換兩個(gè)元素的位置
     *
     * @param array 元素的數(shù)組
     * @param left  前邊元素的索引值
     * @param right 后邊元素的索引值
     */
    private static void swap(int[] array, int left, int right) {
        if (array != null && array.length > right) {
            int temp = array[left];

            array[left] = array[right];

            array[right] = temp;
        }
    }

    /**
     * 打印數(shù)組的元素
     *
     * @param array 數(shù)組
     */
    public static void printArrayElement(int[] array) {
        for (int i : array) {
            Log.d(TAG, "" + i);
        }
    }
}

C++代碼實(shí)現(xiàn)

// 插入排序思想
// 1.確定首位
// 2.從右邊相鄰的元素倒序往左遍歷比較大小，若左邊元素比右邊元素大則交換兩個(gè)元素的位置
// 3.重復(fù)步驟2，直到最后一個(gè)元素
void insertSort(int array[], int len) {
    for (int i = 0; i < (len - 1); ++i) {
        for (int j = i + 1; j > 0; --j) {
            //如果后邊的元素大于前邊的元素，兩個(gè)元素交換位置
            if (array[j] < array[j - 1]) { std::swap(array[j - 1], array[j]); }
            else
                //如果后邊的元素大于前邊的元素，跳轉(zhuǎn)內(nèi)層循環(huán)。因?yàn)槊恳惠喲h(huán)過(guò)后，前邊的元素都是已經(jīng)排好序的，這時(shí)候該元素大于前邊的所有元素
                break;
        }
    }
}

文中部分概念引用了菜鳥(niǎo)