POJ 1007 DNA Sorting

想法：
　　 使用bubble sort時候每交換一次逆序數就+1，最後由逆序數小到大輸出。至於求逆序數更快的算法可參考UVa 10810 Ultra-Quicksort。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct sortedDNA
	{
	int num;
	char *line;
	}a[101];
	int bubble_sort(char a[],int n);
	bool cmp(sortedDNA a,sortedDNA b);
	int main()
	{
	int n,m,i,j;
	char DNA[101][52];
	scanf("%d %d\n",&n,&m);
	for(i=0;i<m;i++){
	gets(DNA[i]);
	a[i].line=DNA[i];
	a[i].num=bubble_sort(DNA[i],n);
	}
	sort(a,a+m,cmp);
	for(i=0;i<m;i++){
	for(j=0;j<n;j++){
	printf("%c",a[i].line[j]);
	}
	printf("\n");
	}
	return 0;
	}
	bool cmp(sortedDNA a,sortedDNA b)
	{
	return a.num<b.num;
	}
	int bubble_sort(char a[],int n)
	{
	int i,j,num=0;
	for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
	if(a[i]>a[j]) num++;
	return num;
	}

view raw [POJ] 1007 DNA Sorting.cpp hosted with ❤ by GitHub