View Code of Problem 126

#include<bits/stdc++.h>
using namespace std;
typedef struct dna {
	char s[100];
	int num;
}DNA;
int cou(char a[]) {
	int count = 0;
	for (int i = 0; i < strlen(a); i++) {
		for (int j = i + 1; j < strlen(a); j++) {
			if (a[i] > a[j])count++;
		}
	}
	return count;
}

int main() {
	int m, n;
	while (cin>>m>>n) {
		DNA s1[100], temp;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++)cin >> s1[i].s[j];
		}
		for (int k = 0; k < n; k++) {
			s1[k].num = cou(s1[k].s);
		}
//		stable_sort(s1, s1 + n, cmp);
		// 插入排序
		int index;
		for(int i=1; i<n; i++) {
			index=i;
			temp=s1[i];
			if(temp.num<s1[i-1].num) {
				for(int j=i-1; j>=0; j--) {
					if(s1[j].num>temp.num) {
						s1[j+1]=s1[j];
						index=j;
					}
				}
				if(index!=i) {
					s1[index]=temp;	
				}
			} 
		} 
		for (int i = 0; i < n; i++)cout << s1[i].s << endl;
	}
}