插入排序

直接插入排序的基本思想：每次將一個(gè)待排序的記錄，按其keyword的大小插入到前面已經(jīng)排好的子序列中的適當(dāng)位置，直到所有記錄插入完畢為止。

假設(shè)數(shù)組為A[0...n-1]

1.初始時(shí)，A[0]自成1個(gè)有序區(qū),無序區(qū)為A[1....n-1]。令i = 1；

2.將A[i]并入當(dāng)前的有序區(qū)A[0...i-1]中形成A[0...i]的有序區(qū)間

3.i++并反復(fù)第二步直到i == n-1

至此排序完畢

代碼實(shí)現(xiàn)如圖:

插入排序

效率分析：

穩(wěn)定

空間復(fù)雜度O(1)

時(shí)間復(fù)雜度O(n2)

最差情況：反序。須要移動(dòng)n*(n-1)/2個(gè)元素

最好情況：正序，不須要移動(dòng)元素

數(shù)組已是排序或者接近順序。插入排序的效率最好的情況是O(n)，最壞的情況執(zhí)行時(shí)間和平均情況執(zhí)行時(shí)間均為O(n2)

通常插入排序呈現(xiàn)出二次排序算法中的最佳性能。

插入算法進(jìn)階---->希爾排序

希爾排序是根據(jù)插入排序來實(shí)現(xiàn)的。

希爾排序根據(jù)插入排序的以下兩點(diǎn)性質(zhì)而提出的改進(jìn)方法：

1.插入排序在對(duì)幾乎已經(jīng)順序排列的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。

2.插入排序一般說來是低效的。因?yàn)椴迦肱判驔]次數(shù)據(jù)只能移動(dòng)一位。

希爾排序算法利用了插入排序的簡單，同時(shí)又避免了插入排序每次交換數(shù)據(jù)只能消除一個(gè)逆序的缺點(diǎn)。所以希爾排序一般不是交換相鄰的元素，而是跳躍一段距離進(jìn)行交換。

算法思想：

希爾排序通過將整個(gè)待排序元素序列分成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成）分別直接進(jìn)行插入排序。然后依次縮減增量再次進(jìn)行排序，待整個(gè)序列中的元素基本有序，即增量足夠小時(shí)，再對(duì)全體進(jìn)行元素進(jìn)行一次直接插入排序。因?yàn)樽詈笠淮尾迦肱判蚴腔谟行蛐蛄械牟迦肱判?，效率是很高的。因此希爾排序在時(shí)間上是優(yōu)于直接插入排序的。

步長序列：

步長序列是希爾排序的核心部分。只要最終步長為1，任何步長序列都可以工作。算法最開始以一定的步長進(jìn)行排序。初次排序完畢之后，再次根據(jù)既定步長進(jìn)行排序。最終算法是以步長為1進(jìn)行排序。當(dāng)步長為1的時(shí)候，算法演變?yōu)椴迦肱判颉?/p>

時(shí)間、效率

最優(yōu)時(shí)間為O（n），不穩(wěn)定

java代碼：

java

iOS代碼：

iOS