排序

插入排序：
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有
序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序
的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为⊙(㎡)。
是稳定的排序方法。
  插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，
但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到
此刻已是有序的第一部分里的正确位置中。
包括：直接插入排序，折半插入排序，链表插入排序，Shell排序


交换排序：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：
将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

选择排序：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，
直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。

归并排序：
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。
最简单的归并是直接将两个有序的子表合并成一个有序的表。 
在内部排序中，通常采用的是2-路归并排序。
即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。 
每一趟归并的时间复杂度为 O(n)

基数排序：
“基数排序法”（radix sort）则是属于“分配式排序”（distribution sort），
基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，
将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，
其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，
基数排序法的效率高于其它的比较性排序法。 
解法 
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），
LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

外排序：
若排序的文件存入外存储器排序过程借助内外存数据交换（或归并）来完成，则称这种排序为外排序。
一般地，外排序的时间由三部分组成：
(1) 预处理时间；
(2) 内部合并的时间；
(3) 外存读/写记录的时间。