作者：Leon916 来源：C++博客 酷勤网收集 2008-05-22
摘要
主要用到了插入排序算法，并且参看了桶排序算法，如果大家有什么好的想法，希望能够共享一下，嘿嘿！我的代码有哪里写的不好，也请大家指教！
题目：来自：http://acm.pku.edu.cn/JudgeOnline/problem?id=1007
Description
One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.
Input
The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.
Output
Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.
Sample Input
10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT
Sample Output
CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA
Source
昨天晚上写完了这道题，早上过来提交。 主要用到了插入排序算法，并且参看了桶排序算法，如果大家有什么好的想法，希望能够共享一下，嘿嘿！我的代码有哪里写的不好，也请大家指教！
1
#include <stdlib.h>
2#include <stdio.h>
3typedef struct dNANumber
4
{
5
char ch[100];
6 int count;
7
}DNANumber;
8
9void Sort(DNANumber *arr, int rows)
10{
11 int i, j;
12 DNANumber temp;
13 for(i = 1; i < rows; i++)
14
{
15 temp = arr[i];
16 for(j = i-1; j >= 0; j--)
17 {
18 if(arr[j].count > temp.count)
19 arr[j+1] = arr[j];
20 else
21 break;
22
}
23 arr[j+1] = temp;
24 }
25 return;
26}
27
28int Index(char ch)
29{
30 switch(ch)
31 {
32 case 'A':
33 return 0;
34 case 'C':
35 return 1;
36 case 'G':
37 return 2;
38 case 'T':
39 return 3;
40 }
41}
42
43void CountNumber(DNANumber *dna, int length)
44{
45 int count = 0;
46 int letter[4] = {0,0,0,0};
47 int i, j;
48 int temp;
49
50 for(i = 0; i < length; i++)
51 {
52 letter[Index(dna->ch[i])]++;
53 }
54
55 for(i = length-1; i >= 0; i--)
56 {
57 temp = Index(dna->ch[i]);
58 for(j = temp+1; j < 4; j++)
59 {
60 count += letter[j];
61 }
62 letter[temp]--;
63 }
64 dna->count = count;
65 return;
66}
67int main(int argc, char* argv[])
68{
69 int length = 0, rows = 0;
70 int i;
71 DNANumber dnaArray[10000];
72 //DNANumber *dna;
73
74 scanf("%d %d", &length, &rows);
75 for(i = 0; i < rows; i++)
76 {
77 dnaArray[i].count=0;
78 scanf("%s", dnaArray[i].ch);
79 CountNumber(&dnaArray[i], length);
80 }
81
82 Sort(dnaArray, rows);
83
84 for(i = 0; i < rows; i++)
85 {
86 printf("%s\n", dnaArray[i].ch);
87 }
88 return 0;
89}
90
91
92
#include <stdlib.h>2
#include <stdio.h>3
typedef struct dNANumber4
{5
char ch[100];6
int count;7
}DNANumber;8
9
void Sort(DNANumber *arr, int rows)10
{11
int i, j;12
DNANumber temp;13
for(i = 1; i < rows; i++)14
{15
temp = arr[i];16
for(j = i-1; j >= 0; j--)17
{18
if(arr[j].count > temp.count)19
arr[j+1] = arr[j];20
else 21
break;22
}23
arr[j+1] = temp;24
}25
return;26
}27
28
int Index(char ch)29
{30
switch(ch)31
{32
case 'A':33
return 0;34
case 'C':35
return 1;36
case 'G':37
return 2;38
case 'T':39
return 3;40
}41
}42
43
void CountNumber(DNANumber *dna, int length)44
{45
int count = 0;46
int letter[4] = {0,0,0,0};47
int i, j;48
int temp;49
50
for(i = 0; i < length; i++)51
{52
letter[Index(dna->ch[i])]++;53
}54
55
for(i = length-1; i >= 0; i--)56
{57
temp = Index(dna->ch[i]);58
for(j = temp+1; j < 4; j++)59
{60
count += letter[j];61
}62
letter[temp]--; 63
}64
dna->count = count;65
return;66
}67
int main(int argc, char* argv[])68
{69
int length = 0, rows = 0;70
int i;71
DNANumber dnaArray[10000];72
//DNANumber *dna;73
74
scanf("%d %d", &length, &rows);75
for(i = 0; i < rows; i++)76
{77
dnaArray[i].count=0;78
scanf("%s", dnaArray[i].ch);79
CountNumber(&dnaArray[i], length); 80
}81
82
Sort(dnaArray, rows);83
84
for(i = 0; i < rows; i++)85
{86
printf("%s\n", dnaArray[i].ch);87
}88
return 0;89
}90
91
92
来自：acm1007探讨！