题目大意：

序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如：在单词序列“DAABEC’”中，因为D大于右边四个单词，E大于C，所以计算结果为5。这种计算方法称为序列的逆序数。序列“AACEDGG”逆序数为1（E与D）——近似排序，而序列“ZWQM” 逆序数为6（它是已排序序列的反序）。

你的任务是分类DNA字符串（只有ACGT四个字符）。但是你分类它们的方法不是字典序，而是逆序数，排序程度从好到差。所有字符串长度相同。

输入：

第一行包含两个数：一个正整数n（0<n<=50）表示字符串长度，一个正整数m（0<m<=100）表示字符串个数。接下来m行，每行一个长度为n的字符串。

输出：

输出输入字符串列表，按排序程度从好到差。如果逆序数相同，就原来顺序输出。

Java源码：

import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; import java.util.Scanner;


class Main {
static class Node implements Comparable{
String str="";

int id=0;

int sortN=0;
Node(String str,int id,int sortN){

this.str=str;

this.id=id;

this.sortN=sortN;

}
public int compareTo(Object o) {

Node node=(Node)o;

if(node.sortN==sortN){

return node.id<id?1:(node.id==id?0:-1);

}else{

return node.sortN<sortN?1:-1;

}

}
}
private static int getSortN(String str){

int len=str.length();

int ans=0;

for(int i=0;i<len;i++){

for(int j=i+1;j<len;j++){

if(str.charAt(i)>str.charAt(j))

ans++;

}

}

return ans;

}

public static void main(String[] args) { Scanner in = new Scanner(System.in); in.nextInt(); int ncase=in.nextInt(); List<Node> l=new ArrayList<Node>(); for(int i=0;i<ncase;i++){ String str=in.next(); l.add(new Node(str,i,getSortN(str))); } Collections.sort(l); for(Iterator<Node> it=l.iterator();it.hasNext();){ System.out.println(it.next().str); } } }

未经允许不得转载：Bcoder资源网 » Poj 1007 Java DNA 排序