排序是计算机程序设计中的一种重要运算，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

内部排序：指的是待排序记录存放在计算机随机存储器（RAM）中进行的排序过程；
按排序原则分类：插入排序、交换排序、选择排序、归并排序、计数排序等五类。

按内排过程工作量区分：
简单的排序方法，时间复杂度；
先进排序方法，时间复杂度；
基数排序，时间复杂度；

排序过程中的两种基本操作：
1、比较两个关键字大小
2、将记录从一个位置移动至另一个位置。

待排序的记录序列存储方式有3种：
1、存放在地址连续的一组存储单元上，类似线性表的顺序存储结构。
2、链表排序：存放在静态链表中，记录之间的次序关系由指针指示。
3、地址排序：存放在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，排序时移动地址向量中记录的地址，排序后，按照向量中的值，调整存储地址。

插入排序

直接插入排序算法简便，且容易实现。简单讨论即可。
但是当待排序记录的数量很大时，我们可以从查找次数和移动次数中去改进算法，我们来看 折半插入排序是怎么做的。

折半插入排序：折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

代码举例：

性能分析：
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。

希尔排序

（缩小增量排序）
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

举例（图1）：

微信图片_20180502164926.png

49与13比较，38与27比较，65与49比较。。。
得到第一趟排序。
然后13、55、38、76一组，27、04,、65一组，49、49、97一组；
13、55、38、76得到13最小，38次之；
27、04,、65得到04最小，27次之；
49、49、97得到49最小；49次之；
得到第二趟排序。13、04、49与38、27、49与55、65、97最后一位76？
13与04，,04与49，49与38，38与27 ？？？

希尔排序说明图解（图2）:

希尔排序说明图.png

图1增量为：增量的计算为每次减2；5--3--1
图2的增量为：增量的计算为每次除2；10--5--2--1