数据结构排序查找

《数据结构排序查找》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、訪妥财證曇旎信息学院《算法与数据结构》实验报告实验名称：排序与查找实验地点：实验楼423实验H期：2013-12-17一、实验目的:掌握排序和杳找的定义以及算法。二、实验设计：HeapSort(intR[],intn);/*堆排序*/Insert_Sort(intR[],intn);/*直插*/ShelISort(intR[],intn);/*希尔排序*/Quicksort(intR[],ints,intt);/*对R[s]至R[t]的元素进行快速排序*/Bubble_Sort(intR[],intn);/*冒泡排序*/SelectSort(intR[]

2、,intn);/*直接选择排序*SeqSearch(intR[],intn,intk);/*顺序查找*/BinSearch(intR[],intn,intk);/*折半查找*/三、算法图示：(―)直接插入排序直接插入排序的基本操作是将当前无序区的第1个记录R[i]插入到有序区R[0・・i-l]中适当的位置上，使R[0・・i]变为新的有序区。这种方法通常称为增量法，因为它每次使冇序区增加1个记录。(二)冒泡排序通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直金“水而”。(三)直接选择排序第i趟排序开始时，当前有

3、序区和无序区分别为R[0・・i-l]和R[i..n-1](0Wi

4、kbf•JaeI第一趟希尔排序，设增量d二5bfcacdg■JhkI第二趟希尔排序，设增量d=3aecbfdg■1hkJ第三趟希尔排序，设增量d二1abcdefgh•1jK（五）快速排序在待排序的n个记录屮任取一个记录（通常取第一个记录），把该记录放入适当位置后，数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分，所有比它大的记录放置在后一部分，并把该记录排在这两部分的中间（称为该记录归位）,这个过程称作一趟快速排序。!sR[0]eItecl•1cafg•JL）hfLowtHighlsR[0]eIt1d■1cafg•JbhfLo

5、wtHighlsR[0]eIt1d■1cafg■J1hfLowfHighIsR[0]eIt1d■1cafg■J1hfLowfHighIsR[0]eIt1d■1cafg■J1htLowtHighIsR[0]eIt1d■1cafg■J1htLowtHighIsR[0]eIt1d•cafg•J1htLowtHighIsR[0]eIt1d1cafg•J1htLowtHigh1sR[0]eIt1d1cafg•J1hfLowtHigh!sR[0]eIt1d1c1fg•J1hLowffHigh这个是一趟快速排序，第二趟时为R[l]为b,继续进行快速排序。（六）堆排序在

6、排序过程屮，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最犬（或最小）的记录。例如{6,8,7,9,0,1,3,2,4,5}（七）顺序查找从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等,则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败。查找eC•1aeh•Jfgbd第一次比较1•1aeh■Jfgbdi二1第二次比较Caehjfgbdi二1第三次比较c•11eh■Jfgbd第四次比较c■1achJfgbdi二

7、3查找成功，返回序号3.（A）折半查找折半查找要求线性表屮的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个了表，这样递归进行下去，直到找到满足条件的结点或者该线性表屮没有这样的结点。查找C匚bCdefgh■1jLow二0high=9Mid二（0+9）/2二4Tbcdefgh■1■JLow二0high二3Mid二（0+3）/2二1abJLdefgh•1•JLow=2high=3Mi

8、d二（2+3）/2二2ab□匚defgh•1•JR[2]・key=c查找成功，返