давай также для radix sort
- User
давай также для radix sort
Assistant
Radix Sort: Реализация на Python и C++
Radix Sort — это несравнительный алгоритм сортировки, который сортирует числа по разрядам, начиная с младшего. Он использует стабильную сортировку (например, подсчет) для каждого разряда, что позволяет ему работать за линейное время.
✅ Реализация Radix Sort на Python
def radix_sort(arr): if not arr: return arr # Найти максимальное число для определения количества разрядов max_num = max(arr) exp = 1 # Степень 10 (1, 10, 100, ...) while max_num // exp > 0: # Использовать стабильную сортировку (подсчет) для текущего разряда count = [0] * 10 output = [0] * len(arr) # Подсчёт количества элементов for num in arr: digit = (num // exp) % 10 count[digit] += 1 # Накопление количества for i in range(1, 10): count[i] += count[i - 1] # Построение выходного массива for i in reversed(range(len(arr))): digit = (arr[i] // exp) % 10 output[count[digit] - 1] = arr[i] count[digit] -= 1 # Обновить массив arr = output # Перейти к следующему разряду exp *= 10 return arr # Пример использования arr = [170, 45, 75, 90, 802, 24, 2, 66] sorted_arr = radix_sort(arr) print("Отсортированный массив:", sorted_arr)
✅ Реализация Radix Sort на C++
#include <iostream> #include <vector> #include <cmath> using namespace std; vector<int> radix_sort(vector<int> arr) { if (arr.empty()) { return arr; } int max_num = *max_element(arr.begin(), arr.end()); int exp = 1; // Степень 10 (1, 10, 100, ...) while (max_num / exp > 0) { vector<int> count(10, 0); vector<int> output(arr.size(), 0); // Подсчёт количества элементов for (int num : arr) { int digit = (num / exp) % 10; count[digit]++; } // Накопление количества for (int i = 1; i < 10; ++i) { count[i] += count[i - 1]; } // Построение выходного массива for (int i = arr.size() - 1; i >= 0; --i) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } // Обновить массив arr = output; // Перейти к следующему разряду exp *= 10; } return arr; } // Пример использования int main() { vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66}; vector<int> sorted_arr = radix_sort(arr); cout << "Отсортированный массив: "; for (int num : sorted_arr) { cout << num << " "; } cout << endl; return 0; }
📌 Пояснения:
-
Этап 1: Нахождение максимального числа
Чтобы определить, сколько разрядов нужно обработать, мы находим максимальное число в массиве. -
Этап 2: Сортировка по разрядам
Для каждого разряда (единицы, десятки, сотни и т.д.) мы используем стабильную сортировку (подсчет), чтобы распределить числа по цифрам. -
Этап 3: Повторение для всех разрядов
После сортировки по текущему разряду, мы переходим к следующему разряду (умножаяexpна 10). -
Сложность:
- Время: O(n * k), где
n— количество элементов,k— количество разрядов. - Память: O(n + b), где
b— размер алфавита (в данном случае 10 для десятичных цифр).
- Время: O(n * k), где
🧪 Пример работы:
Вход:
[170, 45, 75, 90, 802, 24, 2, 66]
Выход:[2, 24, 45, 66, 75, 90, 170, 802]
⚠️ Примечание:
Radix Sort работает эффективно только с неотрицательными целыми числами. Для отрицательных чисел требуется дополнительная обработка (например, разделение на положительные и отрицательные).
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.