排序在所有数据结构中我认为实际使用频率最大之一，并且看似简单，好像都会用，但实际上在合适地方使用合适的排序方式并不简单，并且是其他很多解决问题模型的基础；最近工作过程中实现一个消息总线，过程要解决消息分发时搜索消息效率问题，发现以前学习的数据结构大都已经还回去了，于是抽空好好再学习一下，并且总结出来供后续偶尔再回顾以及改善其中的理解；

    排序整体而言分为：内部排序和外部排序；内部排序是指排序过程使用的空间都是内存空间；而外部排序是指由于排序元素太多，排序过程使用的空间只有一部分使用内存空间，其余使用的是外设空间；

    下面我们先来了解一下内部排序；内部排序分为插入排序、交换排序、选择排序、基数排序、归并排序五种类型的排序方法；

    而插入排序是各位牌友最熟悉也是每次牌友抓牌的时候使用的技能——每次抓牌的时候手中的牌都是有序的，抓一张牌上来，逐一与手中牌比较，然后插入到合适的位置，直到所有的牌都抓完的时候，手里的牌都是有序的了。这其实就是我们的直接插入排序——在对记录序列R[1..n]的排序过程中，区段R[1..i-1]中的记录已按关键字非递减的顺序排列，将 R[i] 插入到有序序列 R[1..i-1] 中，使区段 R[1..i] 中的记录按关键字非递减顺序排列；直接插入排序优点就是简单，占用空间小；缺点是比较次数和移动次数太依赖要排序的集合元素；

    为了提高效率，我们在直接插入基础上从比较、移动、空间三个角度出发得到了半折插入排序、2路插入排序、表插入排序、希尔插入排序；

    首先我们先从比较次数入手，于是我们有了半折插入排序，简单讲就是比较的时候我们不一个个去比较，我们直接与中间元素比较，一下子就淘汰一半的元素不需要比较了，按照这个规则一直比较，最终找到插入位置；以前直接插入一个元素比较级别是O(n)级别，现在直接变成了O(log以2为底n的对数了)级别；

    比较次数有了很大改善；但是移动次数没有改变，有些元素是个结构体，占用内存大，移动一次的时间消耗比比较的时间消耗大多了，于是我们得减少移动的时间消耗，有了二路插入排序；比较简单的做法就是我们拷贝一份R[1..n]的空间D[1..n]，R[1]赋值到D[1],从R[2]开始对D[1..n]中有序列表使用二分法查询插入位置，插入到D[1]左边[D[n]]或者右边D[2]，这样确实减少了移动次数，但是增加了一倍的空间，并且减少的移动次数不是特别明显，还有提升空间；

    为了节省空间和提高移动效率，我们又有了表插入排序，其根本思想就是以前以顺序存储变角度出发，现在以链式存储角度出发，每个元素都增加一个next指，得到插入位置后，只需要修改插入元素和插入元素前面元素的next值；这个排序无疑无需移动，但是查询插入位置的效率和直接插入的效率一样了，并且还多了一个next的存储空间；

    那么我们有没有一个综合提高比较、移动、空间效率的排序方式，于是希尔排序又称缩小增量排序诞生了；它的基本思想是，先对待排序列进行"宏观调整"，待序列中的记录"基本有序"时再进行直接插入排序；其基本思想是将带排序的记录按照增量d划分为几组，然后对每组进行插入排序；依次对增量d进行缩小，然后进行插入排序，直到d为1，然后进行最优插入排序；这样对比较、移动、空间效率方面有综合的提高，这个提高的程度取决于d的划分；

    经过这几个插入排序的了解，发现其实每种插入排序都有其存在的价值，我们需要针对具体情况选择具体的插入排序；比如元素集合顺序差别不大的情况我们适合选择直接插入排序；如果对比较效率要求比较高，则选择半折插入排序；如果对比较、移动要求高但是对空间要求不高，则使用二路插入排序；如果对移动、空间要求高，对比较要求不高，则使用表插入排序；如果对比较、移动、空间都有要求，则选择希尔排序。

排序——了解总体以及插入排序