学步园

这道题拿到以后，自己的第一感觉 就是递归穷举所有可能的情况，然后用strcmp来比大小。

先然效率不高 有n!中情况，可能性很低。。

看书了，发现快排居然可以这样用，自己定义比较来处理，真的长见识了。

来code一遍。

#include "stdio.h"
#include "string.h"
#define MAX 1024
#define STRLEN 25
int cmp(char *str1,char *str2)
{
	char *str=(char *)malloc(sizeof(char )*(strlen(str1)+strlen(str2)+1));
	char *strR=(char *)malloc(sizeof(char )*(strlen(str1)+strlen(str2)+1));
	int compare =0;
	int ret=0;
	strcpy(str,str1);
	strcat(str,str2);
	strcpy(strR,str2);
	strcat(strR,str1);
	compare = strcmp(str,strR);
	if(compare>0)
		ret = 1;
	else if(compare ==0)
		ret=0;
	else
		ret=-1;	
	
	free(str);
	free(strR);
	return ret;
}
int Partion(char **strGroup,int s,int e,int (*cmp)(char *str1,char *str2))
{
	char *temp = (char *)malloc(sizeof(char)*(STRLEN+1));
	int i=s-1;
	int j=0;
	char *key = strGroup[e];
	for(j=0;j<e;j++)
	{
		if(cmp(strGroup[j],key)<0)
		{
			strcpy(temp,strGroup[i+1]);
			strcpy(strGroup[i+1],strGroup[j]);
			strcpy(strGroup[j],temp);
			i+=1;
		}
	}
	strcpy(temp,strGroup[i+1]);
	strcpy(strGroup[i+1],key);
	strcpy(key,temp);
	free(temp);
	return i+1;
}
void quickSort(char **strGroup,int s,int e,int (*cmp)(char *str1,char *str2))
{
	int q=0;
	if(s<e)
	{
		q = Partion(strGroup,s,e,cmp);
		quickSort(strGroup,s,q-1,cmp);
		quickSort(strGroup,q+1,e,cmp);
	}

}





int main()
{
	char **strGroup;
	int i=0;
	int n=0;
	strGroup = (char **)malloc(sizeof(char *)*MAX);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		strGroup[i] =(char *)malloc(sizeof(char)*STRLEN);
		scanf("%s",strGroup[i]);
	}
	quickSort(strGroup,0,n-1,cmp);
	for(i=0;i<n;i++)
	{
		printf("%s",strGroup[i]);
	}
	printf("\n");
	for(i=0;i<n;i++)
	{
		free(strGroup[i] );
	}
	
	free(strGroup);
}

这种代码写起来爽多了。