赞
踩
代码前面的声明:
#include <stdio.h> #include <stdlib.h> #include <time.h> //顺序表我是随机生成的伪随机数,引入time.h头文件 #define MAXSIZE 20 //顺序表的最大长度 #define EQ(a,b) ((a) == (b)) //a = b #define LT(a,b) ((a) < (b))//a<b #define LQ(a,b) ((a) <= (b))/a<=b /* 字符串型关键字的比较 #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b)) < 0) #define LQ(a,b) (strcmp((a),(b)) <= 0) */ typedef int KeyType;//设置关键字类型为整数类型 typedef char InfoType; typedef struct{ KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; //记录类型 typedef struct{ RedType r[MAXSIZE + 1]; //r[0]哨兵 int length; //顺序表长度 }SqList; //顺序表类型
首先创建顺序表,这里生成了20个伪随机数构成顺序表
SqList *CreateSqList(SqList *S){
S = (SqList *)malloc((MAXSIZE+1)*sizeof(SqList));
//生成20个伪随机数
long t = time(NULL); //产生一个'随机'数
srand(time(NULL));
for(int i=1; i<=20; i++){
S->r[i].key = rand() % 100; //将'随机数'范围控制在0~100
}
S->length = 20;
return S;
}
直接插入排序:
//直接插入排序
void InsertSort(SqList *L){
for(int i=2; i<= L->length; ++i){
if(LT(L->r[i].key,L->r[i-1].key)){//如果后一个元素比前一个元素小
L->r[0] = L->r[i]; //复制为哨兵
L->r[i] = L->r[i-1]; //交换位置
for(int j=i-2; LT(L->r[0].key ,L->r[j].key); --j){
L->r[j+1] = L->r[j];//再交换位置
}
L->r[j+1] = L->r[0];//插入元素,因为L-r[i].key > L->r[j].key,所以插入在 j+1的位置
}
}
}
希尔排序
希尔排序又称“缩小增量排序”
基本思想:先将整个待排序记录序列分割成若干子序列分别进行直接插入排序
,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序
就是多次执行增量逐渐减小的直接插入排序
//希尔排序
void ShellInsert(SqList *L, int dk){//dk是增量
for(int i=dk+1;i<=L->length; i++){
if(LT(L->r[i].key, L->r[i-dk].key)){//如果后面的数比前面小
L->r[0] = L->r[i]; //L->r[i]的值暂存再L->r[0]中
for(int j=i-dk; j>0&&
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。