插入排序详解：直接插入排序与希尔排序及性能对比
一、常见排序算法分类
常见的排序算法有八种，我们简单盘点一下：
- 插入排序：直接插入排序、希尔排序
- 选择排序：直接选择排序、堆排序
- 交换排序：冒泡排序、快排
- 计数排序
以上就是我们常用的八大排序算法，我们会在后面的排序算法部分为大家一一介绍。今天我们要介绍的就是插入排序这一大类。
二、直接插入排序
我们先来简单地介绍一下直接插入排序的思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
在我们玩扑克牌时，拿到牌后首先就是对牌进行排序。我们会将已经排好序的牌放在左手边，然后右边就是我们等待排序的牌。随后我们会将右边没有排好序的牌依次去插入到已经有序的牌中。如上图，2,4,5,10 就是一组已经排好序的牌，而 7 我们就可以看作是我们打牌时放在右边的还未排序的牌。我们想把 7 排好序，就只需要将 7 插入到 5 和 10 的中间，其它牌不变。
这也正是我们直接插入排序的算法思想，将所有的数据分成两部分，左边就是已经排好序的数据，右边则是待排序数据。随后我们将右边待排序的数一个一个插入到有序的数据中，直到最后一个数据插入完成，所有数据也就有序了。
现在问题的关键就是，在最开始时我们所有的数据都是乱序，怎么才能将它划分成左右两部分？实际上很简单，只要我们把第一个数据看作一个有序的序列即可，这样左右两部分就被划分出来了。
这样我们就将最开始的数据划分成了两部分，左边只有一个数据，可以看作是有序的，右边是乱序的、待排序的数据。接下来我们要做的就是如何将右边一个一个的元素依次插入到左边的有序序列中。
这也是我们直接插入排序的重点。上面我们讲解了直接插入排序的原理，接下来我们就开始介绍直接插入排序的具体实现，我们以升序为例讲解。
首先我们可以创建一个变量 end 作为左边有序序列中的最后一个数据。在最开始时，end 就在第一个位置上，因为第一个元素就是有序的序列的最后一个数据。随后我们要做的就是将第二个元素插入到这个有序序列。
方法就是，记录下来 end+1 位置的数据，因为 end 是左边有序的序列的最后一个数据，那么 end+1 自然就是右边待排序序列的第一个数据。我们要将 end+1 这个位置的数据插入到左边的有序序列中，首先就是将它用变量 tmp 记录下来，它就是我们要往左边有效序列中插入的数据。
接下来我们就开始比较 end 位置的数据和 tmp 这个数据，看看 end 位置的数据是否比 tmp 更大。如果更大，说明我们的 tmp 要往 end 位置的左边插入数据，于是我们就可以让 end 位置的数据往后挪动一下。
此时就可以看到，我们成功将右边的一个数据插入了到左边的有序序列中。现在这些数据重新被划分成了两部分，左边是新的有序序列，而右边而是新的待排序数据。接下来我们要继续上面的操作。
这里我就不再画图演示了。我们这时候要再来讨论一个问题，是不是每次只需要 end 位置的数据和 tmp 比较一次就够了，还是说整个过程是循环进行的？很明显这个过程是循环进行的。为什么我们刚刚只比较了一次呢？因为我们刚刚的有序序列只有一个元素，自然就只需要比较一次了。如果有序序列中有多个元素，那么 tmp 就要一直去找比它小的元素，如果碰到比它大的数据就让它往后挪动。
如果一直遇到的都是比 tmp 大的数据，那么 end 就会一直减一，到最后就跟上图一样，end 直接越界了，我们就需要直接结束循环，将 tmp 放到 end+1 的位置上。
然后根据上面我们说的思路，我们也会发现一个规律，就是第一次的 end 指向第一个元素，第二次的 end 指向第二个元素。因为经过第一次的排序，将右边的一个待排序数据成功插入到了左边，所以我们第二次的 end 就指向第二个元素 (end 就是有序序列的最后一个数据)。
那么相当于就是这个 end 会从第一个数据开始，遍历所有数据，也就是会遍历我们要排序的数组，这里我们就需要一个 for 循环完成。
然后每一个 end 的比较又是一个循环，循环条件就是 end >= 0。只要 end 没有越界，并且 tmp 的值比 end 位置的值小，就会一直将大的数据往后挪，end 要减一，直到 end 越界，再将 tmp 放到 end+1 的位置。
当然，并不是所有情况都会越界。如果中途碰到了比 tmp 小的值，那么就直接退出循环，也是将 tmp 放到 end+1 的位置。
那么以上就是直接插入排序的所有算法思路以及实现方法，接着我们就按照刚才的内容将直接插入排序写出来：
// 直接插入排序
{
( i = ; i < n - ; i++) {
end = i;
tmp = arr[end + ];
(end >= ) {
(arr[end] > tmp) {
arr[end + ] = arr[end];
end--;
} {
;
}
}
arr[end + ] = tmp;
}
}
