快速排序法(C语言)

#include #include #include #include

#define randx(x) (rand()%x) typedef int KeyType; typedef int DataType; typedef struct {

KeyType key;/*排序码字段*/ DataType info; /*记录的其它字段*/ }RecordNode; typedef struct {

int n; /*文件中的记录个数,可以视为常量*/ RecordNode *record; }SortObject;

void creatsort(SortObject * pvector, int &l, int &r)//新建二叉排序树 { int i; int k; printf(\您即将要创建一个序列\\n\ printf(\请输入该序列元素的个数\\n\ scanf(\ pvector->record = (RecordNode*)malloc((sizeof(RecordNode))*(pvector->n));

printf(\你要以什么方式创建序列？\\n方式1：自动创建请输入1，方式2：手动创建请输入0\\n\ scanf(\ if (k) { srand((int)time(0)); for (i = 0; i < pvector->n; i++) { if(pvector->n<100) pvector->record[i].key = randx(100); else if((pvector->n<1000)) pvector->record[i].key = randx(1000); else pvector->record[i].key = randx(pvector->n); } } else { printf(\请输入%d个大小不一样的整数\\n\

for (i = 0; i < pvector->n; i++) { scanf(\ } }

if (pvector) printf(\序列创建成功！\\n\else

printf(\序列创建失败！\\n\ l = 0, r = pvector->n-1; }

void show(SortObject * pvector) {

printf(\当前序列为：\\n\ if (!pvector) printf(\当前序列为空\ else for (int i = 1; i <= pvector->n; i++) { printf(\ if (i % 15 == 0) printf(\ } printf(\}

void quickSort(SortObject* &pvector, int l, int r) { int i, j; RecordNode temp, *data = pvector->record; if (l >= r) return; /* 只有一个记录或无记录，则无须排序*/ i = l; j = r; temp = data[i]; while (i != j) {/* 找Rl的最终位置*/ while (i< j && data[j].key >= temp.key) j--; /* 向左扫描找排序码小于temp.key的记录*/ if (i< j) data[i++] = data[j]; while (i< j && data[i].key <= temp.key) i++; /* 向右扫描找排序码大于temp.key的记录*/ if (i< j)

data[j--] = data[i]; } data[i] = temp; /* 将 Rl存入其最终位置*/ quickSort(pvector, l, i - 1); /* 递归处理左区间*/ quickSort(pvector, i + 1, r); /* 递归处理右区间*/ }

void interface(void) {

printf(\输入序号执行相应操作&&&&&&&&&&&&&&&&&\\n\printf(\ 输入1，重新建立序列！ \\n\printf(\

printf(\ 输入2，快速排序当前序列！\\n\printf(\

printf(\ 输入3，显示当前序列！\\n\ printf(\ printf(\ 输入其他，退出操作！\\n\ printf(\}

void operation(SortObject* pvector, int l, int r) { int k = 1, num; while (k) { interface();//显示界面 scanf(\ switch (num) { case 1: free(pvector->record);//重新生成之前释放空间 free(pvector);//重新生成之前释放空间 creatsort(pvector, l, r); break; case 2: { quickSort(pvector, l, r);//执行快速排序 printf(\已经为你执行快速排序！\\n\ } break; case 3: { show(pvector); } break; default:

printf(\您未选定任何操作！请重新输入操作序号！\\n\ k = 0; break; } } }

int main() { int l=0,r=0; }

SortObject * pvector = (SortObject *)malloc(sizeof(SortObject));//分配序列指针 creatsort(pvector, l, r); operation(pvector, l, r); getchar(); getchar(); return 0;