- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
Counting Sort - O(n + k)
Counting Sort O(n + k) O(n + k) O(n + k) O(k) ✅ Маленький диапазон значений
def counting_sort(nums):
count = defaultdict(int)
minVal, maxVal = min(nums), max(nums)
for val in nums:
count[val] += 1
index = 0
for val in range(minVal, maxVal + 1):
while count[val] > 0:
nums[index] = val
index += 1
count[val] -= 1
from collections import defaultdict
def stable_counting_sort(nums):
if not nums:
return nums
# 1. Считаем сколько раз встретилось каждое число
count = defaultdict(int)
for val in nums:
count[val] += 1
# 2. Получаем отсортированные ключи
sorted_keys = sorted(count.keys())
# 3. Считаем префиксные суммы (позиции для стабильности)
positions = {}
total = 0
for key in sorted_keys:
positions[key] = total
total += count[key]
# 4. Создаём массив результата
output = [0] * len(nums)
for val in nums:
index = positions[val]
output[index] = val
positions[val] += 1 # увеличиваем позицию для следующего одинакового элемента
return output
Follow us!
Комментарии (0) RSS
Добавить комментарий