数据结构学习总结算法设计---排序

数据学习总结排序的算法设计。

hi，你好啊 今天是11月4号 大概这一次真的要结束了。但学习的道路是不会停下的哦。

(1)如果一组记录的排序代码是(46、79、56、38、40、84)，则使用。

快速排序法以第一条记录为基准，得到第一次划分结果如下：

()。

38，40，46，56，79，84，

56,84

40，38，46，56，79，84，

56,79

答：C .分析:这个问题主要集中在快速排序的方法上。记得把中心点放在后卫线上，从后面找一个比中心点小的数字。从后面空出位置后，记得从前面找一个大于中心点的数字。

(11)如果一组记录的排序代码是(46、79、56、38、40、84)，则使用。

通过堆排序方法创建的初始堆是()。

79，46，56，38，40，84，

40,46

84，79，56，46，40，38，

46,38

答：B分析:根据排序代码构建一棵树，然后构建一个大根堆或一个小根堆进行排序。

(1)让要排序的关键字序列为{12，2，16，30，28，10，16*，20，

6，18}，试着用下面的排序方法写出每次排序后的关键词序列。

列的状态。

直接插入排序。

二进制插入排序[mid=(低高)/2]。

希尔排序(增量5、3、1)。

气泡排序。

快速分拣(重点掌握 注意掌握方法)

简单的选择排序。

堆排序

双向合并排序。

(3)输入文件(101，51，19，61，3，71，31，17，19，100，

55,20,9,30,50,6,90);当k=6时，使用替换选择算法进行写入。

生成建立的初始失败树和生成的初始合并段。

初始合并段：r1:3，19，31，51，61，71，100，101。

R2:9，17，19，20，30，50，55，90

R3:6

算法

(1)尝试使用单一链表作为存储结构，实现简单的排序算法。

`[算法描述]:

void LinkedListSelectSort(链接列表头)

//该算法在一次行程中找出关键字最小的节点，其数据与当前节点进行交换。要交换指针，必须写下当前节点和最小节点的前任指针。

p=head-next；

while(p！=null)

{ q=p-next；r=p；//让r成为指向具有最小关键字的节点的指针。

while (q！=null)

{ if(q-datar-data)r=q；

q :=q-next；

}

if(r！=p)r-数据-p-数据；

p=p-next；}`

(2)前导节点的双向链表中存储有n条记录，目前按双向冒泡排序。

按升序排序，请写出这种排序的算法。(注：双向冒泡。

也就是说，两个相邻的分拣行程以相反的方向冒泡)。

` typedef结构节点

{ ElemType数据；

结构节点*上一个，*下一个；

}节点，* DLinkedList

无效双向气泡起始(DLinkedList la)

//对头节点双向链表la中存储的元素进行双向发泡行。

前言。

{ int exchange=1；//设置标记。

dlinkdlistp，temp，tail

Head=la //双链表的头，在算法过程中向下冒泡。

起始节点

tail=null//在双链表的末尾，是算法过程中向上冒泡。

起始节点

while(交换)

{ p=head-next；//p是指向当前节点的工作指针。

exchange=0；//假设这次旅行没有兑换。

while (p-next！=尾部)//向下冒泡(右)，一趟最多。

元素下沉。

If (p-datap-next-data) //交换两个节点的指针，涉及六个。

链条

{ temp=p-next；exchange=1；//有一个交换。

p-next=temp-next；temp-next-previous=p//首先列出链表中的节点。

上上下下。

temp-next=p；p-pre-next=temp；//将temp插入p。

在节点之前

temp-pre=p-pre；prior=temp

}

否则p=p-next；//没有交换，指针向后移动。

tail=p；//准备冒泡。

p=尾部优先；

while(交换p-pre！=head)

//向上冒泡(左)，一趟就出来一个最小元素。

if(p-data p-pre-data)//交换两个节点。

针，涉及6条链。

{ temp=p-previous；exchange=1；//有一个交换。

p-pre=temp-pre；temp-pre-next=p；

//首先从链表中删除临时节点。

temp-pre=p；p-next-previor=temp；//将temp插入p节点。

后(右)

temp-next=p-next；p-next=temp；

}

否则p=p-previous；//无交换，指针前移。

head=p；//准备向下冒泡。

}//while(交换)

}//算法结束`。

(5)借助快速排序算法，在一组无序记录中找到给定的级别。

键值等于键的记录。让这组记录存储在数组r[l.n]。Ruocha

如果搜索成功，输出记录在R数组中的位置和值；否则，显示“不”。

查找”信息。请简要说明算法思路，写出算法。分析:把要检查的记录作为支点，从后到前依次进行比较。如果它们小于枢轴，

轴，从前到后，直到搜索成功返回到其位置或未能返回到0。

` int索引(RectType R[]，int l，h，数据类型键)

{int i=l，j=h；

while (ij)

{ while (i=j R[j])。key key)j-；

if (R[j].key==key)返回j；

而(i=j R[i]。key key)I；

if (R[i]。key==key)返回I；

}

cout“未找到”；返回0；

}//索引`

现在时22时54分 你今天过的开心吗如果不开心记得早点睡觉 明天醒来又是活力满满的一天哦 我也要勇敢的奔赴考研的战场了。加油