a233 - 排序法~~~ 挑戰極限

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取多組測試資料，每組資料包含一個正整數 N，代表接下來有 N 個正整數需要排序。輸出排序後的 N 個正整數，以空白分隔。題目提示 Bubble Sort, Insertion Sort, Selection Sort 容易 TLE，Quick Sort 在某些測資下也會 TLE，推薦使用 Merge Sort, Heap Sort 或 Radix Sort。

解題思路

此題的解題思路非常直接，使用 C++ 標準函式庫中的 sort 函數對輸入的陣列進行排序。sort 函數預設使用 IntroSort，它結合了 QuickSort、HeapSort 和 Insertion Sort 的優點，在大多數情況下具有良好的效能。雖然題目提示 QuickSort 可能 TLE，但 sort 函數的 IntroSort 演算法可以避免 QuickSort 在最壞情況下的效能問題。

複雜度分析

• 時間複雜度: O(N log N) (平均情況和最壞情況，因為 sort 使用 IntroSort)
• 空間複雜度: O(log N) (IntroSort 的遞迴堆疊空間，在最壞情況下可能達到 O(N))

程式碼

#include <iostream>
#include <algorithm> 

using namespace std;

int main(){

	long long int a=0;
	while(cin >> a){
		long long int b[a];
		for(long long int i=0;i<a;i++){
			cin >> b[i];
		}
		sort(b,b+a);
		for(long long int i=0;i<a;i++){
			cout << b[i] << " ";
		}
		cout << endl; 
	}
	
}