none
快速排序问题!请帮我看看怎么回事? RRS feed

  • 问题

  • 今天在wikipedia上面找了个快速排序的算法(地址:http://en.wikipedia.org/wiki/Qsort),在vs2010里面进行了代码编写,但是编译结果是错误的,没有查到是什么原因导致排序失败。请大家帮我看看是怎么回事?

    代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    
    #define MAXNUMBER 1000
    
    int (*cmp)(char *s1,char *s2);
    
    int main(int argc,char *argv[])
    {
    	int getline(char *line,int maxc);
    	void printline(char *line);
    	void quicksort(char *charline[],int left,int right);
    	int numcmp(char *s1,char *s2);
    
    	int lengthc[MAXNUMBER];
    	int i;
    	int linec=0;
    	char *charline[MAXNUMBER]={NULL};
    
    	if (*argv[1]=='n')
    		cmp = &numcmp;
    	if (*argv[1]=='s')
    		cmp = &strcmp;
    	i = 0;
    	charline[i] = (char *)malloc(MAXNUMBER*sizeof(char));
    	while ((lengthc[i]=getline(charline[i],MAXNUMBER))>0)//赋值
    	{
    		charline[++i] = (char *)malloc(MAXNUMBER*sizeof(char));
    		linec++;
    	}
    	printf("output original strings:\n");
    	i = 0;
    	while (lengthc[i]>0)//输出原字符
    	{
    		if (*argv[1]=='n' || *argv[1]=='s')
    			printf("line %d:\t",i);
    		printline(charline[i]);
    		i++;
    	}
    	quicksort(charline,0,linec-1);
    	printf("output strings sorted:\n");
    	i = 0;
    	while (lengthc[i]>0)//输出排序后字符
    	{
    		if (*argv[1]=='n' || *argv[1]=='s')
    			printf("line %d:\t",i);
    		printline(charline[i]);
    		i++;
    	}
    	system("pause");
    	return 0;
    }
    int getline(char *line,int maxc)
    {
    	char c;
    	int linec=0,i=0;
    
    	while ((c=getchar())!=EOF && c!='\n' && linec-1<maxc)
    	{
    		*(line+i++) = c;
    		linec++;
    	}
    	if (c=='\n')//回车键不是可见字符
    		*(line+i) = c;
    	*(line+i) = '\0';
    	return linec;	
    }
    void printline(char *line)
    {
    	int i=0;
    	char c;
    
    	while ((c=*(line+i++))!=EOF && c!='\n' && c!='\0')
    		printf("%c",c);
    	printf("\n");
    }
    void quicksort(char *charline[],int left,int right)  //from en.wikipedia.org
    {
    	int partition(char *charline[],int left,int right,int pivotindex);
    
    	int pivotnewindex;
    
    	if (left<right)
    	{
    		pivotnewindex = partition(charline,left,right,left);
    		quicksort(charline,left,pivotnewindex-1);
    		quicksort(charline,pivotnewindex+1,right);
    	}
    }
    //int partition(char *charline[],int left,int right,int pivotindex)  //from <The C Programming Language> book,by B.W.Kernighan&D.M.Ritchie 
    //{
    //	int numcmp(char *s1,char *s2);
    //
    //	char *pivotkey=NULL;
    //	char *temp=NULL;
    //
    //	charline[0] = temp = charline[left];
    //	pivotkey = charline[left];
    //	while (left<right)
    //	{
    //		while (left<right && (*cmp)(pivotkey,charline[right])<0) right--;
    //		charline[left] = charline[right];
    //		while (left<right && (*cmp)(charline[left],pivotkey)<0) left++;
    //		charline[right] = charline[left];
    //	}
    //	charline[left] = charline[0];
    //	//charline[left] = temp;
    //	return left;
    //}
    int partition(char *charline[],int left,int right,int pivotindex)  //from en.wikipedia.org
    {
    	int numcmp(char *s1,char *s2);
    	void swap(char *s1,char *s2);
    
    	char *pivotkey=NULL;
    	int storeindex=0,i;
    
    	pivotkey = charline[pivotindex];
    	swap(charline[pivotindex],charline[right]);
    	storeindex = left;
    	for (i=left;i<right;i++)
    		if ((*cmp)(charline[i],pivotkey)>0)
    		{
    			swap(charline[i],charline[storeindex]);
    			storeindex++;
    		}
    	swap(charline[storeindex],charline[right]);
    	return storeindex;
    }
    int numcmp(char *s1,char *s2)
    {
    	double var1,var2;
    
    	var1 = atof(s1);
    	var2 = atof(s2);
    	if (var1<var2) return -1;
    	else if (var1>var2) return 1;
    	else return 0;
    }
    void swap(char *s1,char *s2)
    {
    	char *temp;
    
    	temp = s1;
    	s1 = s2;
    	s2 = temp;
    }
    //注:命令参数中使用字符's'


    输入以及输出结果举例:

    ksiggl
    dlgogohohho
    sdogo
    dfohohho
    ldfo
    dlfhhjhj


    output original strings:
    line 0: ksiggl
    line 1: dlgogohohho
    line 2: sdogo
    line 3: dfohohho
    line 4: ldfo
    line 5: dlfhhjhj
    output strings sorted:
    line 0: ksiggl
    line 1: dlgogohohho
    line 2: sdogo
    line 3: dfohohho
    line 4: ldfo
    line 5: dlfhhjhj
    Press any key to continue . . .


    煮酒论英雄

    2012年2月16日 3:07

全部回复

  • 调试一下

    看看程序具体是怎样执行的

    然后再具体分析原因


    新浪微博http://weibo.com/xianglitian,欢迎围观

    2012年2月17日 0:21