求教：数据结构几个算法问题!谢谢！(200分)

P

psky

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #1

内部排序算法比较： {严尉敏 吴伟民 《数据结构〉〉清华大学出版社 p169页 6.6}
[基本要求]
（1）对以下6种常用的内部算法进行比较：冒泡（起泡）排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不少于100;其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。
[实现提示] 主要工作是设法在已知算法重的适当位置插入对关键字的比较次数和移动系数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。
请尽量给出完整程序。谢谢！期盼。。。

 

P

psky

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #2

对了我学的是C语言版的！请用C

 

L

laoli

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #3

*冒泡排序算法*/
#define MAXITEM 100
typedef int KeyType;
typedef char ElemType[5];
typedef struct rec
{
KeyType key;
/*关键字域*/
ElemType data;
/*数据域*/
} elemnode[MAXITEM];
void bubblesort(elemnode r,int n)
{
int i,j;
for (i=1;i<=n-1;i++)
for (j=n;j>=i+1;j--)
if (r[j].key<r[j-1].key) /*比较*/
{ /*r[j]与r[j-1]进行交换*/
r[0]=r[j];
r[j]=r[j-1];
r[j-1]=r[0];
}
printf("成绩从低到高排列如下:/n");
for (i=1;i<=n;i++)
printf("%6d",r.key);
printf("/n");
for (i=1;i<=n;i++)
printf("%6s",r.data);
printf("/n");
}
main()
{
elemnode s={0," ",75,"王华",87,"李英",68,"张萍",92,"陈涛",88,"刘丽",
61,"章强",77,"孙军",96,"朱斌",80,"许伟",72,"曾亚"};
/*s[0]元素不计入元素个数*/
int n=10;
bubblesort(s,n);
}

 

L

laoli

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #4

/*直接选择排序算法*/
#define MAXITEM 100
typedef int KeyType;
typedef char ElemType[5];
typedef struct rec
{
KeyType key;
/*关键字域*/
ElemType data;
/*数据域*/
} elemnode[MAXITEM];
void selectsort(elemnode r,int n)
{
int i,j,k;
for (i=1;i<=n-1;i++)
{
k=i;
for (j=i+1;j<=n;j++)
if (r[j].key<r[k].key) k=j;
/*用k指出每趟在无序区段的最小元素*/
r[0]=r;
/*将r[k]与r交换*/
r=r[k];
r[k]=r[0];
}
printf("成绩从低到高排列如下:/n");
for (i=1;i<=n;i++)
printf("%6d",r.key);
printf("/n");
for (i=1;i<=n;i++)
printf("%6s",r.data);
printf("/n");
}
main()
{
elemnode s={0," ",75,"王华",87,"李英",68,"张萍",92,"陈涛",88,"刘丽",
61,"章强",77,"孙军",96,"朱斌",80,"许伟",72,"曾亚"};
/*s[0]元素不计入元素个数*/
int n=10;
selectsort(s,n);
}

 

L

laoli

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #5

/*快速排序算法*/
#define MAXITEM 100
typedef int KeyType;
typedef char ElemType[5];
typedef struct rec
{
KeyType key;
/*关键字域*/
ElemType data;
/*数据域*/
} elemnode[MAXITEM];
void quicksort(elemnode r,int s,int t) /*把r至r[t]的元素进行快速排序*/
{
int i=s,j=t;
r[0]=r;
while (i<j)
{
while (j>i &amp;&amp;
r[0].key<r[j].key) j--;
if (i<j)
{
r=r[j];i++;
}
while (i<j &amp;&amp;
r.key<=r[0].key) i++;
if (i<j)
{
r[j]=r;j--;
}
}
r=r[0];
if (s<i) quicksort(r,s,j-1);
if (i<t) quicksort(r,j+1,t);
}
disp(elemnode r,int n)
{
int i;
printf("成绩从低到高排列如下:/n");
for (i=1;i<=n;i++)
printf("%6d",r.key);
printf("/n");
for (i=1;i<=n;i++)
printf("%6s",r.data);
printf("/n");
}
main()
{
elemnode s={0," ",75,"王华",87,"李英",68,"张萍",92,"陈涛",88,"刘丽",
61,"章强",77,"孙军",96,"朱斌",80,"许伟",72,"曾亚"};
/*s[0]元素不计入元素个数*/
int n=10;
quicksort(s,1,n);
disp(s,n);
}

 

L

laoli

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #6

用现成的,没空改!^_^

 

C

chnplzh

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #7

家中有一本《C语言算法大全》，里面都有。你到处找找看。

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #8

樓主是不是做作業求教啊。自己去動動腦子吧。
這些排序算法及它們的分析到處能找到。

 

P

psky

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-05

• #9

是呀！~俺脑子笨，就只想用现成的！不过有机会我一定好好学习学习C。
谢谢[red]laili[/red]同志！感激。。。。

 

M

mandying

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-09

• #10

连一些基本的改进都没有，上面的排序慢得很

 

P

psky

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-10

• #11

那该怎么做？

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-09-10

• #12

http://www.csdn.net/develop/article/20/20928.shtm