a539 - 10327 - Flip Sort
題目描述
題目要求計算將給定的整數序列使用相鄰元素交換（類似 Bubble Sort）排序所需的最小交換次數。
解題思路
此題採用貪心策略。每次遍歷數組，如果發現相鄰元素順序錯誤，則立即交換。重複此過程，直到數組完全排序。由於每次交換只考慮相鄰元素，因此可以保證在每次迭代中，最大的元素會“冒泡”到其正確的位置。持續進行此操作，直到整個數組排序完成。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int b;
while(cin>>b){
int c = 0,a[b]={};
for(int h=0;h<b;h++)
cin>>a[h];
for(int i=0;i<b;i++){
bool flag = 0;
for(int j=0;j<b-1;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
c++;
}
}
for(int o = 1;o<b;o++)
if(a[o]<a[o-1])
flag = 1;
if(flag==0)
break;
}
cout<<"Minimum exchange operations : "<< c <<'\n';
}
}