很早之前，为了应付数据结构考试。花了一星期多看了数据结构，当时觉得也没什么难的。
过了老久，总算是招报应了，做笔试题发现其实所有理解只是在表面，实际上我并不会实现，确实是这样，学术这东西真没捷径，还是要沉下心来才能有所见解。
看了清华慕课上邓老师的数据结构，决定自己跟着他的接口实现一下，于是也开始学c++，学了点语法，然后就开始实现了，说实话，真难。刚好今天写插入排序算法，所以也就记下来。
其实这是很简单的算法
好吧，废话不多说，插入排序，就是有一堆乱序的数据，如果要排好顺序，除了最直观的我们人最喜欢的选择排序外，应该就是插入排序了，从递归思路开始想，在排序过程中，一般我们都是分成排好的那一堆和还没排好的那一堆，我们在排序过程中，从没有排好的里面拿出最前面那个，然后找到排好那一堆里面的一个适当的位置，使得插入以后排好那一堆依然是有序的，于是排好的会一直增加，未排好的也会一直减退。保证了算法的有穷性。从迭代的思路当然是一开始，拿最开始那个，随便找个地方放上去，然后拿出下一个，比较如果大，就放在它后面，依次类推。
我c++的实现是这样的：
template<typename T> void List<T>::insertionSort(Posi(T) p, int n) { Posi(T) runner = p; p = p->next; for (int i = 1; i < n; i++) { int j = i+1; while (j-- > 0) { if ((p->data)>(runner->data)||p==header) { Posi(T) temp = p->next; this->insertAsNext(p, runner); runner = temp->pred; p = temp; break; } else { runner = runner->pred; } } } }
我相信直接看，肯定有疑问，首先，我这个方法是链表LIst类的一个保护成员，Posi(T)是这样的：
#define Posi(T) ListNode<T>*
每个链表节点，邓老师用了链表节点部件，我的接口声明当然是取至邓老师的教材。（这里有必要提一下）
我想算法并没有什么好说的，但是我在定义这个算法的过程中，遇到了点问题，其实一开始我的while循环是这样的：
if ((p->data)<(runner->data)) { runner = runner->pred; } else { Posi(T) temp = p->next; this->insertAsNext(p, runner); runner = temp->pred; p = temp; break; }
其实是一样的，但是有个漏洞就是，如果，准备插入的元素如果是有序部分的最小，那么它会比较到有序序列的前一个，在这个链表类里应该是header哨兵，隐患很显而易见，在这个情况下是无法正常排序的。
所以我考虑了两种解决方案：
if ((p->data)<(runner->data)&&p!=header) { runner = runner->pred; } else { Posi(T) temp = p->next; this->insertAsNext(p, runner); runner = temp->pred; p = temp; break; }
和我决定下一种：
if ((p->data)>(runner->data)||p==header) { Posi(T) temp = p->next; this->insertAsNext(p, runner); runner = temp->pred; p = temp; break; } else { runner = runner->pred; }
之后看了邓老师的实现方法：
天啊，竟然忘记接口定义的search函数。罪过罪过，太水了。
好吧那我定义一下search
template<typename T> Posi(T) List<T>::search(T const& e, int n, Posi(T) p) const { while (n-->0) { p = p->pred; if (p->data <= e) { return p; } } return header; }
书上版本：
