几种常见排序的动画演示：[常见排序的动画演示](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; } } ~~~