Реализации алгоритмов/Сортировка/Блочная
- Блочная сортировка
- Карманная сортировка
- Корзинная сортировка
- Bucket sort
C#
править"Быстрый" вариант Является подвидом блочной сортировки - Сортировка подсчётом.
private void BucketSort(ref int[] items)
{
// Предварительная проверка элементов исходного массива
//
if (items == null || items.Length < 2)
return;
// Поиск элементов с максимальным и минимальным значениями
//
int maxValue = items[0];
int minValue = items[0];
for (int i = 1; i < items.Length; i++)
{
if (items[i] > maxValue)
maxValue = items[i];
if (items[i] < minValue)
minValue = items[i];
}
// Создание временного массива "карманов" в количестве,
// достаточном для хранения всех возможных элементов,
// чьи значения лежат в диапазоне между minValue и maxValue.
// Т.е. для каждого элемента массива выделяется "карман" List<int>.
// При заполнении данных "карманов" элементы исходного не отсортированного массива
// будут размещаться в порядке возрастания собственных значений "слева направо".
//
List<int>[] bucket = new List<int>[maxValue - minValue + 1];
for (int i = 0; i < bucket.Length; i++)
{
bucket[i] = new List<int>();
}
// Занесение значений в пакеты
//
for (int i = 0; i < items.Length; i++)
{
bucket[items[i] - minValue].Add(items[i]);
}
// Восстановление элементов в исходный массив
// из карманов в порядке возрастания значений
//
int position = 0;
for (int i = 0; i < bucket.Length; i++)
{
if (bucket[i].Count > 0)
{
for (int j = 0; j < bucket[i].Count; j++)
{
items[position] = bucket[i][j];
position++;
}
}
}
}
Python
правитьdef bucketSort(a, n, buckets, m):
for j in range(m):
buckets[j] = 0
for i in range(n):
buckets[a[i]] += 1
i = 0
for j in range(m):
for k in range(buckets[j]):
a[i] = j
i += 1
PHP
правитьfunction lists(array $lists = []) {
if(!$lists || count($lists) < 2) {
return [];
}
$min = $lists[0];
$max = $lists[0];
// вычисляем самое минимальное и максимальное значение через цикл
for ($i = 1; $i < count($lists); $i++) {
if($lists[$i] > $max) {
$max = $lists[$i];
}
if($lists[$i] < $min) {
$min = $lists[$i];
}
}
// Создаем блочный массив
$newLists = range(0, $max - $min + 1);
for ($i = 0; $i < count($newLists); $i++) {
$newLists[$i] = [];
}
for ($i = 0; $i < count($lists); $i++) {
$newLists[$lists[$i] - $min][] = $lists[$i];
}
$position = 0;
for ($i = 0; $i < count($newLists); $i++) {
if(count($newLists[$i]) > 0) {
for ($j = 0; $j < count($newLists[$i]); $j++) {
$lists[$position++] = $newLists[$i][$j];
}
}
}
return $lists;
}
C
правитьvoid b_sort(int sarray[], int array_size) {
const int max = array_size;
// use bucket[x][max] to hold the current count
int bucket[10][max+1];
// init bucket counters
for(var x=0;x<10;x++) bucket[x][max] = 0;
// main loop for each digit position
for(int digit = 1; digit <= 1000000000; digit *= 10) {
// array to bucket
for(int i = 0; i < max; i++) {
// get the digit 0-9
int dig = (sarray[i] / digit) % 10;
// add to bucket and increment count
bucket[dig][bucket[dig][max]++] = sarray[i];
}
// bucket to array
int idx = 0;
for(var x = 0; x < 10; x++) {
for(var y = 0; y < bucket[x][max]; y++) {
sarray[idx++] = bucket[x][y];
}
// reset the internal bucket counters
bucket[x][max] = 0;
}
}
}