幾種常見排序的動畫演示：[常見排序的動畫演示](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; } } ~~~