一个序列的逆序数定义为序列中无序元素对的数目。例如，在字符序列DAABEC中，逆序数为5，因为字符D比它右边的4个字符大，而字符E比它右边的1个字符大。字符序列AACEDGG只有1个逆序，即E和D,它几乎是已经排好序的，而字符序列“ZWQM”有6个逆序，它是最大程度的无序，即有序序列的逆序。 在本题中，你的任务是对DNA字符串（只包含字符“A”、“C”，“G”和“T”）进行排序。注意不是按照字母顺序，而是按照逆序数从低到高进行排序，所有字符串的长度都一样。
输入文件中包含多组测试数据。每组测试数据的格式为：第1行为2个整数，正整数n(0 < n <= 50，表示字符串的长度)和正整数m(1 < m <= 100,表示字符串的数目)；然后是m行，每一行为一个字符串，长度为n。
对应到输入文件中的N组测试数据，输出也有N组，每2组输出之间有一个空行。对每组输入数据，按逆序数从低到高输出各字符串，如果2个字符串的逆序数一行，则按输入时的先后顺序输出。
思路：
首先构造结构体，结构体里面有①存储字符串的数组，②求解字符串逆序数的函数，③求字符串长度的函数（求逆序数的函数要用到字符串长度）。通过每个字符串的逆序数对结构体数组的排序，用到qsort()函数。（自定义cmp比较函数）qsort(数组首地址，数组长度，数组元素字节大小，指向比较函数的指针)
#include <iostream> using namespace std; struct charList { char data[20]; //求字符串长度的函数（求逆序数的函数要用到字符串长度） int length() { int pos = 0; while(this->data[pos] != '\0') { pos++; } return pos - 1; } //求解字符串逆序数的函数 int antiNum() { int result = 0; int listLength = this->length(); for(int i = 0; i < listLength; i++) { for(int j = i + 1; j < listLength; j++) { if(this->data[i] > this->data[j]) { result++; } } } return result; } }; //自定义比较函数 int cmp(const void *a, const void *b) { charList *p1 = (charList *)a; charList *p2 = (charList *)b; return p1->antiNum() - p2->antiNum(); } //定义结构体数组 charList DNA[20]; int main() { int m, n; //m是字符串的长度，n是字符串个数 scanf("%d %d", &m, &n); int pos = 0; while(pos < n) { cin>>DNA[pos].data; pos++; } qsort(DNA, n, sizeof(DNA[0]), cmp); for(int i = 0; i < m; i++) { cout<<DNA[i].data<<endl; } return 0; }