CareerCup 150 1.3 @1point3acres

1.3.c

/*
* CareerCup 150 4/16-4/22 1.3
*
* slaink@1point3acres
*
*/

/*
*感觉上和1.1类似，但是不需用任何其他的buffer，只能一两个变量。这样说来bitmap就肯定不行了。
*再考虑一下qsort的可能性，qsort的确可以nlogn时间找到dup,但是另一个问题是如何删除字符串。
*暂时的想法是移动到末尾，用一个计数器，最后统一删除掉。可是这样的话在递归过程中就可能产生问题(另外这样的方式就改变字符串顺序了)
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int dup=0;

void quicksort(char *string, int low, int high);
int select(char *string, int low, int high);
char *qsort_way(char *string);

int main(int argc, char **argv)
{
    if(argc != 3){
        printf("usage: <program name> <type 1:qsort> <string>\n");
        return 0;
    }
    switch(atoi(argv[1])) {
        case 1:
			printf("%s\n", qsort_way(argv[2]));
            break;
    }

    return 0;
    
} 

char *qsort_way(char *string)
{
	quicksort(string, 0, strlen(string) - 1);
	
	string[strlen(string)-dup]='\0';
/*	if(dup!=0)
		free((char *)(string+sizeof(char)*(strlen(string) - dup)));
*/	
	return string;
}

void quicksort(char *string, int low, int high)
{
	int i;
	if(low < high) {
		i = select(string, low, high);
		if(i == -1)
			return;
		quicksort(string, low, i-1);
		quicksort(string, i+1, high);
	}
}

int select(char *string, int low, int high)
{
	int p, q;
	char i, tmp;
	i = string[low];
	p = low+1;
	q = high - dup;
	if(p >=strlen(string)-1-dup)
		return -1;
	while(p < q) {
		while(string[p] < i)
			p++;
		if(string[p] == i) {
			string[p] = string[high-dup];
			string[high-dup] = i;
			if(q == high - dup)
				q --;
			dup++;
		}
		while(string[q] > i)
			q--;
		if(string[q] == i && q != low) {
			string[q] = string[high-dup];
			string[high-dup] = i;
			if (q == high - dup)
				q --;
			dup++;
		}
		
		if(p < q) {
			tmp = string[p];
			string[p] = string[q];
			string[q] = tmp;
		}
	}
	
	string[low] = string[q];
	string[q] = i;
	
	return q;
	
}