Я делал свою домашнюю работу и застрял в одном из вопросов, которые задают о сортировке по линейному времени. Ниже вопрос.
Предположим, у вас есть массив A из n целых чисел с множеством дубликатов, и вам говорят, что в A. есть не более 10 различных целых чисел. Дайте алгоритм линейного времени для сортировки массива A с использованием основанной на сравнении модели для сортировки. Вы не можете использовать хеширование или любой другой алгоритм линейной сортировки по времени, основанный на значениях, например, Bucket Sort или Redix Sort.