【一】需求分析
课程题目是排序算法的实现,课程设计一共要设计八种排序算法。这八种算法共包括:堆排序,归并排序,希尔排序,冒泡排序,快速排序,基数排序,折半插入排序,直接插入排序。
为了运行时的方便,将八种排序方法进行编号,其中1为堆排序,2为归并排序,3为希尔排序,4为冒泡排序,5为快速排序,6为基数排序,7为折半插入排序8为直接插入排序。
【二】概要设计
1.堆排序
⑴算法思想:堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。
⑵程序实现及核心代码的注释:
for(j=2*i+1; j<=m; j=j*2+1)
{
if(j j++; if(temp>=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为:"< output(); for(i=N/2-1; i>=0; i--) { head(i,N); } for(i=N-1; i>0; i--) { temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为:"< output(); } 2.归并排序 ⑴算法思想:先将相邻的个数为1的每两组数据进行排序合并;然后对上次归并所得到的大小为2的组进行相邻归并;如此反复,直到最后并成一组,即排好序的一组数据。 ⑵程序实现及核心代码的注释: int is2[1000]; void bin(int low,int mid,int high) { int i=low,j=mid+1,k=low; while(i<=mid&&j<=high) if(su[i]<=su[j]) // 此处为排序顺序的关键,用小于表示从小到大排序is2[k++]=su[i++]; else is2[k++]=su[j++]; while(i<=mid) is2[k++]=su[i++]; while(j<=high) is2[k++]=su[j++]; for(i=low; i<=high; i++) // 写回原数组 su[i]=is2[i]; } void g(int a,int b) { if(a { int mid=(a+b)/2; g(a,mid); g(mid+1,b); bin(a,mid,b); } } 3.希尔排序 ⑴算法思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。其中,子序列的构成 不是简单的“逐段分割”,而是将分隔某个“增量”的记录组成一个子序列。 ⑵程序实现及核心代码的注释: while(m) { m/=2; if(m!=0) { for(i=m; i if(su[i]< su[i-m]) { temp=su[i]; for(j=i-m; j>=0&&(temp su[j+m]=su[j]; su[j+m]=temp; } } } 4.冒泡排序 ⑴算法思想:1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较,并将较小的数放于两个数中较前的位置,然后将比较后的较小的数与倒数第三个进行比较,依次比较到第一个数,即可得到第一个数是所有数中最小的数;2、然后再将数组的最后一个数与倒数第二个数进行比较,并将较小的数放于两个数中较前的位置,依次比较到第二个数,3、如此循环到只剩最后两个比较,即得到排好序的一组数。 ⑵程序实现及核心代码的注释: for(i=0; i { flag=true; for(j=0; j { if(su[j]>su[j+1]) { temp=su[j]; su[j]=su[j+1]; su[j+1]=temp; flag=false; } } break; } cout<<"排序之后的数组为:"< output(); } int K; int find(int i,int j) { int temp; bool flag=true; temp=su[i]; while(i { if(flag) { while(temp<=su[j]) { j--; if(i>=j) break; } if(i>=j) break; su[i]=su[j]; while(temp>=su[i]) { i++; if(i>=j) break; } if(i>=j) break; su[j]=su[i]; } else { while(temp>=su[i]) { i++; if(i>=j) break; } su[j]=su[i]; if(i>=j) break; while(temp<=su[j]) { j--; if(i>=j) break; } su[i]=su[j]; flag=true; } } for(i=1; i { head=su[i]; for(j=0; j { if(head { for(k=i; k>j; k--) { su[k]=su[k-1]; } su[j]=head; break; } } } for(i=1; i { head=su[i]; for(j=0; j { if(head { for(k=i; k>j; k--) { su[k]=su[k-1]; } su[j]=head; break; } } } 5.快速排序 (1)任取待排序记录序列中的某个记录作为基准,按照该记录的关键字大小,将整个记录序列划分为左右两个子序列。 左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。右侧子序列中所有记录的关键字都大于基准记录的关键字。 取序列第一个记录为枢轴记录,其关键字为Pivotkey;指针low指向序列第一个记录位置(low=1),指针high指向序列最后一个记录位置(High=SeqList.Len) (2) 从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low++ (3) 从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high— 重复2、3,直到low==high,将枢轴记录放在low(high)指向的位置。 (2)程序实现及核心代码的注释: int find(int i,int j) { int temp; bool flag=true; temp=su[i]; while(i { if(flag) { while(temp<=su[j]) { j--; if(i>=j) break; } if(i>=j) break; su[i]=su[j]; while(temp>=su[i]) { i++; if(i>=j) break; } if(i>=j) break; su[j]=su[i]; flag=false; } else { while(temp>=su[i]) { i++; if(i>=j) break; } su[j]=su[i]; if(i>=j) break; while(temp<=su[j]) { j--; if(i>=j) break; } su[i]=su[j]; flag=true; } } su[i]=temp; cout<<"排完"< output(); return i; } void qsort(int low,int high) { if(low { int mid=find(low,high); qsort(low,mid-1); qsort(mid+1,high); } } 6.基数排序 (1)算法的基本思想: 基数排序是属于“分配式排序”,又称“桶子法”,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。 最高位优先法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再 对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。 (2)程序实现及核心代码的注释: for(i=0; i { if(max max=su[i]; a[H(su[i])][b[H(su[i])]++]=su[i]; } k=0; for(i=0; i<10; i++) { if(b[i]!=0) { for(j=0; j { su[k++]=a[i][j]; } } } cout<<"第一躺排序之后的数组为:"< output(); ///第二次 if(max/10==0) return ; for(i=0; i<10; i++) b[i]=0; for(i=0; i { a[HH(su[i])][b[HH(su[i])]++]=su[i]; } k=0; for(i=0; i<10; i++) { if(b[i]!=0) { for(j=0; j { su[k++]=a[i][j]; } } } cout<<"第二躺排序之后的数组为:"< output(); ///第三次 if(max/100==0) return ; for(i=0; i<10; i++) b[i]=0; for(i=0; i { a[HHH(su[i])][b[HHH(su[i])]++]=su[i]; } k=0; for(i=0; i<10; i++) { if(b[i]!=0) { for(j=0; j { su[k++]=a[i][j]; } } } 7.折半排序 ⑴算法思想:由于折半插入排序的基本操作是在一个有序表中进行查找和插入,这个“查找”操作可利用折半查找来实现,由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同,从时间上比较,这般插入排序仅减少了关键字间的 比较次数,而记录的移动次数不变。因此,这般插入排序的时间复杂度仍为O(n2)。 ⑵程序实现及核心代码的注释: for(i=1; i { temp=su[i]; low=0; high=i-1; while(low<=high) { m=(low+high)/2; if(temp high=m-1; else low=m+1; } for(j=i; j>high+1; j--) su[j]=su[j-1]; su[high+1]=temp; } 8.直接插入排序 ⑴算法思想:直接插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入到一个已排好序的有序表中,从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第二个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 ⑵程序实现及核心代码的注释: for(i=1; i { head=su[i]; for(j=0; j { if(head { for(k=i; k>j; k--) { su[k]=su[k-1]; } su[j]=head; break; } } } 【三】详细设计 程序代码: #include #include #include #include #include #define H(X) (X%10) #define HH(X) (X%100/10) #define HHH(X) (X/100) using namespace std; //int ss[10000]= {32,37,64,87,16,12,24,32}; //将要排序的数组 int ss[10000]= {372,209,53,942,547,234,645,468,7,83}; //将要排序的数组int su[10000]; //将要排序的数组 int N=10; //数组的长度 void input() //数组的输入函数 { cout<<"请输入要排序的数组的长度N:"; cin>>N; cout<<"请输入需要排序的数组:"< for(int i=0; i cin>>ss[i]; } void output() //数组的输出函数 { for(int i=0; i cout< cout< } void head(int i,int m) //堆排序的一个函数 { int j; int temp; temp=su[i]; for(j=2*i+1; j<=m; j=j*2+1) { if(j j++; if(temp>=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为:"< output(); for(i=N/2-1; i>=0; i--) { head(i,N); } for(i=N-1; i>0; i--) { temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为:"< output(); } int is2[1000]; void bing(int low,int mid,int high) { int i=low,j=mid+1,k=low; while(i<=mid&&j<=high) if(su[i]<=su[j]) // 此处为排序顺序的关键,用小于表示从小到大排序 is2[k++]=su[i++]; else is2[k++]=su[j++]; while(i<=mid) is2[k++]=su[i++]; while(j<=high) is2[k++]=su[j++]; for(i=low; i<=high; i++) // 写回原数组 su[i]=is2[i]; } void g(int a,int b) { if(a { int mid=(a+b)/2; g(a,mid); g(mid+1,b); bing(a,mid,b); } } void gbpx() //归并排序 { cout<<"排序之前的数组为:"< output(); g(0,N-1); cout<<"排序之后的数组为:"< output(); } void xepx() //希尔排序 { int i,j,temp; int m=N; cout<<"排序之前的数组为:"< output(); while(m) { m/=2; if(m!=0) { for(i=m; i if(su[i]< su[i-m]) { temp=su[i]; for(j=i-m; j>=0&&(temp su[j+m]=su[j]; su[j+m]=temp; } } } cout<<"排序之后的数组为:"< output(); } void mppx() //冒泡排序 { int i,j,k; int temp,min; bool flag; cout<<"排序之前的数组为:"< output(); for(i=0; i { flag=true; for(j=0; j { if(su[j]>su[j+1]) { temp=su[j]; su[j]=su[j+1]; su[j+1]=temp; flag=false; } } if(flag==true) break; } cout<<"排序之后的数组为:"< output(); } int K; int find(int i,int j) { int temp; bool flag=true; temp=su[i]; while(i { if(flag) { while(temp<=su[j]) { j--; if(i>=j) break; } if(i>=j) break; su[i]=su[j]; while(temp>=su[i]) { i++; if(i>=j) break; } if(i>=j) break; su[j]=su[i]; flag=false; } else { while(temp>=su[i]) { i++; if(i>=j) break; } su[j]=su[i]; if(i>=j) break; while(temp<=su[j]) { j--; if(i>=j) break; } su[i]=su[j]; flag=true; } } su[i]=temp; cout<<"排完"< output(); return i; } void qsort(int low,int high) { if(low { int mid=find(low,high); qsort(low,mid-1); qsort(mid+1,high); } } void kspx() //快速排序 { K=0; cout<<"排序之前的数组为:"< output(); qsort(0,N-1); cout<<"排序之后的数组为:"< output(); } void jspx() //基数排序 { int i,j,k; int max=0; int a[10][100]; int b[10]= {0}; cout<<"排序之前的数组为:"< output(); for(i=0; i { if(max max=su[i]; a[H(su[i])][b[H(su[i])]++]=su[i]; } k=0; for(i=0; i<10; i++) { if(b[i]!=0) { for(j=0; j { su[k++]=a[i][j]; } } } cout<<"第一躺排序之后的数组为:"< output(); ///第二次 if(max/10==0) return ; for(i=0; i<10; i++) b[i]=0; for(i=0; i { a[HH(su[i])][b[HH(su[i])]++]=su[i]; } k=0; for(i=0; i<10; i++) { if(b[i]!=0) { for(j=0; j { su[k++]=a[i][j]; } } } cout<<"第二躺排序之后的数组为:"< output(); ///第三次 if(max/100==0) return ; for(i=0; i<10; i++) b[i]=0; for(i=0; i { a[HHH(su[i])][b[HHH(su[i])]++]=su[i]; } k=0; for(i=0; i<10; i++) { if(b[i]!=0) { for(j=0; j { su[k++]=a[i][j]; } } } cout<<"第三次排序之后的数组为:"< output(); } void zbcrpx() //折半插入排序 { int i,j,k,m; int low,high,temp; cout<<"排序之前的数组为:"< output(); for(i=1; i { temp=su[i]; low=0; high=i-1; while(low<=high) { m=(low+high)/2; if(temp high=m-1; else low=m+1; } for(j=i; j>high+1; j--) su[j]=su[j-1]; su[high+1]=temp; } cout<<"排序之后的数组为:"< output(); } void zjcrpx() //直接插入排序 { int i,j,k; int temp,head; cout<<"排序之前的数组为:"< output(); for(i=1; i { head=su[i]; for(j=0; j { if(head { for(k=i; k>j; k--) { su[k]=su[k-1]; } su[j]=head; break; } } } cout<<"排序之后的数组为:"< output(); } void jiemian() { cout<<"************************************************************** ******************"< cout<<"************************************************************** ******************"< cout<<"****************************< 1: 堆排序>***************************"< cout<<"****************************< 2: 归并排序>***************************"< cout<<"****************************< 3: 希尔排序>***************************"< cout<<"****************************< 4: 冒泡排序>***************************"< cout<<"****************************< 5: 快速排序>***************************"< cout<<"****************************< 6: 基数排序>***************************"< cout<<"****************************< 7: 折半插入排序>***************************"< cout<<"****************************< 8: 直接插入排序>***************************"< cout<<"****************************< 9: 重新输入>***************************"< cout<<"****************************< 0: 退出>***************************"< 算法设计与分析基础 实验报告 应用数学学院 二零一六年六月 实验一插入排序算法 一、实验性质设计 二、实验学时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. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第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 次记录移动(赋值)的操作。而实际上, 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统,学生对象至少要包含:学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能:1.总成绩要求自动计算; 2.查询:分别给定学生学号、姓名、性别,能够查找到学生的基本信息(要求至少用两种查找算法实现); 3.排序:分别按学生的学号、成绩1、成绩2、总成绩进行排序(要求至少用两种排序算法实现)。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义,哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果,对程序进行分析。 五、算法设计 a、折半查找 设表长为n,low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时,令low=1,high=n,mid=(low+high)/2,让key与mid指向的记录比较, 若key==r[mid].key,查找成功 若key 《排序问题求解》实验报告 一、算法的基本思想 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学期 信息与软件工程学院插入排序算法实验报告
= 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); } } } Ⅳ、运行结果显示:《数据结构》实验报告——排序.docx
(完整word版)查找、排序的应用 实验报告
算法排序问题实验报告
实验报告-排序与查找