计数排序

1def counting_sort(a):2    # Works for non-negative integers with a small max value3    counts = [0] * (max(a) + 1)4    for value in a:5        counts[value] += 16    # Prefix sums turn counts into final positions7    for i in range(1, len(counts)):8        counts[i] += counts[i - 1]9    out = [0] * len(a)10    for value in reversed(a):  # reversed keeps equal values stable11        counts[value] -= 112        out[counts[value]] = value13    return out14
15
16nums = [4, 2, 2, 8, 3, 3, 1]17print("Before:", nums)18print("After: ", counting_sort(nums))

1function countingSort(arr) {2    // Count occurrences of each value, then rebuild in order3    const max = Math.max(...arr);4    const count = new Array(max + 1).fill(0);5    for (const x of arr) count[x]++;6    const out = [];7    count.forEach((c, value) => {8        for (let k = 0; k < c; k++) out.push(value);9    });10    return out;11}12
13const data = [4, 2, 9, 2, 7, 4, 1, 4];14console.log("Before:", data);15console.log("Sorted:", countingSort(data));

1import java.util.Arrays;2
3public class Main {4    static int[] countingSort(int[] arr) {5        int max = 0;6        for (int v : arr) max = Math.max(max, v);7        int[] count = new int[max + 1];8        for (int v : arr) count[v]++;9        // Prefix sums turn counts into final positions10        for (int i = 1; i <= max; i++) count[i] += count[i - 1];11        int[] out = new int[arr.length];12        // Walk backwards so equal values keep their order (stable)13        for (int i = arr.length - 1; i >= 0; i--) {14            out[--count[arr[i]]] = arr[i];15        }16        return out;17    }18
19    public static void main(String[] args) {20        int[] arr = {4, 2, 2, 8, 3, 3, 1};21        System.out.println("Before: " + Arrays.toString(arr));22        int[] sorted = countingSort(arr);23        System.out.println("After:  " + Arrays.toString(sorted));24    }25}

1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void countingSort(std::vector<int>& a) {11    if (a.empty()) return;12    int maxVal = *std::max_element(a.begin(), a.end());13    // count[v] = how many times v appears14    std::vector<int> count(maxVal + 1, 0);15    for (int x : a) ++count[x];16    // Rebuild the array from the counts17    size_t idx = 0;18    for (int v = 0; v <= maxVal; ++v) {19        while (count[v]-- > 0) a[idx++] = v;20    }21}22
23int main() {24    std::vector<int> data = {4, 2, 2, 8, 3, 3, 1, 7};25    std::cout << "Before: ";26    printVec(data);27    countingSort(data);28    std::cout << "After:  ";29    printVec(data);30    return 0;31}

1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9void countingSort(int a[], int n) {10    int maxVal = a[0];11    for (int i = 1; i < n; i++) {12        if (a[i] > maxVal) maxVal = a[i];13    }14    // count[v] = how many times v appears15    int* count = calloc(maxVal + 1, sizeof(int));16    for (int i = 0; i < n; i++) count[a[i]]++;17    // Rebuild the array from the counts18    int idx = 0;19    for (int v = 0; v <= maxVal; v++) {20        while (count[v]-- > 0) a[idx++] = v;21    }22    free(count);23}24
25int main(void) {26    int data[] = {4, 2, 2, 8, 3, 3, 1, 7};27    int n = sizeof(data) / sizeof(data[0]);28    printf("Before: ");29    printArr(data, n);30    countingSort(data, n);31    printf("After:  ");32    printArr(data, n);33    return 0;34}