Какая сортировка эффективна для сортировки данных по возрастанию в порядке убывания?

Question

Я хочу отсортировать набор данных, используя реализацию C. Интересно, какая сортировка эффективна и лучше всего подходит по времени. Обратите внимание, что данные находятся только в порядке возрастания. Я хочу отсортировать его в порядке убывания. Какой из них более эффективный и наименее эффективный и почему? Кто-нибудь может объяснить это разумом?

Answer 1

В этом конкретном случае вам не нужно использовать алгоритм сортировки как таковой. Например, вы можете просто поменять элемент i th с элементом n - i th:

for(i = 0; i < size/2; ++i)
{
    tmp = arr[i];
    arr[i] = arr[size - 1 - i];
    arr[size - 1 - i] = tmp;
}

Это всегда имеет сложность O(n/2). Я не думаю, что есть гораздо более быстрый способ. Конечно, кроме чтения данных в другом направлении.