插入排序的基本思想是：在一个已排好序的记录子集的基础上，一步一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排序记录全部插入为止。也就是说不断地将待排序的数值插入到有序段中，使有序段逐渐扩大，直至所有数值都进入有序段中位置。
       打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，知道抓完牌为止，即可得到一个有序序列。

直接插入排序

       直接插入排序是一种比较简单的排序方法。它的基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。
直接插入排序排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数 据较大时，直接插入排序的性能就不好，为此可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，从减少“比较关键词”和“移动记录”两种操作的次数着手来进行改进。

d0c8a786c9177f3eee69fa7e70cf3bc79f3d5667.jpg

希尔排序

       先选定一个元素的间隔数d，将整个元素序列按此间隔数从第一个元素开始分成若干个子序列，即分别将所有的间隔为d的元素为一个子序列，在各个子序列中进行排序；然后减少元素间隔数d,重新将整个序列按新的d分成若干个子序列，再分别对各个子序列进行排序；如此下去，知道间隔数d<1。

9f510fb30f2442a77555f25dd343ad4bd01302ea.jpg