QuickSort Java ошибка при выдаче кода Превышен лимит времени - PullRequest
Новая
       11

QuickSort Java ошибка при выдаче кода Превышен лимит времени

0 голосов
/ 05 февраля 2020

Я использую приведенный ниже код для сортировки заданного массива с помощью быстрой сортировки Al go. Я новичок и изо всех сил пытаюсь понять, почему мой код работает нормально на нескольких тестовых примерах, но не на нескольких. Я получаю сообщение об ошибке Превышен лимит времени. Код постоянно проходит тестовый случай: - 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;
        }    
    }

1 Ответ

0 голосов
/ 06 февраля 2020

На первый взгляд кажется, что вы используете индексы как способ указания пределов подмассива 

        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 игнорируется, как вы go - input.length в любом случае, вызывая условие защиты:

if (startIndex >= endIndex )

никогда не оценивать как истинное, следовательно, работает вечно.

Попробуйте изменить значение для l oop на (не пробовал сам, просто взглянув на код): 

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

И посмотрите, работает ли это.

Надеюсь, это поможет.

...