插入排序和希尔排序
最后更新于：2022-04-01 16:16:59
几种常见排序的动画演示：[常见排序的动画演示](http://www.cs.usfca.edu/~galles/visualization/flash.html)****
**插入排序**：由N-1趟排序组成，第i趟排序保证位置0到i-1上元素是已经排好序的。
在该算法代码实现中使用了可以减少元素交换次数的技巧：在for循环内，实现了数组元素移动而没有明显使用交换。将插入排序的搜索插入位置的过程和移动元素的过程合并一起进行，从而减少了元素交换次数。位置i上的元素存储在tmp中，而位置i之前的所有更大的元素都被向右移动一个位置；然后tmp被放置在正确的位置上。这个技巧与实现二叉堆和堆排序中所用的技巧相同（可以减少交换次数，加快速度），参考[二叉堆的插入删除等操作C++实现](http://blog.csdn.net/u013074465/article/details/42028473) 和 [堆排序](http://blog.csdn.net/u013074465/article/details/42043697)。
**注意：**这几处之所以可以使用该技巧是因为他们都是对数组的操作，通过下标来实现该技巧。
该算法的平均时间为O(N^2)。希尔排序是为了冲破二次时间的屏障，但是最终证明，其时间最坏情况为O(N^2)，希尔增量对算法效率的影响很大。本文只给出了希尔排序的简单思路，没有涉及希尔增量的选取。
~~~
/*
插入排序的C实现。
平均情形为O(N^2)。
一共进行n-1趟排序，第i趟排序时保证前i个(0到i-1)是排好序的
*/
void InsertionSort(int array[], int n) {
int i, j;
int tmp;
for (i = 1; i < n; i++) {
/*
这里实现了数组元素移动而没有明显使用交换。
位置i上的元素存储在tmp中，而位置i之前的所有更大的元素
都被向右移动一个位置；然后tmp被放置在正确的位置上。
这个技巧与实现二叉堆所用的技巧相同（可以减少交换次数，加快速度）。
*/
tmp = array[i];
for (j = i; j > 0 && array[j - 1] > tmp; j--)
array[j] = array[j - 1];
array[j] = tmp;
}
}
template<typename T>
void ShellSort(vector<T>& unorder) { //希尔排序
int gap;
int i;
for (gap = unorder.size() / 2; gap > 0; gap /= 2)
for (i = gap; i < unorder.size(); i++) {
T tmp = unorder[i];
int j = i;
for (; j >= gap && tmp < unorder[j - gap]; j -= gap)
unorder[j] = unorder[j - gap];
unorder[j] = tmp;
}
}
~~~