洛谷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;
}