我正在使用下面的代码使用快速排序算法对给定的数组进行排序。我是一个初学者,正在努力理解为什么我的代码在少数测试用例上运行良好,但在少数测试用例上失败。我收到错误“超出时间限制”。代码不断地使测试用例失败:- array{5,5,6,8,4,5,6}
。请随意提供有关如何更好地编码的提示。
public static void quickSort(int[] input) {
quickSort(input, 0 , input.length-1) ;
}
public static void quickSort(int input[] , int startIndex , int endIndex) {
if(startIndex >= endIndex){
return;
} else{
int pivot = partition(input, startIndex , endIndex);
quickSort(input,startIndex , pivot-1) ;
quickSort(input , pivot+1 , endIndex) ;
}
}
public static int partition(int input[] ,int startIndex , int endIndex) {
int pivot = input[startIndex] ;
int count = 0;
for(int i = 1+startIndex ; i < input.length ; i++){
if(input[i] < pivot){
count++;
}
}
input[startIndex] = input[startIndex+count];
input[startIndex+count] = pivot ;
int s = startIndex ;
int e = endIndex ;
int sc = startIndex+count;
while(s < sc && sc < e){
if(input[s] < pivot) {
s++;
} else if(input[e] >= pivot){
e--;
}else if(input[s] > pivot && input[e] < pivot){
int temp = input[e];
input[e] = input[s] ;
input[s] = temp;
e--;
s++;
}
}
return sc;
}
}
最佳答案
乍一看,您似乎正在使用索引来指示子数组限制
public static int partition(int input[] ,int startIndex , int endIndex)
但是你总是迭代整个数组(条件是 i < input.length
):
for(int i = 1+startIndex ; i < input.length ; i++){
if(input[i] < pivot){
count++;
}
...
因此,在后续迭代中,您仍然会遍历整个数组:
所以在这次通话中:
quickSort(input,startIndex , pivot-1);
pivot -1
当您浏览 input.length
时将被忽略无论如何都会导致守卫状态:
if (startIndex >= endIndex )
永远不会评估为 true,因此永远运行。
尝试将 for 循环更改为(我自己没有尝试过,只是查看代码):
for(int i = 1+startIndex ; i < endIndex ; i++){
看看这是否有效。
我希望这会有所帮助。
关于java - QuickSort Java 代码给出错误超过时间限制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60078247/