Стабильность подхода быстрого разделения

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

Сортировка стабильна, если исходный порядок подобных элементов не меняется. Ваш алгоритм нестабилен, так как он меняет местами равные элементы.

Если это не так, то он все равно не будет стабильным:

( 1, 5, 2, 5, 3 )

У вас есть два элемента с ключом сортировки "5". Если вы по какой-то причине сравните элемент № 2 (5) и № 5 (3), то 5 будет заменено на 3, тем самым нарушив контракт стабильного вида. Это означает, что тщательный выбор сводного элемента не помогает, вы также должны убедиться, что копирование элементов между разделами никогда не меняет исходный порядок мест.

Ваш код подозрительно похож на образец функции разделения, приведенный в wikipedia , который нестабилен, поэтому ваша функция, вероятно, нестабильна. По крайней мере, вы должны убедиться, что ваша точка поворота r указывает на последнюю позицию в массиве значений, равных A [r].

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

Мартин (см. комментарии) прав, что быстрая сортировка в связанном списке, где вы начинаете с первого элемента в качестве точки поворота и добавляете значения в конце нижнего и верхние подсписки при просмотре массива. Однако предполагается, что быстрая сортировка работает с простым массивом, а не со связанным списком. Одно из преимуществ быстрой сортировки - это ' малый объем памяти (потому что все происходит на месте). Если вы используете связанный список, у вас уже есть накладные расходы на память для всех указателей на следующие значения и т. Д., И вы меняете местами их, а не значения.

Из Википедии:

Быстрая сортировка - это сортировка сравнения, а в эффективные реализации, не является стабильная сортировка.

Если вам нужна стабильная сортировка O (n * log (n)), используйте mergesort . (Лучший способ сделать QuickSort стабильным, кстати, выбрать медиану случайных значений в качестве шарнира. Это не является стабильным для всех элементов, эквивалентных, однако.)