View Code of Problem 143

#include<iostream>
using namespace std;
struct node{
	int no;//序号 
	int count;//逆序数 
};
int main() {
	int n, m;
	while(cin>>n>>m) {
		string s[m];
		struct node arr[m];
		for(int i=0; i<m; i++) {
			cin>>s[i];
			arr[i].no=i;
			arr[i].count=0;
			//统计逆序数 
			for(int j=0; j<n-1; j++) {
				for(int k=j+1; k<n; k++) {
					if(s[i][j]>s[i][k]) arr[i].count++;
				}
			}
		}
		//插入排序(稳定排序)
		int temp, j, index;
		for(int i=1; i<m; i++) {
			temp=arr[i].count;
			index=arr[i].no;
			if(temp<arr[i-1].count) {
				for(j=i-1; j>=0; j--) {
					if(temp<arr[j].count) {
						arr[j+1].count=arr[j].count;
						arr[j+1].no=arr[j].no;
					}else {//找到要插入的位置了! 
						break;
					}
				}
				if(j+1!=i) {
					arr[j+1].no=index;
					arr[j+1].count=temp;
				}
			}
		} 
		for(int i=0; i<m; i++) cout<<s[arr[i].no]<<endl;
	}
}