数据结构
排序算法综合实验报告
姓名: xx x x
班级: 10电信1 学号: xxx 指导老师:胡圣荣
日期: 2012.12.15~2013.1.5 华南农业大学工程学院
算法基本思想:
1、插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中的适当位置,直到全部记录插入完毕为止。
(1)直接插入排序:在排序过程中,每次都讲无序区中第一条记录插入到有序区中适当位置,使其仍保持有序。初始时,取第一条记录为有序区,其他记录为无序区。显然,随着排序过程的进行,有序区不断扩大,无序区不断缩小。最终无序区变为空,有序区中包含了所有的记录,排序结束。
(2)希尔排序:将排序表分成若干组,所有相隔为某个“增量”的记录为一组,在各组进行直接插入排序;初始时增量d1较大,分组较多(每组的记录数少),以后增量逐渐减少,分组减少(每组的记录数增多),直到最后增量为1(d1>d2>...>dt=1),所有记录放为一组,再整体进行一次直接插入排序。
2、交换排序:每次比较两个待排序的记录,如果发现他们关键字的次序与排序要求相反时就交换两者的位置,直到没有反序的记录为止。
(1)冒泡排序:设想排序表R[1]到R[n]垂直放置,将每个记录R[i]看作是重量为R[i].key 的气泡;根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡违反本原则的轻气泡,就使其向上“漂浮”,如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
(2)快速排序:在待排序的n个记录中任取一个作为“基准”,将其与记录分为两组,第一组中个记录的键值均小于或等于基准的键值,第二组中个记录的键值均大于或等于基准的键值,而基准就排在这两组中间(这也是该记录的最终位置),这称为一趟快速排序(或一次划分)。对所分成的两组重复上述方法,直到所有记录都排在适当位置为止。
3、选择排序:每次从待排序的记录中选出关键字最小(或最大)的记录,顺序放在已排好序的子序列的后面(或最前),直到全部记录排序完毕。
(1)直接选择排序:首先,所有记录组成初始无序区R[1]到R[n],从中选出键值最小的记录,与无序区第一个记录R[1]交换;新的无序区为R[2]到R[n],从中再选出键值最小的记录,与无序区第一个记录R[2]交换;类似,第i趟排序时R[1]到R[i-1]是有序区,无序区为R[i]到R[n],从中选出键值最小的记录,将它与无序区第一个记录R[i]交换,R[1]到R[i]变为新的有序区。因为每趟排序都使有序区中增加一个记录,所以,进行n-1趟排序后,整个排序表就全部有序了。
(2)堆排序:利用小根堆(或大根堆)来选取当前无序区中关键字最小(或最大)的记录来实现排序的。下面介绍利用大根堆来排序。首先,将初始无序区调整为一个大根堆,输出关键字最大的堆顶记录后,将剩下的n-1个记录在重建为堆,于是便得到次小值。如此反复执行,知道全部元素输出完,从而得到一个有序序列。
4、并归排序:指将若干个已排序的子表合成一个有序表。
(1)二路并归排序:开始时,将排序表R[1]到R[n]看成n个长度为1的有序子表,把这些子表两两并归,便得到n/2个有序的子表(当n为奇数时,并归后仍是有一个长度为1的子表);然后,再把这n/2个有序的子表两两并归,如此反复,直到最后得到一个程度为n的
有序表为止。
各种排序实验结果:
实验结果原因分析和结论:
1.插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的速度。反而在这种情况下,快速排序反而慢了。
当n较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限围时,且空间允许是用桶排序。
当n较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。
当n较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下。宜用归并排序。
当n较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。
2.插入排序、冒泡排序、选择排序的时间复杂性为O(n2)
其它非线形排序的时间复杂性为O(nlog2n)
线形排序的时间复杂性为O(n);
3.在算法运行期间,运行QQ软件、360安全卫士、360杀毒、word文档、ppt、酷狗等软件会影响绝对时间和逻辑时间,使时间增大
4.随着n的取值增大,算法的实际时间增长速度逐渐增大。
5.直接插入排序(有、无监视哨)、冒泡排序(上升、下沉)、堆排序(递归、非递归)的关键字比较次数相同,但绝对时间相差比较大;直接选择排序与冒泡排序的关键字比较次数相近。
6.相比较其他同学的数据,直接插入(有、无监视哨),直接选择,冒泡(上升、下沉)的结果相差较小,希尔选择结果相差很大,另快速(递归),堆(递归,非递归),二路归并(非递归)结果并不会受计算机环境而不同。
附录:源程序极其代码
#define CPP C++
#define MPP M++
#define MP2 M+=2
#define MP3 M+=3
#include
#include
#include
#include
#include
const int maxsize=20000; //排序表容量
typedef int datatype;
typedef struct {
datatype key; //关键字域
// othertype other; //其它域
} rectype; //记录类型
typedef rectype list[maxsize+2]; //排序表类型,0号单元不用
__int64 C,M; //比较和移动次数
void check(list R,int n) { //检验排序结果
int i;
for(i=2;i<=n;i++)
if(R[i].key cout<<"Correct! "; } void disp(list R,int n) { //显示排序后的结果 int i; for(i=1;i<=n;i++) { cout< // if(i%20==0) cout< } cout< } void InsertSort1(list R,int n) {//直接插入排序,带监视哨(并不改变关键字次数) int i,j; for(i=2;i<=n;i++) { //依次插入R[2],R[3],…,R[n] if(CPP,R[i].key>=R[i-1].key) continue; //R[i]大于有序区最后一个记录,则本趟不需插入 MPP,R[0]=R[i]; //R[0]是监视哨 j=i-1; do { //查找R[i]的插入位置 MPP,R[j+1]=R[j];j--; //记录后移,继续向前搜索 } while(CPP,R[0].key MPP,R[j+1]=R[0]; //插入R[i] } } void InsertSort2(list R,int n) {//直接插入排序,无监视哨 int i,j;rectype x; //x为辅助量(用R[0]代替时间变长) for(i=2;i<=n;i++) { //进行n-1次插入 if(CPP,R[i].key>=R[i-1].key) continue; MPP,x=R[i]; //待排记录暂存到x j=i-1; do { //顺序比较和移动 MPP,R[j+1]=R[j];j--; } while(j>=1 && (CPP,x.key MPP,R[j+1]=x; //插入R[i] } } void ShellSort1(list R,int n){//一趟插入排序,h为本趟增量 int h,i,j,k; for(h=n/2;h>=1;h=h/2){ for(i=1;i<=h;i++){ //i为组号 for(j=i+h;j<=n;j+=h){ //每组从第2个记录开始插入 if(CPP,R[j].key>=R[j-h].key) continue;//R[j]大于有序区最后一个记录, //则不需要插入 MPP,R[0]=R[j]; //R[0]保存待插入记录,但不是监视哨 k=j-h; //待插记录的前一个记录 do{ //查找正确的插入位置 MPP,R[k+h]=R[k];k=k-h;//后移记录,继续向前搜索 }while(k>0&&(CPP,R[0].key MPP,R[k+h]=R[0]; //插入R[j] } } if(h==1) break; } } 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上, 算法设计与分析基础 实验报告 应用数学学院 二零一六年六月 实验一插入排序算法 一、实验性质设计 二、实验学时14学时 三、实验目的 1、掌握插入排序的方法和原理。 2、掌握java语言实现该算法的一般流程。 四、实验内容 1、数组的输入。 2、输入、输出的异常处理。 3、插入排序的算法流程。 4、运行结果的输出。 五、实验报告 Ⅰ、算法原理 从左到右扫描有序的子数组,直到遇到一个大于(或小于)等于A[n-1]的元素,然后就把A[n-1]插在该元素的前面(或后面)。 插入排序基于递归思想。 Ⅱ、书中源代码 算法InsertionSort(A[0..n-1]) //用插入排序对给定数组A[0..n-1]排序 //输入:n个可排序元素构成的一个数组A[0..n-1] //输出:非降序排列的数组A[0..n-1] for i ←1 to n-1 do v ← A[i] j ← i-1 while j ≥0and A[j] > v do A[j+1] ← A[j] j ← j-1 A[j+1] ← v Ⅲ、Java算法代码: import java.util.*; public class Charu { public static void main(String[] args) { int n = 5; int a[] = new int[n]; int s = a.length; int i = 0, j = 0, v = 0; System.out.println("请输入若干个数字:"); Scanner sc = new Scanner(System.in); try { while (i < s) { a[i] = sc.nextInt(); i++; } for (i = 1; i 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的, 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort,它的参数是一个数组A[1..n],包含了n 个待排序的数。用伪代码表示直接插入排序算法如下: InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是,通过一趟排序将待排序序列分割成独立的两部分,其中一 部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序序列为数组A[1..n],首先选取第一个数A[0],作为枢轴(pivot),然后按照下述原则重新排列其余数:将所有比A[0]大的数都排在它的位置之前,将所有比A[0]小的数都排在它的位置之后,由此以A[0]最后所在的位置i 作为分界线,将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey,则首先从high 所指位置起向前搜索,找到第一个小于pivotkey 的数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 的数,并将其移到高端,重复这两步直至low=high。最后,将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下: Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院《数据结构》实验报告——排序.docx
插入排序算法实验报告
= 0 && a[j] > v) { a[j + 1] = a[j]; j--; } a[j + 1] = v; } System.out.println("插入排序结果显示:"); for (i = 0; i < s; i++) { System.out.println(a[i]); } } catch (Exception es) { System.out.println(es); } } } Ⅳ、运行结果显示:算法排序问题实验报告
实验报告-排序与查找