洛谷P1177【模板】排序：十种排序算法全解(2)

我们接着上一篇继续讲【洛谷P1177【模板】排序：十种排序算法全解(1)】

三、计数排序（Counting Sort）

‌仅适用于数据范围较小的情况‌

// Java
import java.io.*;
public class Main {
    static final int OFFSET = 100000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strs = br.readLine().split(" ");
        int[] cnt = new int[200001];
        for (int i = 0; i < n; i++) 
            cnt[Integer.parseInt(strs[i]) + OFFSET]++;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= 200000; i++) 
            while (cnt[i]-- > 0) sb.append(i - OFFSET).append(" ");
        System.out.println(sb);
    }
}

# Python
n = int(input())
nums = list(map(int, input().split()))
min_val, max_val = min(nums), max(nums)
offset = -min_val
count = [0] * (max_val - min_val + 1)
for num in nums:
    count[num + offset] += 1
sorted_arr = []
for i in range(len(count)):
    sorted_arr.extend([i - offset] * count[i])
print(' '.join(map(str, sorted_arr)))

// C
#include <stdio.h>
#include <limits.h>
int main() {
    int n;
    scanf("%d", &n);
    int min_val = INT_MAX, max_val = INT_MIN;
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];
    }
    int size = max_val - min_val + 1;
    int* count = calloc(size, sizeof(int));
    for (int i = 0; i < n; i++) count[arr[i] - min_val]++;
    for (int i = 0; i < size; i++)
        while (count[i]-- > 0) printf("%d ", i + min_val);
    return 0;
}