几种排序算法的代码实现(3)

break;

if (status = inputList(test, n) != 0) {

puts(\输入的数字有误！\ while(getchar() != '\\n'); //exit(status); }

heapSort(test, comp); outputList (test);

printf(\请输入下一组待排序的数的个数(输入0结束循环)：\ }

free(test); return 0; }

int comp(void * d1, void * d2) {//比较函数

return (((PRedType)d1)->data - ((PRedType)d2)->data ); }

//归并排序

/*这是merge_sort.h文件*/ #ifndef merge_sort

#define merge_sort

#define MAXSIZE 100 typedef int KeyType;

typedef struct {

KeyType data; //其他的属性 }RedType,* PRedType;

typedef struct {

RedType list[MAXSIZE]; int length; }SqList, * PSqList;

#define K_T \ //用于输入输出 如 printf(K_T, p->list[i].data);

#define OK 0

#define P_NULL 1 #define TOOBIG 2

#define NUM_ERROR 3

int inputList (PSqList p,int length); int outputList (PSqList p);

int mergeSort (PSqList p, PSqList d, int (*comp)(void *, void *)); #endif

/*这是merge_sort.cpp文件*/ #include #include #include #include \

int inputList (PSqList p,int length) {//输入序列

if (p == NULL)

return P_NULL; //1，指针是空的 if (length > MAXSIZE)

return TOOBIG; //2，要输入的序列太多 srand(time(NULL)); int i = 0;

for (i = 0; i < length; i++)

p->list[i].data = rand()000;

//if (scanf(K_T,&(p->list[i].data)) != 1)

// return NUM_ERROR; //3，输入的数字有误 p->length = length; return OK; //0 }

int outputList (PSqList p) {//输出序列

if (p == NULL)

return P_NULL;

int i = 0;

for (i =0; i < p->length; i++)

printf (K_T\ putchar('\\n'); return OK; }//outputList

static int merge (PSqList p, PSqList d,int (*comp)(void *,void *), int s, int m, int n) {

//本来是没使用tmp作为中转的，后来考虑到，如果p和d是一个列表就会出现问题。而且下面给的非递归版的归并排序，p和d是同以个列表

PSqList tmp; //如果用全局变量就不用每次申请了 tmp = (PSqList)malloc(sizeof(SqList)); tmp->length = p->length; int i = s; int j = m + 1; int k = s;

while (i <= m && j <= n) {

if (comp(&(p->list[i]), &(p->list[j])) < 0) tmp->list[k++] = p->list[i++]; else

tmp->list[k++] = p->list[j++]; }

while (i <= m)

tmp->list[k++] = p->list[i++];

while (j <= n)

tmp->list[k++] = p->list[j++];

for (i = s; i <= n; i++)

d->list[i] = tmp->list[i]; free(tmp); return 0; }

static int mSort (PSqList p, PSqList d, int (*comp)(void *, void *), int s, int n) {

if (s == n) {

d->list[s] = p->list[s]; return 0; }

SqList t;

t.length = p->length;

int m;

m = (s + n)/2;

mSort(p, &t, comp, s, m); mSort(p, &t, comp, m + 1, n);

merge(&t, d, comp, s, m, n); return OK; }//mSort

int mergeSort (PSqList p, PSqList d, int (*comp)(void *, void *)) {

mSort (p, d, comp, 0, p->length-1); return OK; } /*

int mergeSort (PSqList p, PSqList d,int (*comp)(void *, void *))

{//这是非递归实现的归并排序，第二个参数是不需要的，这里只是为了和之前的函数兼容 //将p归并排序，需要改变原本的p列表的内容，排序后的结果还是保留在p中。如果要不改变p并且将排序后的结果放在d中则只需开辟一个中转站即可 d = p; int i,j;

for (i = 1; i < p->length; i*=2) {

for (j = 0; j+2*i-1 < p->length; j = j+2*i) {

merge (p, d, comp, j, j+i-1, j+2*i-1); }

if (j+i-1 length-1)

merge (p, d, comp, j, j+i-1, p->length-1); }

return OK; } */

/*这是main.cpp文件*/ #include #include #include \int comp(void *, void *);

int main (int argc, char * argv) {

int status; PSqList test;

test = (PSqList)malloc(sizeof(SqList)); PSqList dist;

dist = (PSqList)malloc(sizeof(SqList)); int n = 0 ;

printf(\请输入第一组待排序的数的个数(输入0结束循环)：\

while (1) {

while (scanf(\ {

puts(\输入有误！请重新输入！\ while(getchar() != '\\n'); }

if (n == 0) //结束 break;

if (status = inputList(test, n) != 0) {

puts(\输入的数字有误！\ while(getchar() != '\\n'); //exit(status); }

dist->length = n;

mergeSort(test, dist, comp); outputList (dist);

printf(\请输入下一组待排序的数的个数(输入0结束循环)：\ }

free(test); free(dist); return 0; }

int comp(void * d1, void * d2) {//比较函数

return (((PRedType)d1)->data - ((PRedType)d2)->data ); }

//计数排序

#include #include #include #include

#define MAXSIZE 1000000

#define MAX 1000 //定义数据的取值范围 int count[MAX];

int rand_num (int *s, int n); int output (int *d, int n);