Как отсортировать массив с уникальными значениями

Question

Быстрая сортировка дает нам довольно хороший O (nlogn);Тем не менее, я подумал, есть ли способ сортировки массива с уникальными значениями, который быстрее, чем Quicksort?

Answer 1

Об алгоритмах и методах сортировки @Bilal ответ весьма полезен !!

Обойти проблему можно в O(N*log(N)), но для дальнейших вычислений будет меньше из-за удаления дублированных значений.

Таким образом, идея состоит в том, чтобы ввести значения и вставить их в std::set, что автоматически удалит дублирующиеся значения, и если дубликаты необходимы, вы можете сохранить их количество при получении ввода от пользователя !!

Пример кода будет примерно таким:

int n,x;
set<int> st;
int cnt[MAX_VAL];
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>x;
        cnt[x]++;
        st.insert(x);
    }
    // Rest of your code
}

Answer 2

Без дополнительных предположений нижняя граница для наихудшей временной сложности любого алгоритма, который использует сравнения, составляет BigTheta(nlogn). Отметим, что сортировка перестановки фактически будет обратной к р.Это означает, что если вы можете отсортировать p ({1,2, ... n), то вы сможете определить, какая перестановка была применена к вашим данным, из всех возможных перестановок.

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

Если ваш алгоритм определяет, какой раздел вы используете, листья будут одиночными, так что вы получите n!листья.Дерево с минимальной высотой, содержащее n!листьями является log (n!), который асимптотически nlog (n).http://lcm.csa.iisc.ernet.in/dsa/node208.html - хороший справочник для всего этого.

Answer 3

Вот некоторые из самых быстрых алгоритмов сортировки и их время выполнения:

• Слияние: O (nlogn)
• Timsort: O (nlogn)
• Heapsort:O (nlogn)
• сортировка по радикалам: O (nk)
• сортировка по счетам: O (n + k)