Сортировка в линейное время? [закрытый]

Связи протоколов - это то, что вы ищете:

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

blockquote>

  
    
      
        
          
        
      
    
  

23
задан Pete Kirkham 16 April 2009 в 14:57
поделиться

7 ответов

Также обратите внимание на родственные сорта: сортировка по голубям или подсчетная сортировка , а также радикальной сортировки , как упомянуто Пукку.

23
ответ дан 29 November 2019 в 01:07
поделиться
23
ответ дан 29 November 2019 в 01:07
поделиться

When people say "sorting algorithm" they often are referring to "comparison sorting algorithm", which is any algorithm that only depends on being able to ask "is this thing bigger or smaller than that". So if you are limited to asking this one question about the data then you will never get more than n*log(n) (this is the result of doing a log(n) search of the n factorial possible orderings of a data set).

If you can escape the constraints of "comparison sort" and ask a more sophisticated question about a piece of data, for instance "what is the base 10 radix of this data" then you can come up with any number of linear time sorting algorithms, they just take more memory.

This is a time space trade off. Comparason sort takes little or no ram and runs in N*log(n) time. radix sort (for example) runs in O(n) time AND O(log(radix)) memory.

9
ответ дан 29 November 2019 в 01:07
поделиться

Википедия показывает довольно много различных алгоритмов сортировки и их сложности. Вы можете проверить их

3
ответ дан 29 November 2019 в 01:07
поделиться

Это действительно просто, если n = 2 и числа уникальны:

  • Построить массив битов (2 ^ 31-1 бит => ~ 256 МБ). Инициализируйте их равными нулю.
  • Считайте ввод, для каждого значения, которое вы видите, установите соответствующий бит в массиве на 1.
  • Сканируйте массив, для каждого установленного бита выведите соответствующее значение.

Сложность => O (2n)

В противном случае используйте Radix Sort:

Complexity => O (kn) (надеюсь)

3
ответ дан 29 November 2019 в 01:07
поделиться

Набор ограниченного диапазона чисел может быть представлен битовой картой битов RANGE. В этом случае, 500-битное растровое изображение, поэтому для всех, кроме огромных списков, вам будет лучше с Radix Sort. Когда вы встретите число k, установите битовую карту [k] = 1. Одиночный обход списка, O (N).

2
ответ дан 29 November 2019 в 01:07
поделиться

alike algo is possible:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

It's alone possible algo for linear complexity, but it has complexity O(k*N) by ram (N - number array elements, k -- element's len)

-2
ответ дан 29 November 2019 в 01:07
поделиться
Другие вопросы по тегам:

Похожие вопросы: