Блог

У меня есть код быстрой сортировки на java, который я хочу улучшить. Улучшенный код должен занимать меньше времени, чем код быстрой сортировки. Однако при использовании моего улучшенного кода, который реализует разделение медианы из 3, это занимает на 400 милисекунд больше. Кто-нибудь может помочь мне решить эту проблему? если возможно, можете ли вы предложить мне другие возможные способы улучшения моего кода. Мне нужно отсортировать от 10 000 до 10 миллионов целых чисел.

Быстрая сортировка

 public void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);

        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex 1, end);
    }


}

private int partition(int arr[], int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);

    for (int j = begin; j < end; j  ) {
        if (arr[j] <= pivot) {
            i  ;

            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }

    int swapTemp = arr[i 1];
    arr[i 1] = arr[end];
    arr[end] = swapTemp;

    return i 1;
}

}
  

Улучшенный код

 package sorting;


public class improvement {

Clock c = new Clock();

  public void quickSort(int[] intArray) {

    recQuickSort(intArray, 0, intArray.length - 1);

  }

  public static void recQuickSort(int[] intArray, int left, int right) {
    int size = right - left   1;
    if (size <= 3)
      manualSort(intArray, left, right);
    else {
      double median = medianOf3(intArray, left, right);
      int partition = partitionIt(intArray, left, right, median);
      recQuickSort(intArray, left, partition - 1);
      recQuickSort(intArray, partition   1, right);
    }
  }

  public static int medianOf3(int[] intArray, int left, int right) {
  int center = (left   right) / 2;

    if (intArray[left] > intArray[center])
      swap(intArray, left, center);

    if (intArray[left] > intArray[right])
     swap(intArray, left, right);

   if (intArray[center] > intArray[right])
     swap(intArray, center, right);

   swap(intArray, center, right - 1);
   return intArray[right - 1];
  }

  public static void swap(int[] intArray, int dex1, int dex2) {
    int temp = intArray[dex1];
    intArray[dex1] = intArray[dex2];
    intArray[dex2] = temp;
 }

  public static int partitionIt(int[] intArray, int left, int right, double 
  pivot) {
    int leftPtr = left;
    int rightPtr = right - 1;

     while (true) {
       while (intArray[  leftPtr] < pivot) 
       ;
       while (intArray[--rightPtr] > pivot)
       ;
       if (leftPtr >= rightPtr)
         break;
       else
       swap(intArray, leftPtr, rightPtr);
    }
    swap(intArray, leftPtr, right - 1);
    return leftPtr;
 }

 public static void manualSort(int[] intArray, int left, int right) {
    int size = right - left   1;
    if (size <= 1)
     return;
   if (size == 2) {
  if (intArray[left] > intArray[right])
    swap(intArray, left, right);
  return;
} else {
  if (intArray[left] > intArray[right - 1])
    swap(intArray, left, right - 1);
  if (intArray[left] > intArray[right])
    swap(intArray, left, right);
  if (intArray[right - 1] > intArray[right])
    swap(intArray, right - 1, right);
  }
 }
}