今天仍然是O(n^2)級(jí)別的排序算法劫哼，插入排序。思路也很簡(jiǎn)單割笙，就是對(duì)每一個(gè)元素权烧，在其前所有已經(jīng)排序的元素中，查找一個(gè)合適的位置伤溉，將該元素放在那個(gè)位置上般码。
實(shí)現(xiàn)上，我們將當(dāng)前元素依次與其前面的元素進(jìn)行比較乱顾，如果前面的元素比當(dāng)前元素大板祝，則交換這兩個(gè)元素，直到某個(gè)位置走净，前面的元素比當(dāng)前元素小券时，則已完成排序孤里。
template<typename T>
void insertSort(T a[], int n) {
for(int i = 1; i < n; ++i) {
for(int j = i; j > 0 && a[j] < a[j-1]; --j) {
swap(a[j], a[j-1]);
}
}
}
與第一課的選擇排序相比，該算法存在提前退出的可能性橘洞，就是說(shuō)捌袜，如果當(dāng)前元素已經(jīng)找到了合適的位置，就不再需要繼續(xù)與更前面的元素進(jìn)行比較了震檩。這對(duì)于一個(gè)基本有序的數(shù)組來(lái)說(shuō)琢蛤，會(huì)是一個(gè)比較大的性能改進(jìn)。因此抛虏，插入排序在實(shí)際應(yīng)用中也往往非常有用博其，甚至比其他O(nlgn)的算法的性能表現(xiàn)更好。
但是迂猴，上面的實(shí)現(xiàn)方法還存在一個(gè)問(wèn)題慕淡，就是內(nèi)層循環(huán)中一直在做兩個(gè)元素之間的交換操作(swap)，而這個(gè)操作本身的開(kāi)銷也不低沸毁。標(biāo)準(zhǔn)的swap函數(shù)的實(shí)現(xiàn)如下：
template<typename T>
void swap(T &a, T &b) {
T temp(a);
a = b;
b = temp;
}
可見(jiàn)峰髓，swap包含了一個(gè)copy構(gòu)造函數(shù)和兩個(gè)賦值，這往往不能滿足我們對(duì)性能的需求息尺。因此携兵，我們對(duì)插入排序的實(shí)現(xiàn)進(jìn)行優(yōu)化：
template<typename T>
void insertSort2(T a[], int n) {
for(int i = 1; i < n; ++i) {
T tmp = a[i];
int j;
for(j = i; j > 0 && a[j-1] > tmp; --j) {
a[j] = a[j-1];
}
a[j] = tmp;
}
}
我們將swap操作替換成賦值操作以優(yōu)化swap造成的開(kāi)銷。
