Java-реализация быстрой сортировки


Это моя реализация алгоритма быстрой сортировки (алгоритм взят из книги Кормена). Это в место реализации. Пожалуйста, дайте нам знать проблем с этой или какой-либо идеи, чтобы сделать его лучше. Он выполняет в Фремонт, Калифорния.

import java.util.ArrayList;

public class MyQuickSort {

    /**
     * @param args
     */
    public static void main(String[] args) {

        //int[] a = { 1, 23, 45, 2, 8, 134, 9, 4, 2000 };
        int a[]={23,44,1,2009,2,88,123,7,999,1040,88};
        quickSort(a, 0, a.length - 1);
        System.out.println(a);
        ArrayList al = new ArrayList();
    }

    public static void quickSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q=partition(a,p,r);
            quickSort(a,p,q);
            quickSort(a,q+1,r);
        }
    }

    private static int partition(int[] a, int p, int r) {

        int x = a[p];
        int i = p-1 ;
        int j = r+1 ;

        while (true) {
            i++;
            while ( i< r && a[i] < x)
                i++;
            j--;
            while (j>p && a[j] > x)
                j--;

            if (i < j)
                swap(a, i, j);
            else
                return j;
        }
    }

    private static void swap(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}


77917
24
задан 5 августа 2011 в 07:08 Источник Поделиться
Комментарии
5 ответов

Если алгоритм был взят из книги, то скорее всего, это будет так хорошо, как это может быть. Так что пока вы следовали его букве, там не должно быть никаких проблем в реализации.

Однако есть одна вещь, я думаю, мог бы быть улучшен интерфейс, чтобы начать сортировать. Когда я думаю о сортировке коллекции, я бы ожидать, чтобы обеспечить пару вещей, коллекции конечно возможно и компаратор. Все остальное, что требует принятия конкретных реализации ценностей просто чувствует себя "неправильно" для меня. Это может быть нормально, если эти показатели представляли запуска и остановки диапазон значений для сортировки, но я бы все-таки сделать это как отдельный перегруз.

Ваша реализация с другой стороны требует сбора и индексов, необходимых для работы алгоритма. Это не будет идеальный интерфейс для работы с так как вы должны помнить, чтобы передать определенные ценности для выполнения сортировки, когда вместо этого они могут быть вычислены для меня. Я бы не подвергайте перегрузке, которая только принимает семейство в вид, который бы назвал фактической реализации с правильными аргументами.

Кроме того, хотя это хорошо известный алгоритм быстрой сортировки, я бы до сих пор обеспечивают лучшую имена переменных. Не действительно проблема здесь, личных предпочтений.

// this overload is the public interface to do the sort
public static void quickSort(int[] collection)
{
quickSort(collection, 0, collection.length - 1);
}

// note: method is now private
private static void quickSort(int[] collection, int pivotIndex, int rangeIndex)
{
// etc...
}

21
ответ дан 10 августа 2011 в 06:08 Источник Поделиться

Я вижу одно небольшое улучшение. Вместо...

i++;
while ( i< r && a[i] < x)
i++;
j--;
while (j>p && a[j] > x)
j--;

...вы можете писать:

do {
i++;
} while (i < r && a[i] < x);
do {
j--;
} while (j > p && a[j] > x);

И Джефф сразу про общедоступный интерфейс.

8
ответ дан 11 августа 2011 в 07:08 Источник Поделиться

Если вы пытаетесь сортировать уже отсортированный массив размером более 20000, то это вызовет переполнение стека. Раздел имеет проблемы при возникновении большого размера сортируемого массива.

6
ответ дан 29 апреля 2013 в 05:04 Источник Поделиться

Это выглядит действительно хорошо, но я всегда рекомендую эти руководящие принципы, когда кто-то снова код быстрой сортировки:


  1. Рандомизация: случайные ключи перестановкой можно избежать О(П2), когда почти отсортированные данные.

  2. Медиана дерева: использовать медиану первого, среднего и последнего элементов, чтобы выбрать повороте. Чем больше данных, больше образцов.

  3. Оставьте небольшой суб-массивы для сортировки вставками: отделка быстрая сортировка рекурсия и переключиться на сортировка вставками, когда меньше, то 20 элементов:

         // Insertion sort on smallest arrays
    if (rangeIndex < 20) {
    for (int i=pivotIndex; i < rangeIndex + pivotIndex; i++)
    for (int j=i; j > pivotIndex && x[j-1]>x[j]; j--)
    swap(x, j, j-1);
    return;
    }

  4. Сначала небольших раздела: только o(Фремонт, Калифорния) пространства нужен для рекурсии

Все эти советы приходят из Пластилиновая книга алгоритм руководство по проектированию, от Steven Skiena.

6
ответ дан 12 декабря 2013 в 02:12 Источник Поделиться

Я вижу еще одно улучшение. Я думаю, что это имеет больше смысла думать, что маркеры (я и Джей) должен двигаться после того, как обмен происходит. Он очищает код на несколько строк и в ней больше смысла.

private static int partition(int[] a, int p, int r) {

int x = a[p];
int i = p;
int j = r;

while (true) {
while (i < r && a[i] < x)
i++;
while (j > p && a[j] > x)
j--;

if (i < j) {
swap(a, i, j);
i++;
j--;
} else {
return j;
}
}
}

3
ответ дан 29 сентября 2013 в 02:09 Источник Поделиться