Реализации алгоритмов/Сортировка/Блочная

• Блочная сортировка
• Карманная сортировка
• Корзинная сортировка
• 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;
        }
    }
}