算法思路
可以把插入排序想象成撲克中的插牌股缸，步驟如下：
- 手中的牌永遠(yuǎn)是從小到大排序好的
- 新抽到的牌會(huì)放在手牌的最右側(cè)
- 然后將新抽到的牌與其左側(cè)的牌進(jìn)行比較瘸彤，如果小于左側(cè)的牌則與其互換位置
- 重復(fù)上一步驟，直到新抽的牌大于其左側(cè)的牌為止
- 重新抽取一張新牌放在手牌的最右側(cè)烂琴，重復(fù)以上步驟，直到抽完所有牌為止
應(yīng)用在實(shí)際的數(shù)組中，步驟如下（假設(shè)數(shù)組a中含有n個(gè)元素）：
- 在最開始時(shí)佑颇，
a[0]可以看做為已經(jīng)排序好的手牌 -
a[1]為新抽的手牌 - 比較
a[0]和a[1]，如果a[0] > a[1]草娜，互換位置 - 此時(shí)挑胸，
a[0] ~ a[1]為已經(jīng)排序好的手牌 -
a[2]為新抽的手牌 -
a[2]先于a[1]比較，如果小于a[1]宰闰，則互換位置茬贵；a[2]繼續(xù)和a[0]比較，如果小于a[0]移袍，則互換位置解藻。以上步驟如果a[2]大于與其比較的元素，則立即停止 - 重復(fù)以上步驟葡盗，直到遍歷完整個(gè)數(shù)組
代碼
從上面的例子可以看出螟左，插入排序需要兩個(gè)指針進(jìn)行循環(huán)：
- 指針1：永遠(yuǎn)指向新抽的手牌，即觅够，需要排序的元素的位置胶背。并依次向右循環(huán)指針。
- 指針2：永遠(yuǎn)指已排序好的元素的最末位置喘先。并依次向左循環(huán)與指針1進(jìn)行比較钳吟。
- 因?yàn)槟J(rèn)
a[0]為已經(jīng)排序好的手牌，所以指針1應(yīng)該從索引1的位置開始遍歷
insertion(int[] a)
{
int N = a.length;
for (int i = 1; i < N; i++) { // 指針1從索引位置1開始窘拯，向右遍歷
for (int j = i; j > 0 && (a[j] < a[j - 1]); j--) { // j-1為指針1上一元素红且，依次向左遍歷
exch(a, j, j - 1); // 互換位置
}
}
}
時(shí)間&空間
- 空間：因?yàn)橹苯釉谠瓟?shù)組中進(jìn)行排序操作坝茎，無需額外的空間，空間復(fù)雜度為O(1)
- 時(shí)間：最壞情況下暇番，時(shí)間復(fù)雜度為~O(N2/2)
-
證明：
插入排序的最壞情況為將一個(gè)倒序排序的數(shù)組排列為一個(gè)正序排序的數(shù)組景东。以上面的手牌例子來講，即每次抽到的新手牌小于所有已排序好的手牌奔誓。因?yàn)樾鲁榈氖峙菩枰来闻c前面排序好的每一張手牌進(jìn)行比較和互換斤吐。
以上例子可以寫作為一個(gè)長(zhǎng)度為
N的數(shù)組a = {n, n-1, n-2, n-3, ... 3, 2, 1}，n為數(shù)組中最大的元素厨喂。如果將這個(gè)數(shù)組進(jìn)行排序：0. {n, n-1, n-2, n-3, ... 3, 2, 1} // 原數(shù)組 1. {n-1, n, n-2, n-3, ... 3, 2, 1} // 1次操作 2. {n-2, n-1, n, n-3, ... 3, 2, 1} // 2次操作 3. {n-3, n-2, n-1, n, ... 3, 2, 1} // 3次操作 ... n. {1, 2, 3, ... n-3, n-2, n-1, n} // n-1次操作 操作和： 1 + 2 + 3 + ... + (n-3) + (n-2) + (n-1) = (n-1) * ((n-1)+1) / 2 = n(n-1)/2 ~ n^2/2
-
