排的数是1000，但把maxsize改成1000就会中断
#include<stdio.h>#include<stdlib.h>
#include<time.h>
#define MAXSIZE 2000
typedef int KeyType;
typedef struct{
KeyType key;
}DataType;
typedef struct{
DataType r;
int length;
}Sqlist;
typedef struct{
int count ,assign ;//记录比较次数，赋值次数
}ca;
int quickcount = 0;
int quickassign = 0;
int mergecount = 0;
Sqlist Init_Sqlist(void)
{
Sqlist *s;
s = (Sqlist *)malloc(sizeof(Sqlist));
if (s){
s->length = 0;
}
return *s;
}
//创建1000个随机数
Sqlist CreateSqlist(Sqlist s)
{
int i;
srand((unsigned int)time(NULL));//设置当前时间为种子
for (i = 1; i <= 1000; i++){
s.r.key = rand() % 9999+ 1;
s.length++;
}
for(i = 1;i<=1000;i++){
printf("%d ",s.r.key);
if(i%10==0){
printf("\n");
}
}
//printf("%d ",s.length);
printf("\n");
return s;
}
//直接排序
ca StraightInsertSort(Sqlist s)
{
ca cishu;
cishu.assign = 0;
cishu.count = 0;
int i, j;
for (i = 2; i <= s.length; i++){
s.r = s.r;
cishu.assign++;
j = i - 1;
while (s.r.key<s.r.key){
s.r = s.r;
cishu.assign++;
j--;
cishu.count++;
}
s.r = s.r;//数值插入
cishu.assign++;
}
return cishu;
}
//冒泡排序
ca BubbleSort(Sqlist s)
{
ca cishu;
int i, j;
cishu.count = 0;
cishu.assign = 0;
for (i = 1; i <= s.length - 1; i++){
for (j = 2; j <= 1 + s.length - i; j++,cishu.count++){
if (s.r.key<s.r.key){
//数值交换取最大数
s.r = s.r;
s.r = s.r;
s.r = s.r;
cishu.assign = cishu.assign + 3;
}
}
}
return cishu;
}
//希尔排序
ca ShellInsert(Sqlist *s, int gap)
{ //一趟增量为gap的插入排序，gap为步长
int i, j;
ca cishu;
cishu.assign = 0;
cishu.count = 0;
for (i = gap + 1; i <= s->length; i++,cishu.count++){
if (s->r.key<s->r.key)
{ //小于时将人插入有序表
cishu.count++;
s->r = s->r;
cishu.assign++;
for (j = i - gap; j>0 && s->r.key<s->r.key; j = j - gap,cishu.count++){
s->r = s->r;
cishu.assign++;
}
s->r = s->r;
cishu.assign++;
}
}
return cishu;
}
ca ShellSort(Sqlist s, int gaps[], int t)
{ //按增量序列gaps[],对序列表s做希尔排序
int k, count = { 0 }, assign = { 0 };
ca cishu;
cishu.count = 0;
cishu.assign = 0;
for (k = 0; k<t; k++){
cishu = ShellInsert(&s, gaps); //一趟增量为gaps的插入排序，同时将赋值，比较次数纪录
count = cishu.count;
assign = cishu.assign;
}
cishu.count= count + count + count;
cishu.assign = assign+assign+assign;
return cishu;
}
//快速排序
intQuickSort1(Sqlist *S, int low, int high)
{
KeyType pivotkey;
S->r = S->r; //以子表的第一个记录作为轴值记录
pivotkey = S->r.key; //取轴值记录关键字
while (low<high) //从表的两端交替地向中间扫描
{
while (low<high&&S->r.key >= pivotkey){
quickcount++;
high--;
}
if (low<high){
S->r = S->r;
quickassign++;
}
while (low<high&&S->r.key <= pivotkey) {
quickcount++;
low++;
}
if (low<high)
S->r = S->r; //将比轴值记录大的交换到高端
quickassign++;
}
S->r = S->r; //轴值（支点）记录到位
quickassign++;
return low; //返回轴值（支点）记录所在位置
}
voidQuickSort(Sqlist *s, int low, int high)
{
int pivotloc;
if (low<high)
{
pivotloc = QuickSort1(s, low, high);
QuickSort(s, low, pivotloc - 1);
QuickSort(s, pivotloc + 1, high);
}
}
//归并排序
void Merge(DataType r[], DataType rf[], int u, int v, int t)
{//将有序的r和r归并为有序的rf
inti, j, k;
ca cishu;
cishu.assign = 0;
cishu.count = 0;
for (i = u, j = v + 1, k = u; i <= v&&j <= t; k++)//将r中记录由小到大并到rf
if (r.key <= r.key){
cishu.count++;
rf = r;
cishu.assign++;
}
else{
cishu.count++;
rf = r;
cishu.assign++;
}
while (i <= v) //将剩余的r复制到rf
rf = r;
cishu.assign++;
while (j <= t) //将剩余的复制到rf
rf = r;
cishu.count++;
}
voidMsort(DataType p1[], DataType p2[], int n, int l)
{ //将p归并为p1
int i = 1, j;
while (i + 2 * l - 1 <= n)
{
Merge(p1, p2, i, i + l - 1, i + 2 * l - 1);
i = i + 2 * l;
}
if (i + l <= n)
Merge(p1, p2, i, i + l - 1, n);
else
for (j = i; j <= n; j++)
p2 = p1;
}
voidMergeSort(Sqlist s)
{
intl = 1;
DataTyperf;
while (l <= 1000)
{
Msort(s.r, rf, s.length, l);
l = l * 2;
Msort(rf, s.r, s.length, l);
l = l * 2;
}
}
//选择排序
ca Selectionsort(Sqlist s){
int i ,j;
ca cishu;
cishu.count = 0;
cishu.assign = 0;
for (i = 1; i <= s.length - 1; i++) //作s.lengh-1次选取
{
for (j = i+1; j <= s.length - 1; j++) //在i开始的待排序记录中选关键字最小的记录
{
cishu.count++;
if (s.r.key < s.r.key){
s.r = s.r;
s.r = s.r;
s.r = s.r; //关键字最小的与第i条交换
cishu.assign = cishu.assign + 3;
}
}
}
return cishu ;
}
ca Heapadjust(Sqlist *s, int n, int m)
{ //S->r中的记录关键字r外均满足堆的定义，将对第n个结点为根的子树筛选，使其成为大顶堆
int i, j;
ca cishu;
cishu.count = 0;
cishu.assign = 0;
DataType rc;
rc = s->r;
cishu.count++;
i = n;
for (j = 2 * i; j <= m; j = j * 2)//沿关键字较大的孩子结点向下筛选
{
if (j < m&&s->r.key < s->r.key)
{
cishu.count++;
j = j + 1; //关键字较大的原素下标
}
if (rc.key>s->r.key)//rc应插在位置i上
{
cishu.count++;
break;
}
s->r = s->r;
cishu.assign++;
i = j; //使i结点满足堆定义
}
s->r = rc;
cishu.assign++;
return cishu;
}
ca Heapsort(Sqlist *s)
{
int i;
ca cishu1;
ca cishu2;
cishu2.count = 0;
cishu2.assign = 0;
for (i = s->length / 2; i > 0; i--)//将r建成堆
cishu1=Heapadjust(s, i, s->length);
cishu2.count += cishu1.count;
cishu2.assign += cishu1.assign;
for (i = s->length; i > 1; i--)//将堆顶元素与堆底元素交换，将最大的元素移到后面
{
s->r = s->r;
s->r = s->r;
s->r = s->r;
cishu2.assign += 3;
cishu1=Heapadjust(s, 1, i - 1); //将人重新调整为堆
cishu2.count += cishu1.count;
cishu2.assign += cishu1.assign;
}
return cishu2;
}
int main()
{
Sqlist S, SL;
ca cishu;
intgaps = { 5, 3, 1 };
int n = 1, m = 1000;
S = Init_Sqlist();
SL = CreateSqlist(S);
cishu = StraightInsertSort(SL); //直接插入法排序
printf("直接插入排序比较次数：%d\n", cishu.count);
printf("直接插入排序赋值次数：%d\n", cishu.assign);
cishu = BubbleSort(SL); //冒泡排序
printf("冒泡排序比较次数： %d\n", cishu.count);
printf("冒泡排序赋值次数: %d\n", cishu.assign);
cishu = ShellSort(SL, gaps, 3); //希尔排序
printf("希尔排序比较次数： %d\n", cishu.count);
printf("希尔排序赋值次数： %d\n", cishu.assign);
MergeSort(SL); //归并排序
printf("归并排序比较次数： %d\n", cishu.count);
printf("归并排序赋值次数： %d\n", cishu.assign);
cishu = Selectionsort(SL); //选择排序
printf("选择排序比较次数： %d\n", cishu.count);
printf("选择排序赋值次数: %d\n", cishu.assign);
cishu=Heapsort(&SL); //堆排序
printf("堆排序比较次数: %d\n", cishu.count);
printf("堆排序赋值次数: %d\n", cishu.assign);
QuickSort(&SL, 1, SL.length); //快速排序
printf("快速排序比较次数： %d\n", quickcount);
printf("快速排序赋值次数： %d\n", quickassign);
system("pause");
}
maxsize的定义是怎么决定的
看了下。我想应该跟
//创建1000个随机数
有关吧
#define MAXSIZE 2000 应该要大于1000个随机数
页:
[1]