老师,快排,堆栈溢出了,!!!

Question

老师这里我写==和您写>=有什么区别嘛?我感觉都一样,所以我写了等等,然后就堆栈溢出了,这是无限递归了?

Answer 1

liuyubobobo 2021-05-03 19:59:48

l 是有可能大于 r 的。当 l > r 的时候，从逻辑的角度，不应该做任何事情，因为此时表示要处理的区间 arr[l, r] 为空。但是如果不 return，在下面会继续处理。

换一个小数据量，尝试跟踪一下试试看？

继续加油！：）

• 提问者 我会回来的333 #1

  老师您再看下我的想法

Answer 2

提问者 我会回来的333 2021-05-04 10:07:58

老师我把我的代码又测了测近乎有序数组结果

这个是有序元素越多它就会树越高,高到一定程度应该就会溢出了

Answer 3

提问者 我会回来的333 2021-05-03 23:13:22

想了半天,老师终于想成这样的结果了,第一个递归处理的是[0~上面每个j)的元素,当j左边没有元素的时候第一个递归就到最低层了,现在看l和r的大小,l>r,第二个递归处理的是(上面每个j~右边剩下的元素],当j右边只有一个元素的时候第二个递归就到最低层了,现在看l和r的大小,l=r,所以说是两种情况一种为空的情况停止递归,一种为一个元素的情况停止递归,不知道我理解的对不对呢?波波老师?

还有老师,这里我测试的是随机从1-100的取值的元素,100万个,然后测试结果,如果测试1-10取值的话就直接溢出了

• liuyubobobo #1

  1）不知道我理解的对不对呢：完全正确。2）如果是对完全随机的数据，快排 100 万数据 3s+ 是不正常的。如果是完全有序的数据或者包含大量重复元素的数据，是正常的。课程后续会介绍如何处理这些问题。看一下使用课程的官方代码，用你的测试数据，是否有一样的问题？

• 提问者 我会回来的333 回复 liuyubobobo #2

  我的问题,我还以为老师您是元素取值范围时1-100呢,原来取值范围在0-100万,

• 提问者 我会回来的333 回复 liuyubobobo #3

  我知道了,我设置的无序数组的元素取值范围设置小了,它里面的重复元素就多了,所以慢,我应该设置元素取值1-100万,这样它就重复的不多了