Быстрый поиск. Обработка дубликатов

Question

Может ли кто-нибудь показать мне, как обрабатывать дубликаты в QuickSort с моей функцией здесь?

private static int[] quickSort(int[] input, int left, int right) { 
    int mid = (left + right)/2; 
    int i = left; 
    int j = right; 

    if((right - left) < 1) { 
     return new int[]{}; 
    } 

    while(i <= j) { 
     while((input[i] < input[mid])) { 
      i++; 
     } 

     while((input[j] > input[mid])) { 
      j--; 
     } 

     if(i <= j) { 
      int temp = input[i]; 
      input[i] = input[j]; 
      input[j] = temp; 
      i++; 
      j--; 
     } 
    } 

    if(j > left) { 
     input = quickSort(input, left, j); 
    } 

    if(i < right) { 
     input = quickSort(input, i, right); 
    } 
    return input; 
} 

Answer 1

Код имеет несколько проблем.

• "return new int [] {};" Это создаст новые массивы и без необходимости потребляет память. Вы можете вернуть «ввод».
• Для первых внутренних петель вам может потребоваться «вход [i] < = вход [mid] & & i < mid". Это будет обрабатывать дубликаты.

Есть некоторые хорошо протестированный код здесь: Quick Sort