/*这是shell_sort.h文件的内容*/ //这是希尔排序的头文件 #ifndef shell_sort
#define shell_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 comp(void * d1, void * d2); int inputList (PSqList p,int length); int outputList (PSqList p);
int shell_insert (PSqList p, int (*comp)(void *, void *),const int d);
int shellSort(PSqList p, int (*comp)(void *, void *), const int distance[], const int t); #endif
/*这是shell_sort.cpp文件的内容*/
//这是希尔排序，前面的所有排序都是逐个的将下一个元素插入前面已经排序了的列表中，这就比避免不了
//排序中一些较“大”的数据，开始时却在前面的数据会被进行大量的比较或移动。这是随机数据的主要
//耗时的地方。希尔排序将数据分成d组，每组的每两个相邻数据的下标之差是d。然后对每组数据进行各自的
//排序。因为每组数据的增量是d，所以数据的移动是每次d个位置。如果d取得合适，这样可以很快的将每个
//数据移动到距离自己最终位置较靠近的地方（具体靠近的程度取决于d）。然后将d逐渐减
小，继续排序。
//最后当d的值为1排序结束之后，全部的数据就排序好了。（d直接取1时，就是直接插入排序）
#include
int comp(void * d1, void * d2) {//比较函数
return (((PRedType)d1)->data - ((PRedType)d2)->data ); }
int inputList (PSqList p,int length) {//输入序列
if (p == NULL)
return P_NULL; //1，指针是空的 if (length > MAXSIZE)
return TOOBIG; //2，要输入的序列太多
int i = 0;
for (i = 0; i < length; i++)
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
int shell_insert (PSqList p,int (*comp)(void *, void *), const int d) {//以d为增量的一次排序 RedType tmp;
int i = 0; int j;
for (i = d; i < p->length ; i++) {
tmp = p->list[i]; j = i - d;
while (j >= i%d && comp(&tmp, &(p->list[j])) < 0) {
p->list[j+d] = p->list[j]; j -= d; }
p->list[j+d] = tmp; }
return OK; }//shell_insert
int shellSort (PSqList p, int (*comp)(void *, void *), const int distance[], const int t) {//希尔排序，distance数组用来给出每次排序的增量，最后一个必须为1 int i = 0;
for (i = 0; i < t; i++)
shell_insert (p, comp ,distance[i]);
return OK; }//shellSort
/*这是main.cpp文件的内容*/ #include
int main (int argc, char * argv) {
int status; PSqList test;
test = (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); }
int distance[3];
//distance[]由一些特定的增量算法确定 for (int i = 0; i < 3; i++)
distance[i] = (int)pow(2,3-i) - 1;
shellSort (test,comp, distance, 3); outputList (test);
printf(\请输入下一组待排序的数的个数(输入0结束循环)：\ }
free(test); return 0; }
//快速排序
/*这是quick_sort.h文件*/ #ifndef quick_sort
#define quick_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 comp(void * d1, void * d2); int inputList (PSqList p,int length); int outputList (PSqList p);
int quickSort (PSqList p, int (*comp)(void *, void *));
#endif
/*这是quick_sort.cpp文件*/ #include \#include
int inputList (PSqList p,int length) {//输入序列
if (p == NULL)
return P_NULL; //1，指针是空的 if (length > MAXSIZE)
return TOOBIG; //2，要输入的序列太多
int i = 0;
for (i = 0; i < length; i++)
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\