关于老师说的任意一种高级排序算法可以用插入排序来进行优化以及我的优化方案?

Question

在进行归并排序和快速排序过程中, 对于元素个数少于15左右的采用插入排序来进行优化, 而
在插入排序过程中老师提到了希尔排序, 我通过谷歌了解并实现了希尔排序, 希尔排序作为插入排序的变种, 使得一个元素能够一次移动多个位置, 而插入排序只能移动一个位置, 希尔排序的时间复杂度处于O(nlogn) 与 O(n^2)之间, 经过测试, 我发现希尔排序比插入排序的性能好的非常多, 那么在进行快速排序的时候我采用希尔排序来代替归并排序会不会更好呢, 此时将区间元素个数判断提高到400左右, 那么由此得出高级排序算法在个数达到一定程度用希尔排序进行优化比插入排序好, 请问这样得出的结果是否可行呢?

Answer 1

提问者 慕标8212032 2019-04-04 10:09:59

这个是我的三路排序的代码

        // 获取[l, r]区间随机的一个元素的索引并将其放在第一个位置
		int randomIndex = (int)(Math.random() * (r - l) + l);
		swap(arr, l, randomIndex);
		
		// 对第一个元素进行快速排序
		int littleIndex = l; // 最后一个小于V的位置
		int equalIndex = l; // 最后一个等于V的位置
		
		for (int i = l + 1; i <= r; i++) {
			
			// 小于当前元素
			if (arr[i].compareTo(arr[l]) < 0) {
				swap(arr, i, ++littleIndex);
			} 
			
			// 等于当前的元素(小于之后还要再考虑一次这个元素是否等于V)
			if (arr[i].compareTo(arr[l]) == 0) {
				// 此时需要判断equalIndex是否还指向初始位置
				if (equalIndex <= littleIndex) {
					equalIndex = littleIndex;
				}
				swap(arr, i, ++equalIndex);
			}
			
		}
		
		int insertIndex = littleIndex;
		// 对右边进行遍历前, 需要考虑没有出现相同的元素的情况, 那么此时equalIndex仍然是指向第一个元素的, 此时需要将其调整到littleIndex位置
		// 这样右边的遍历才能够以equalIndex + 1的位置开始
		equalIndex = equalIndex > littleIndex ? equalIndex : littleIndex;

		swap(arr, insertIndex, l);
		
		sort(arr, l, insertIndex - 1);
		sort(arr, equalIndex + 1, r);

• liuyubobobo #1

  大赞！一点儿毛病都没有：）感谢你的分享！：）

Answer 2

liuyubobobo 2019-04-04 01:18:37

赞！很好的想法。

首先，有可能。但需要具体需要实测，来看看具体的结果。

但其实，对于现代计算机来说，这个优化是没有必要的。因为没有从本质上改变整个算法的时间复杂度，影响微乎其微。再加上现代计算机上，算法的实际性能，不仅仅逻辑相关，和语言的编译器，包括操作系统的运行状态，关系很大。所以，这样的一个“理论上”的优化，可能适得其反。即使真能优化，由于优化效果实在太有限了，引入新的代码，反而可能导致bug'的产生。如果我再次讲一下这个课程，可能不会介绍这个优化了：）

具体，也可以参考这个问答：https://coding.imooc.com/learn/questiondetail/108055.html

依然是，这是一个很棒的思考。我没有测试过，不知道答案，如果有兴趣，可以自己测试一试试看：）

继续加油！：）

• 提问者 慕标8212032 #1

  老师，关于二路排序的。我也有一个自己的想法，并且实现了，因为要将相同的元素均匀的分布在两旁，那么我依然向随机排序一样，不同的是我维护了一个布尔值，当为真的时候在将其插入到左侧，当为假的时候什么也不做，就等于插入到了右侧，并且每次遇到相同的值，都对布尔值取反，这样就可以均匀的插入两侧了

• liuyubobobo 回复 提问者 慕标8212032 #2

  大赞！很棒的想法！：）

• 提问者 慕标8212032 回复 liuyubobobo #3

  还有三路排序，我也有了自己的实现，不过要用代码来解释了。现在太晚了，我明天再在评论区跟老师贴上我的思路和代码，经过测试，是可以的，我只维护了两个变量，一个左边最小的值的最后一个位置，一个是相等值的最后一个位置

点开查看后面3条评论

Answer 3

提问者 慕标8212032 2019-04-03 16:49:38

有个地方写错了，是在快速排序和归并排序，采用希尔排序来代替插入排序

Answer 4

提问者 慕标8212032 2019-04-03 16:48:44

有个地方写错了，是在快速排序和归并排序