快速排序 Java 代码给出错误超出时间限制

Question

我正在使用下面的代码使用快速排序算法对给定的数组进行排序。我是初学者，正在努力理解为什么我的代码在少数测试用例上运行良好，但在少数测试用例上失败。我收到错误"超出时间限制"。代码不断使测试用例失败：-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;
}    
}

Answer 1

乍一看，您似乎正在使用索引来指示子数组限制

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);

无论如何，当您经历input.length时，pivot -1将被忽略，从而导致保护条件：

if (startIndex >= endIndex )

永远无法评估为真，因此永远运行。

尝试将 for 循环更改为(我自己没有尝试过，只是通过查看代码(：

for(int i = 1+startIndex ; i < endIndex ; i++){

看看这是否有效。

我希望这有所帮助。