c431 - Sort ! Sort ! Sort !

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一串數字，並將這些數字從小到大排序後輸出。輸入首先包含數字的個數 n，然後是 n 個介於 1 到 100 之間的數字。

解題思路

由於數字的範圍有限 (1 到 100)，可以使用計數排序 (Counting Sort) 的方法來進行排序。計數排序的基本思想是統計每個數字出現的次數，然後按照數字的大小順序輸出對應的次數。

程式碼中，a[i] 用於儲存數字 i 出現的次數。程式首先讀取輸入的數字，並更新 a 陣列中對應數字的計數。然後，程式遍歷 a 陣列，對於每個數字 i，輸出 a[i] 次的 i。

複雜度分析

• 時間複雜度: O(n + k)，其中 n 是輸入數字的個數，k 是數字的範圍 (在本題中 k = 100)。由於 k 是常數，因此時間複雜度可以簡化為 O(n)。
• 空間複雜度: O(k)，其中 k 是數字的範圍。在本題中，空間複雜度為 O(100)，可以視為常數空間。

程式碼

#include <stdio.h>
int a[101]={0};
int main(){
	int n,x;
	scanf("%d",&n);
	while(n--){
		scanf("%d",&x);
		a[x]++;
	}
	for(int i=1;i<101;i++){
		while(a[i]--){
			printf("%d ",i);
		}
	}
}