`
gaofen100
  • 浏览: 1179946 次
文章分类
社区版块
存档分类
最新评论

数据结构 排序 选择排序

 
阅读更多

(1)简单选择排序

头文件:

#defineMAXSIZE20

#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))

typedef
intKeyType;

typedef
intInfoType;

typedef
struct...{
KeyTypekey;
InfoTypeotherinfo;
}
RedType;

typedef
struct...{
RedTyper[MAXSIZE
+1];
intlength;
}
SqList;

源文件:

#include"sort.h"

#include
"stdio.h"

voidinit(SqList&s,intw[],intn)...{
s.length
=n;
for(inti=1;i<=n;i++)...{
s.r[i].key
=w[i-1];
}

}


voidshow(SqLists)...{
for(inti=1;i<=s.length;i++)...{
printf(
"%d ",s.r[i]);
}

printf(
" ");
}


intselectMin(SqList&s,inti)...{
intkey=s.r[i].key;
intret=i;
for(intk=i;k<=s.length;k++)...{
if(key>s.r[k].key)...{
key
=s.r[k].key;
ret
=k;
}

}

returnret;
}


voidselectSort(SqList&s)...{
for(inti=1;i<=s.length;i++)...{
intj=selectMin(s,i);
if(i!=j)...{
RedTypetmp
=s.r[i];
s.r[i]
=s.r[j];
s.r[j]
=tmp;
}

}

}


voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;

SqLists;
init(s,w,n);

selectSort(s);
show(s);
}

程序运行结果:

1327384949657697
Pressanykeyto
continue

算法的复杂度为O(n * n),主要是关键字的比较。

(2)堆排序

头文件:

#defineMAXSIZE20

#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))

typedef
intKeyType;

typedef
intInfoType;

typedef
struct...{
KeyTypekey;
InfoTypeotherinfo;
}
RedType;

typedef
struct...{
RedTyper[MAXSIZE
+1];
intlength;
}
HeapType;

源文件:

#include"sort.h"
#include
"stdio.h"

voidinit(HeapType&s,intw[],intn)...{
s.length
=n;
for(inti=1;i<=n;i++)...{
s.r[i].key
=w[i-1];
}

}


voidshow(HeapTypes)...{
for(inti=1;i<=s.length;i++)...{
printf(
"%d ",s.r[i]);
}

printf(
" ");
}


//adjusttheheapfromstom,tobeamaxheap.
voidheapAdjust(HeapType&h,ints,intm)...{
RedTyperc
=h.r[s];
for(intj=2*s;j<=m;j*=2)...{
if(j<m&&LT(h.r[j].key,h.r[j+1].key))...{
j
++;
}


if(!LT(rc.key,h.r[j].key))...{
break;
}


h.r[s]
=h.r[j];
s
=j;
}

h.r[s]
=rc;
}


voidheapSort(HeapType&h)...{
//constructtheheap
for(inti=h.length/2;i>0;i--)...{
heapAdjust(h,i,h.length);
}


for(i=h.length;i>1;i--)...{
RedTyperc
=h.r[i];
h.r[i]
=h.r[1];
h.r[
1]=rc;

heapAdjust(h,
1,i-1);
}

}


voidmain()...{
intw[]=...{49,38,65,97,76,13,27,49};
intn=8;

HeapTypeh;
init(h,w,n);

heapSort(h);
show(h);
}

程序执行结果:

1327384949657697
Pressanykeyto
continue

说明:

当n较小时,不值得用heapsort;最坏情况的复杂度为O(n * log(n))。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics