qsort4.c

自己做的常用库和实现的数据结构。public domain.

/* Demo of simplest qsort implementation.
 *
 * Written by Cyril Hu ([e-mail]), public domain.
 */
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 50
void swap(int a[], int i, int j)
{
	int t = a[i]; a[i] = a[j]; a[j] = t;
}

int partition(int a[], int low, int high)
{
	int pivot = a[low];
	while(low < high) {
		while(low < high && a[high] >= pivot)
		       high--;
		swap(a, low, high);	
		while(low < high && a[low] <= pivot)
		       low++;
		swap(a, low, high);	
	}
	return low;
}

void quicksort(int a[], int low, int high)
{
	int pivot;
	if(low < high) {
		pivot = partition(a, low, high);
		quicksort(a, low, pivot-1);	
		quicksort(a, pivot+1, high);	
	}
}

typedef struct s {
	int sn;
	struct s *next;
} S;
void push(S **sp, int bp)
{
	static size_t cnt = 0;
	S *t = (S *)malloc(sizeof(S));
	if(t == NULL) {
		fprintf(stderr, "Fatal: mem alloc failed !");
		exit(1);
	}
	t->sn = bp;
	t->next = cnt++ ? *sp : NULL;
	*sp = t;
}
int stack_empty(S *sp)
{
	return sp != NULL ? 0 : 1;
}
void pop(S **sp)
{
	S *t = *sp;
	if(! stack_empty(*sp)) {
		*sp = (*sp)->next;
		free(t);
	}
}
int gettop(S *sp)
{
	return sp->sn;
}
void qsort_stack(int a[], int low, int high)
{
	S *sp;
	int pivot; 
	if(low < high) {
		pivot = partition(a, low, high);
		push(&sp, low);	push(&sp, pivot-1); push(&sp, pivot+1); push(&sp, high);
		while(! stack_empty(sp)) {
			high = gettop(sp); pop(&sp); low = gettop(sp); pop(&sp);
			if(low < high) {
				pivot = partition(a, low, high);
				push(&sp, low);	push(&sp, pivot-1); push(&sp, pivot+1); push(&sp, high);
			}
		}
	}
}
int main()
{
	int i,a[MAX];
	srand(time(NULL));
	for(i=0; i<MAX; i++)
		printf("%d ", a[i] = rand() % (MAX * 2));
	quicksort(a, 0, MAX-1);
	puts("\nafter qsort");
	for(i=0; i<MAX; i++)
		printf("%d ", a[i]);

	puts("\n");
	for(i=0; i<MAX; i++)
		printf("%d ", a[i] = rand() % (MAX * 2));
	qsort_stack(a, 0, MAX-1);
	puts("\nafter qsort with stack");
	for(i=0; i<MAX; i++)
		printf("%d ", a[i]);
	puts("");
	return 0;
}