1007 DNA Sorting

      题目的意思很明显，就是算出每个字符串的逆序数，然后按照它们的逆序数排序，最后输出。因此这里的主要操作可以分两步：

 

①计算逆序数

      注意到这里出现的字符只有4种（ACGT），因此可以将字符串扫描一遍就可以计算出逆序数。方法是，对字符串进行正向扫描，记录扫描时C、G、T出现的次数，如果当前扫描的字符是A，则逆序数要依次加上C、G、T的个数；如果是C，则逆序数加上G、T的个数；如果是G，则逆序数加上T的个数。

 

②将字符串按照逆序数进行排序

      这里要求当逆序数相同时，按照出现顺序排序，即排序结果要稳定。所以如果要使用快速排序的化，不能直接按照逆序数来当做比较标准，但可以变通，比如当逆序数相同时，把字符串的出现的顺序作为比较标准。

      在Java中对于对象数组的排序是稳定的（具体算法：在JDK7以前使用的是归并排序MergeSort，JDK7中使用的是TimSort。有时间研究一下，希望可以看得懂~~）。

 

import java.util.*;
import java.io.*;
//1007 DNA Sorting
public class Main 
{
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		int countOfCase, lengthOfString;

		lengthOfString = in.nextInt();
		countOfCase = in.nextInt();

		DNA[] DNAs = new DNA[countOfCase];
		for(int i = 0; i < countOfCase; i++)
			DNAs[i] = new DNA(in.next());

		Arrays.sort(DNAs);

		for(DNA dna: DNAs)
			System.out.println(dna.strOfDNA);
	}
}

class DNA implements Comparable<DNA>
{
	String strOfDNA;
	int countOfInversion;

	public DNA(String strOfDNA) {
		this.strOfDNA = strOfDNA;
		calInversion();
	}

	private void calInversion() {
		countOfInversion = 0;

		int C = 0, G = 0, T = 0;
		for(int i = 0, n = strOfDNA.length(); i < n; i++) {
			switch(strOfDNA.charAt(i)) {
				case 'A':
					countOfInversion = countOfInversion + C + G + T;
					break;
				case 'C':
					C++;
					countOfInversion = countOfInversion + G + T;
					break;
				case 'G':
					G++;
					countOfInversion = countOfInversion + T;
					break;
				case 'T':
					T++;
					break;
			}
		}
	}

	public int compareTo(DNA another) {
		return countOfInversion - another.countOfInversion;
	}
}