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

pivot -1当您浏览 input.length 时将被忽略无论如何都会导致守卫状态:

if (startIndex >= endIndex )

永远不会评估为 true，因此永远运行。

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

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

看看这是否有效。

我希望这会有所帮助。