基于java数据结构实验 快速排序,归并排序,堆排)
//Sort.bubbleSort(arr1);
//Sort.quickSort(arr1);
Sort.SelectSort(arr1);
//Sort.heapsort(arr1);
//print(arr1);
//Sort.mergesort(arr1);
}
1.1题运行结果：
实验总结（结论或问题分析）：
掌握了各种排序方法的原理以及算法实现，但各种算法各有优劣，在运用是要选者合适的算法。
实验成绩任课教师签名
附：源程序：
希尔排序：
public static void shellsort(int[] ins) {
int n = ins.length;
int gap = n/2;
while(gap > 0){
for(int j = gap; j < n; j++){
int i=j;
int temp;
while(i >= gap && ins[i-gap] > ins[i]){
temp = ins[i-gap]+ins[i];
ins[i-gap] = temp-ins[i-gap];
ins[i] = temp-ins[i-gap];
i -= gap;
}
}
gap = gap/2;
}
}
快排：
public static void quicksort(int[] arr,int left,int right) { if (left>=right) {
return;
}
int key=arr[left];
int i=left;
int j=right;
while(i while(key j--; } while(key>arr[i]&&i i++; } if (i int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } arr[left]=arr[i]; arr[i]=key; quicksort(arr, left, i-1); quicksort(arr, i+1, right); } 归并排序： public static void merge(int[] arr,int left,int mid,int right) { int[] temp=new int[arr.length]; int p1=left,p2=mid+1,k=left; while (p1<=mid&&p2<=right) { if(arr[p1]<=arr[p2]) { temp[k++]=arr[p1++]; } else { temp[k++]=arr[p2++]; } } while(p1<=mid) { temp[k++]=arr[p1++]; } while(p2<=right) { temp[k++]=arr[p2++]; } for (int i = left; i <= right; i++) { arr[i]=temp[i]; } } public static void mergesort(int [] arr,int start,int end){ if(start int mid=(start+end)/2;//划分子序列 mergesort(arr, start, mid);//对左侧子序列进行递归排序 mergesort(arr, mid+1, end);//对右侧子序列进行递归排序 merge(arr, start, mid, end);//合并 } } import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; public class GuiBing { public static void main(String[] args) throws Exception { int datalength=1000000; GuiBing gui=new GuiBing(); int[] array1=gui.createArray(datalength); int[] array2=gui.createArray(datalength); Thread.sleep(20000); long startTime = System.nanoTime();//纳秒精度 long begin_freeMemory=Runtime.getRuntime().freeMemory(); int[] final_array=gui.guibing(array1,array2); boolean result=gui.testResult(final_array); long end_freeMemory=Runtime.getRuntime().freeMemory(); System.out.println("result===="+result); long estimatedTime = System.nanoTime() - startTime; System.out.println("elapsed time(纳秒精 度):"+estimatedTime/100000000.0); System.out.println("allocated memory:"+(begin_freeMemory-end_freeMemory)/1000.0+" KB"); Thread.sleep(20000); } /** * 显示数组的内容 * @param array */ private static void dispalyData(int[] array) { for(int i=0;i 归并排序算法实现（迭代和递归）\递归实现归并排序的原理如下： 递归分割: 递归到达底部后排序返回: 最终实现排序： #include } while(i 实验名称归并排序分治策略的设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室I 实验操作 实验台号班级姓名实验结果 一、实验目的 1、熟悉分治法求解问题的抽象控制策略； 2、熟悉在顺序存储表示下求解分类问题的递归算法设计； 3、通过实例转换, 掌握分治法应用。 二、实验任务 ①从文件中读取数据信息； ②利用归并排序算法，进行排序； ③输出排序结果。 三、实验设计方案 1、结构体设计 用数组存放排序数据。 2、自定义函数设计 ①函数原型声明 int input(int A[]); //从文件读入待排序的数据 void merge(int A[],int low,int mid,int high); // 两个相邻有序数组的归并 void mergesort(int A[],int low,int high); // 归并排序 void input(int A[], int n); // 输出排序结果 ②两个相邻的有序子数组的合并 思路：从两个已排好序的子数组的首元素开始，依次比较大小，按从小到大的顺序存放在b[]数组中，然后转存到A[]数组中。 void merge(int A[],int low,int mid,int high) { int b[N]; int i,j,k = 0; int l = low; //已排序部分1的起始下标 int h = mid+1; //已排序部分2的起始下标 while(l <= mid && h <= high) //两个有序部分合并到b数组中 if(A[l] < A[h]) b[k++] = A[l++]; else 大连理工大学实验预习报告 学院（系）：电信专业：班级： 姓名：学号：组：___ 实验时间：实验室：实验台： 指导教师签字：成绩： 实验名称Merge sort 一、实验目的和要求 (一)、实验目的 Design the merge sort algorithm and implement it in C language 设计归并排序算法并于C语言实现。 (二)、实验要求 Requirements: 1) Analyze the time complexity of your algorithm 2) Submit the document explaining your algorithm as well as the source code. 要求： 1)分析算法的时间复杂度。 2) 提交的文档中说明你的算法和源代码。 二、实验原理 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可 解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？ 可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 关于多路归并排序外部排序败者树技术积累2009-11-24 21:52:06 阅读453 评论0 字号：大中小 编程珠玑第一个case是有关一个技巧性解决外部排序问题的。问题很巧妙的解决了，但一开始提到的利用归并排序进行外部排序的算法仍值得仔细探究一下，毕竟本科时学的不是很深入。 先来看内部排序中最简单的2路归并排序算法。 算法核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，给定数组中序列界限i、m、n，用2个下标变量分别从i和j=m+1开始逐个往后处理，先比较，小的写到结果序列的当前遍历下标k中，相应下标自增继续比较直到某个序列的下标走到边界，再将另外一个序列的剩余元素拷贝到结果序列中。 算法可用递归或递推实现，从相邻的两两元素开始不断调用上面的核心操作组成较长有序序列直到完成整个序列。 算法进行一趟归并就得到一个局部有序的完整新序列，n个元素共需要log2n趟归并，每趟完成比较操作n次（1次得到序列的1个值），得到的新序列写到结果序列空间中，下一趟之前要先将结果序列复制一份到临时空间，下一趟归并在临时空间上进行。因此时间复杂度nlog2n，空间上除了原始序列空间n、结果序列空间n，还需要辅助临时空间n。 接下来看外部排序。外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。 多路归并排序算法在常见数据结构书中都有涉及。从2路到多路（k路），增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次，为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)，也即(向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(向上取整)(log2k)次使总比较次数为(向上取整)(log2m)(n-1)，与k无关。 败者树是完全二叉树，因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k-1]为比较结点，ls[k]--ls[2k-1]为叶子结点（同时用另外一个指针索引b[0]--b[k-1]指向）。另外bk为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。 多路归并排序算法的过程大致为：首先将k个归并段中的首元素关键字依次存入 篇一：归并排序与快速排序实验报告 一、实验内容： 对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。 二、所用算法的基本思想及复杂度分析： 1、归并排序 1）基本思想：运用分治法，其分治策略为： ①划分：将待排序列 r1,r2,……,rn划分为两个长度相等的子序列 r1,……,rn/2和rn/2+1,……,rn。 ②求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。 ③合并：将这两个有序子序列合并成一个有序子序列。 2）复杂度分析： 二路归并排序的时间代价是o(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性o(n)。 2、快速排序： 1）基本思想：运用分治法，其分治策略为： ①划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列 r1……ri-1和ri+1……rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。 ②求解子问题：分别对划分后的每一个子序列递归处理。 ③合并：由于对子序列r1……ri-1和ri+1……rn的排序是就地进行的，所以合并不需要执行任何操作。 2）复杂度分析： 快速排序在平均时间复杂性是o(nlog2n)。最坏的情况下是o(n^2)。 三、源程序及注释： 1、归并排序 #include<iostream> #include<fstream> #include windows.h using namespace std; void merge(int r[],int r1[],int s,int m,int t ) } int mergesort(int r[],int r1[],int s,int t) { } void main() int i=s; int j=m+1; int k=s; while(i<=m&&j<=t) {} if(i<=m)while(i<=m) r1[k++]=r[i++];//第一个没处理完，进行收尾if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小的放入r1[k]中else r1[k++]=r[j++]; else while(j<=t) r1[k++]=r[j++];//第二个没处理完，进行收尾for(int l=0;l<k;l++) { } r[l]=r1[l];//将合并完成后的r1[]序列送回r[]中if(s==t)r1[s]=r[s]; else{int m; m=(s+t)/2; mergesort(r,r1,s,m);//归并排序前半个子序列 mergesort(r,r1,m+1,t); //归并排序后半个子序列 merge(r1,r,s,m,t);//合并两个已排序的子序列 }return 0; int a[100000]; int a1[10000]; 归并排序算法的基本思想及算法实现示例 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 两路归并算法 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。 （1）合并过程 合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。 （2）动态申请R1 实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。 2、归并算法 void Merge(SeqList R，int low，int m，int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 //子文件R[low..high] int i=low，j=m+1，p=0；//置初始值 RecType *R1；//R1是局部向量，若p定义为此类型指针速度更快 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))； if(! R1) //申请空间失败 Error("Insufficient memory available!")； while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]； while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]； for(p=0，i=low；i<=high；p++，i++) R=R1[p]；//归并完成后将结果复制回R[low..high] } //Merge 归并排序 归并排序有两种实现方法：自底向上和自顶向下。 package com.igo.util.file; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; import org.slf4j.Logger; /** * * 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存， * 需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。* 外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分， * 分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。* @author ZhaoWeikai * Company: * 2010-12-23 下午02:25:00 */ public class MergeSort { private static final Logger log = org.slf4j.LoggerFactory.getLogger(MergeSort.class); /** 拆分大小, 单位:行*/ private static int SPLIT_SIZE = 100000; public static void main(String[] args) throws Exception { List #include 归并排序算法解决排序问题 目录 1引言 (2) 2.归并排序的基本思想 (2) 3.归并排序算法不同的方式 (3) 1.归并排序基本算法 (3) 1.实现过程 (3) 2.性能分析： (4) 2.递归二路归并排序 (5) 1.算法过程 (5) 2.性能分析： (6) 3.归并排序算法的改进算法 (7) 1.引理 (7) 2.应用例子 (7) 3.时间复杂性的分析 (8) 4.总结 (9) 5.参考文献 (9) 1引言 从归并排序的概念上进行分析，该算法的思想比较容易理解，并且也能够直观的感知其实质是利用存储空间的归并。在实现的过程中，可以有多种方法，画出归并过程示意图后，随即可以得出其算法的代码。但是我们在利用递归思想实现归并排序的教学程中，一定要让学生分清是用递归还是用回归进行的归并，画出图形区分这两种不同的归并过程。通过这一环节，我们不但能够理解稳定的归并排序，而且还让学生认清递归和回归是解决这一问题两种不同的操作过程。 2.归并排序的基本思想 归并排序主要是二路归并排序，它的基本思想是：设n个数据，初始时把他们看成n 个长度为l的有序子数组，然后从第—个子数组开始，把相邻的子数组两两归并，得到n／2个长度为2的新的有序子数组(当n为奇数是最后—个新的有序子数组长度为1)；对这些新的有序子数组再两两归并；如此重复，直到得到—个长度为n的有序数组为止”。归并排序有两种实现方法：自顶向下和自底向上，前者定义是自底向上， 3.归并排序算法不同的方式 1.归并排序基本算法 1.实现过程 当初次理解归并概念的时候，我们可以列举下列一组数据的归并过程。例如：70 83 100 65 10 32 7 65 9 第一次：【70 83】【65 100】【10 32】【7 65】【9】 第二次：【65 70 83 100】【7 10 32 65】【9】 第三次：【7 10 32 65 65 70 83 100】【9】 第四次：【7 9 10 32 65 65 70 83 100】 具体程序代码如下： 函数：void merge(int e[]，int n) 形参说明：e是已知待排序的数组，n是数组中元素的个数，下标从0开始。void merge(int e[]，int n) { int +p=(int+)malloc(Sizeof(int)+n)；／*开辟一块实现交替归并空间*／ int len=l，f=0；／*len为归并单元宽度，f是一个标识，实现交替归并*／while(1en 算法设计与分析实验报告 实验名称分治法实现归并排序算法评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 then mid←， //求这个集合的分割点// call MERGESORT(low，mid) //将一个子集合排序// call MERGESORT(mid+1，high) //将另一个子集合排序 call MERGE(low，mid，high) //归并两个已排序的子集合// endif end MERGESORT 归并两个已排序的集合 procedure MERGE(low，mid，high) //A(low：high)是一个全程数组// //辅助数组B(low；high)// integer h，i，j，k； h←low；i←low；j←mid+1； while h≤mid and j≤high do //当两个集合都没取尽时// if A(h)≤A(j) then B(i) ←A(h)；h←h+1 else B(i) ←A(j)；j←j+1 endif i←i+1 repeat if h>mid then for k←j to high do //处理剩余的元素// B(i) ←A(k)；i←i+1 repeat else for k←h to mid do B(i) ←A(k)；i←i+1 repeat endif 将已归并的集合复制到A end MERGE 2. 快速排序算法 QuickSort(p,q) //将数组A[1:n]中的元素 A[p], A[p+1], , A[q]按不降次序排列， 并假定A[n+1]是一个确定的、且大于 A[1:n]中所有的数。// int p,q; global n, A[1:n]; if p 归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为： 1）划分子表 2）合并半子表 首先我们来讨论归并算法，归并算法将一系列数据放到一个向量中，索引范围为[first,last],这个序列由两个排好序的子表构成，以索引终点（mid）为分界线，以下面一个序列为例 7，10，19，25，12，17，21，30，48 这样的一个序列中，分为两个子序列 7,10,19,25 和 12,17,21,30,48，如下图所示： 再使用归并算法的时候的步骤如下： 第一步：比较v[indexA]=7和v[indexB]=12,将较小的v[indexA]取出来放到临时向量tempArray中，然后indexA加1 第二步：比较v[indexA]=10和v[indexB]=12,将较小的10放到临时变量tempArray中，然后indexA++; 第三步：比较v[indexA]=19与v[indexB]=12，将较小的12存放到临时变量tempArray中，然后indexB++; 第四步到第七步：按照以上规则，进行比对和存储，得到如下结果： 最后一步：将子表b中剩余项添加到临时向量tempArray中 然后将临时变量中的值按照索引位置，拷贝回向量v中，就完成了对向量v 的归并排序 Java实现代码： package com.sort.merge; public class Merge { /** * 分治法,自顶向下，递归分割数组，最终归并 */ public static void merge(int[] arr,int start,int end){ if(start 算法导论第一次上机报告 班级：1403018姓名：张可心学号：14030188030 （一）题目一 一、问题 Design aΘ(n lg n)-time algorithm that,given a set S of n integers and another integer x,determines whether or not there exist two elements in S whose sum is exactly x. 二、问题分析 集合S中有n个整数，给定一个整数x,设计一个算法，求出S中是否有两个元素相加之和为x。首先采用归并排序算法，复杂度为nlg n。再设计算法进行查找。 三、算法伪代码 merge(A,beg1,mid,end1) n1=mid-beg1+1 n2=end1-mid let A1[1..n1+1]andA2[1..n2+1]be new arrays for i=1to n1 A1[i]=A[beg1+i-1] for j=1to n2 A2[j]=A[mid+j] A1[n1+1]=∞ A2[n2+1]=∞ i=1j=1 for k=beg1to end1 if A1[i]≤A2[j] A[k]=A1[i] i=i+1else A[k]=A2[j] j=j+1 merge_sort(A,beg1,end1) if beg1