一、排序思想
我们可以假想出两个容器,一个容器中是待排序的元素,一个是空容器。每次从容器中取出一个元素(一般是第一个),然后插入空容器中,而插入空容器时必须按大小顺序,找到合适位置,这个过程就是插入排序。
当我用c方式实现时,发现插入排序居然与冒泡排序神奇般的相似,这是我始料未及的。而且他们的时间复杂度都是O(n^2)。老子说:“此二者同出而异名”,莫非它们背后的排序思想竟是一致的么?
又或者如《系辞传》所说:“天下同归而殊途,一致而百虑。”两种排序算法,到最后竟走上殊途同归的道路,恰如“西下夕阳东上月,一般花影有寒温”,花影还是那个花影,只是一个是太阳照出来的,一个是月亮照出来的,一个觉得寒一些,一个觉得暖一些吧。
二、插入图示
三、代码示例
c版本
1 void swap(int * a, int * b) 2 { 3 int tmp = *a; 4 *a = *b; 5 *b = tmp; 6 } 7 8 void insertSort(int * a, int len) 9 { //from begin to end, find a number in order and insert it to the right place 10 //sorted number is added, unsored number is decreased 11 for(int i = 0; i < len - 1; ++i) 12 { 13 for(int j = i; j >= 0; --j) 14 { 15 if(*(a+j) > *(a + j + 1)) 16 { 17 swap(a + j, a + j + 1); 18 } 19 } 20 } 21 }
c++ 版
1 template<typename T> 2 inline void InsertSort(std::list<T> & source) 3 { 4 //should push at least one element 5 //the we can compare elements between two list 6 std::list<T> tmp; 7 tmp.push_back(*source.begin()); 8 while() 9 { 10 auto it = tmp.begin(); 11 for(; it != tmp.end(); ++it) 12 { 13 if(*source.begin() <= *it) 14 { 15 tmp.insert(it, *source.begin()); 16 source.pop_front(); 17 break; 18 } 19 } 20 //the insert motion will not invalid this iterator 21 //this condition happens when *source.begin() is the largest element 22 if(it == tmp.end()) 23 { 24 tmp.push_back(*source.begin()); 25 source.pop_front(); 26 } 27 } 28 source.assign(tmp.begin(), tmp.end()); 29 }
四、算法结语
子夏说:“虽小道,必有可观者焉”。这个排序算法只是浩如烟海的算法系统中的极小部分,然而仔细揣摩,也必然会有所收获。插入排序体现了一种打破旧体制,实现新秩序的思想,正所谓不破不立,推而演之,难道不能用在治家、治国等大的方面吗?
他接着说:“致远恐泥,是以君子不为也。”写代码终究属于小技能吧,希望自己能够走得更高更远,不要只是陷在代码中间!
丙申年立春笔
原文:http://www.cnblogs.com/renzhenxuexi/p/5175964.html