UVa 10327

題目

http://domen111.github.io/UVa-Easy-Viewer/?10327

題目包含多筆測試資料，每筆測試資料第一行有一個正整數 $n$，接下來有 $n$ 個數字

求將這個序列由小到大排序需要最少只需要交換多少次

$n \leq 1000$

想法

因為這一題的 $n$ 很小，所以我們可以直接實作 bubble sort，然後計算我們總共交換了幾次

如果說 $n$ 很大，那就需要用 merge sort 來實作，不過這裡就不實作了

Code

//By Koios1143
#include<iostream>
using namespace std;
int n, ans, arr[1005];
int bubble_sort(){
	ans=0;
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<n-1-i ; j++){
			if(arr[j] > arr[j+1]){
				swap(arr[j], arr[j+1]);
				ans++;
			}
		}
	}
	return ans;
}
int main(){
	while(cin>>n){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		bubble_sort();
		cout<<"Minimum exchange operations : "<<ans<<"\n";
	}

	return 0;
}

複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資排序時間複雜度為 $O(n^2)$

每筆測資總時間複雜度為 $O(n + n^2)$