4回答

慕标8212032

提问者

2019-04-04

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

        // 获取[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);

0

1

liuyubobobo

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

2019-04-04

共1条回复

liuyubobobo

2019-04-04

赞！很好的想法。

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

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

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

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

继续加油！：）

0

6

慕标8212032

回复

liuyubobobo

由于不能超过300个字，补充: 所以最后我小于V等于V的判断是分开的两个if， 而不是if. ..else的情况， 跟老师的相比，老师的一次考虑一个元素，三个判断只能执行一个，遇到小于的情况下一次还要考虑这个元素，而我的只有两个判断，每次遍历都要执行两次判断， 然后代码我在下面加了一个回答, 里面把代码放上去了, 老师能帮我看下我的实现和你的实现相比是否有劣势呢

2019-04-04

共6条回复

慕标8212032

提问者

2019-04-03

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

0

0

慕标8212032

提问者

2019-04-03

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

0

0