PAT 1067 Sort with Swap(0, i) (25 分)

#include <iostream> using namespace std; int main() { int n,cnt=0,a[100010]; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); //从下标1开始 for(int i=1;i<n;i++) { //a[i]不在最终位置上 if(a[i]!=i) { //0不在位置0上，将位置0上的数字移动到其最终位置上 while(a[0]!=0) { swap(a[0],a[a[0]]); cnt++; } //0在位置0上，寻找第一个不在最终位置上的数字，与其交换 if(i!=a[i]) { swap(a[0],a[i]); cnt++; } } } printf("%d",cnt); return 0; }