Быстрая Реализация Сортировки


Я написал ниже код для быстрой сортировки в Java:

void quicksort (int[] a, int lo, int hi)
    {
 //  lo is the lower index, hi is the upper index
 //  of the region of array a that is to be sorted
 int i=lo, j=hi, h;

 // comparison element x
 int x=a[(lo+hi)/2];

 //  partition
 do
 {    
     while (a[i]<x) i++; 
    while (a[j]>x) j--;
    if (i<=j)
    {
        h=a[i]; 
        a[i]=a[j]; 
        a[j]=h;
        i++; 
        j--;
    }
 } while (i<=j);

 //  recursion
  if (lo<j) quicksort(a, lo, j);
 if (i<hi) quicksort(a, i, hi);
}

Пожалуйста, ознакомьтесь и, возможно, предложить лучшее решение.



1165
7
задан 17 декабря 2011 в 04:12 Источник Поделиться
Комментарии
2 ответа

Некоторые мелкие замечания:


  1. Вместо того, чтобы комментировать здесь:

    void quicksort (int[] a, int lo, int hi) {
    // lo is the lower index, hi is the upper index
    // of the region of array a that is to be sorted
    int i=lo, j=hi, h;

    переименовать переменные:

    void quicksort (final int[] a, final int lowerIndex, final int upperIndex)

    Это легче читать.

    (Проверить чистый код Роберт С. Мартин, С. 53-54 также.)


  2. Старайтесь свести к минимуму объем локальных переменных. Это не нужно объявлять их в начале метода.

    (Эффективная Java, второе издание, пункт 45: минимизировать область видимости локальных переменных. (Google для "минимизации видимости локальных переменных", это в Google книгах тоже.))


  3. Это:

    h=a[i]; 
    a[i]=a[j];
    a[j]=h;

    могут быть извлечены для замены метода:

    public void swap(final int[] arr, final int pos1, final int pos2) {
    final int temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
    }

  4. Может быть, вы должны предоставить простой в использовании вспомогательный метод для клиентов:

    public void quicksort(final int[] data) {
    if (data == null) {
    throw new NullPointerException("data cannot be null");
    }
    if (data.length == 0) {
    return;
    }
    quicksort(data, 0, data.length - 1);
    }

    Обратите внимание на проверки входных данных.


7
ответ дан 17 декабря 2011 в 05:12 Источник Поделиться

Вы сократить код немного, но это может навредить читабельности:

    a[i]=a[j]; 
a[j]=h;
i++;
j--;

//can be written as:

a[i++]=a[j];
a[j--]=h;

1
ответ дан 17 декабря 2011 в 09:12 Источник Поделиться