В чем разница между встроенной функцией qsort и стабильной функцией сортировки?
Из приведенных источников я знаю, что встроенная функция C, stable_sort, стабильна, но qsort нестабильна. Если это так, почему мы вообще используем qsort? Разве это не избыточно? Почему бы вместо этого не использовать stable_sort?
Решение
Причиной выбора быстрой сортировки вместо стабильной является в основном скорость: qsort часто быстрее чем stable_sort, что не должно вызывать удивления, потому что stable_sort поставляется с более сильной гарантией.
O (N · журнал2(N)). Если доступна дополнительная память, то сложность O (N · log (N)).
Пространство является еще одним соображением: qsort выполняется на месте, это означает, что дополнительное выделение памяти не требуется. stable_sortс другой стороны, пытается временно выделить размер, равный сортируемому массиву.
Эта функция пытается выделить временный буфер, равный по размеру последовательности, которую нужно отсортировать. Если распределение не удается, выбирается менее эффективный алгоритм.
Примечание от rcgldrкомментарий: (Реализация HP / Microsoft std::stable_sort использует временный буфер 1/2 размера последовательности. Вторая половина сортируется во вторую половину последовательности, первая половина во временный буфер, затем временный буфер и вторая половина последовательности объединяются обратно в последовательность.
Другие решения
Стабильная сортировка означает, что порядок равных элементов сохраняется. Это не всегда обязательно.
Если это не требуется, алгоритм упрощается, а иногда быстрее и / или более эффективно использует память.
Типичным примером стабильного алгоритма сортировки является Сортировка слиянием.
Если это так, почему мы вообще используем qsort?
stable_sort() не является частью стандарта C. qsort() является частью стандарта C.
C о qsort() не указано использование алгоритма быстрой сортировки, не требуется быть стабильным или нестабильным.
qsort() часто используется как самый портативный. Так как qsort() не имеет спецификаций, касающихся скорости, эффективности использования памяти и стабильности данных, часто кодируется с использованием практического метода для целевой платформы. На встроенной платформе пространство памяти часто более критично, чем скорость. На рабочем столе скорость, вероятно, имеет первостепенное значение.