Обработка дубликатов ключей в алгоритме быстрой сортировки


Наивный быстрой сортировки займет o(п^2) времени, чтобы отсортировать массив, содержащий уникальные ключи, так как все ключи будут разделены либо до, либо после разворота стоимости. Есть способы, чтобы справиться с повторяющимися ключами (как описано в алгоритме быстрой сортировки является оптимальным). Предложенное решение работает только для раздела Хоара, но я реализовал раздела Lomuto. Чтобы бороться с дубликатами ключей, я колебался между перемещение дубликатов слева от оси и перемещение дубликатов в правой части разворота. Вот моя быстрая сортировка (игнорировать отсутствие генериков):

public static void swap(Comparable[] sort, int a, int b){
    Comparable temp=sort[a];
    sort[a]=sort[b];
    sort[b]=temp;
}
public static void quicksort(Comparable[] sort, int start, int end){
    while(end-start>1){//normal case
        int pivot=gen.nextInt(end-start)+start;//random pivot
        swap(sort, pivot, start);
        int index=start;//walking index
        boolean dupHandler=false;//init to true works also
        for(int i=start+1; i<end; ++i){//Lomuto partition
            int val=sort[start].compareTo(sort[i]);
            if(val>0 || ( val==0 && (dupHandler=!dupHandler) ) )
                swap(sort, ++index, i);
        }
        swap(sort, start, index);
        if(index-start<end-index-1){//recurse into smaller partition
            quicksort(sort, start, index);
            start=index+1;//use iteration for other partition
        }
        else{
            quicksort(sort, index+1, end);
            end=index;
        }
    }
}

Есть ли лучше (более эффективный) способ обработки дубликатов ключей? Если нет, есть ли способ, чтобы значительно улучшить мой код?



8858
3
задан 5 августа 2011 в 02:08 Источник Поделиться
Комментарии
1 ответ


  1. Использовать функцию swap, а затем повторяя три линии, необходимые для замены элементов в три раза

  2. Ставить пробелы вокруг операторов

  3. Вам избежать рекурсией для второго раздела. Я не думаю, что прирост производительности от этого достаточно для дополнительной сложности в коде.

А потом меняла до/после элемента равного к оси, посчитать количество элементов, равное опорной. Затем, когда вы отсортировать подмассив сделать один подмассив короче, чтобы не сортировать элементы, равные оси.

Еще как Рейф отметил, Проблема в том, что есть и другие проблемы, к тому же дубликаты ключей, которые могут привести к О(N^2) поведения. Ваш код не обрабатывает какой-либо из этих.

3
ответ дан 5 августа 2011 в 05:08 Источник Поделиться