牛骨文教育服务平台(让学习变的简单)

几种常见排序的动画演示:常见排序的动画演示****

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

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

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

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