插入排序和希尔排序

逃离我推掉我的手 2022-08-06 04:12 158阅读 0赞

几种常见排序的动画演示：[常见排序的动画演示][Link 1]

**插入排序**：由N-1趟排序组成，第i趟排序保证位置0到i-1上元素是已经排好序的。

在该算法代码实现中使用了可以减少元素交换次数的技巧：在for循环内，实现了数组元素移动而没有明显使用交换。将插入排序的搜索插入位置的过程和移动元素的过程合并一起进行，从而减少了元素交换次数。位置i上的元素存储在tmp中，而位置i之前的所有更大的元素都被向右移动一个位置；然后tmp被放置在正确的位置上。**这个技巧与实现二叉堆和堆排序中所用的技巧相同（可以减少交换次数，加快速度），参考[二叉堆的插入删除等操作C++实现][C] 和 [ 堆排序][Link 2]。**

**注意：**这几处之所以可以使用该技巧是因为他们都是对数组的操作，通过下标来实现该技巧。

**该算法的平均时间为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;
    		}
    }

[Link 1]: http://www.cs.usfca.edu/~galles/visualization/flash.html
[C]: http://blog.csdn.net/u013074465/article/details/42028473
[Link 2]: http://blog.csdn.net/u013074465/article/details/42043697