算法设计与分析实验报告--排序
- 格式：doc
- 大小：233.00 KB
- 文档页数：13
计算机算法设计与分析实验报告学号：2011211773 姓名：吕功建班级：0411103实验一快速排序一、实验目的1）以排序（分类）问题为例，掌握分治法的基本设计策略。
2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法；二、算法思想基本描述分治算法思想：把规模为n的问题分成k个规模较小的子问题，且每个子问题相互独立且于原问题性质相同，递归的求解子问题，最后合并得到原问题的解。
插入算法思想：在无序的数组中，先将序列中的第一个数字看作是有序子序列，然后从第二个记录起逐个进行插入，直至将整个序列变成有序序列为止。
快速排序算法思想：快速算法是一种基于分治技术的重要排序算法，把对n个对象的排序看作是对1到n的n个整数的排序。
快速排序算法的基本思想是从中取一适合的关键字k，以k为标准把需要排序的n个对象分成两部分，一部分比k小，另一部分比k大，即：(小于k的部分)k（大于k的部分）然后对两部分分别进行快速排序，排序完毕后，简单的合并连接起来即可，算法还可递归的进行。
三、算法流程图插入排序：四、算法执行结果及分析1、生成的随机数：2、运行时间插入排序：快速排序：3、排序结果：结论：从上图中结果可见，完成2000个相同随机数的排序，插入排序的时间为5ms，而快速排序只用了1ms，之间相差4ms，而且当排序的数量增加时，快速排序用时要远远少于插入排序，由此可见，快速排序比插入排序更优。
五、实验的心得体会、经验快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。
其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。
算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。
附：算法实现代码：因为随机数的生成是在InsertionSort.java中，所以需要先运行此程序。
插入排序代码：package sort;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.FileReader;import java.io.FileWriter;import java.util.Random;import java.util.StringTokenizer;public class InsertionSort {static Random ran = new Random();static String dataPath = "D:/data.txt";static String resultsISPath = "D:/resultsIS.txt";public static void main(String[] args) throws Exception{ ceratRanNumber();int[] number = Read();int i,j;long startTime=System.currentTimeMillis(); // 排序算法开始时间for(i = 2; i < number.length; i++) {if(number[i] < number[i-1]) {number[0] = number[i];number[i] = number[i-1];}for(j = i - 2; number[0] < number[j]; j--)number[j+1] = number[j];number[j+1] = number[0];}long endTime=System.currentTimeMillis(); // 排序算法结束时间System.out.println("插入排序用时" + (endTime - startTime) + "ms");Write(number);}public static void ceratRanNumber() throws Exception{ BufferedWriter bw = new BufferedWriter(newFileWriter(dataPath));for (int i = 0; i < 2000; i++) {int t = ran.nextInt(2000);bw.write(t + " ");}System.out.println("成功生成2000个随机数，存放路径：D:/data.txt");bw.close();}public static int[] Read() throws Exception {BufferedReader br = null;StringTokenizer st = null;String temp = null;String[] a = null;int[] num = new int[2000];br = new BufferedReader(new FileReader(dataPath));while(br.ready()) {temp = br.readLine();a = temp.split(" ");}for(int i = 0; i < a.length; i++)num[i] = Integer.parseInt(a[i]);br.close();return num;}public static void Write(int[] num) throws Exception{ BufferedWriter bw = new BufferedWriter(new FileWriter(resultsISPath));for (int i = 1; i < num.length; i++) { bw.write(num[i] + " ");}System.out.print("排序结果成功写入文件D:/resultsIS.txt");bw.close();}}快速排序代码：package sort;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.FileReader;import java.io.FileWriter;import java.util.StringTokenizer;public class QuickSort {static String dataPath = "D:/data.txt";static String resultsQSPath = "D:/resultsQS.txt";public static void main(String[] args) throws Exception{ int[] number = Read();long startTime=System.currentTimeMillis(); //排序开始时间QSort(number,1,1999);long endTime=System.currentTimeMillis(); //排序结束时间System.out.println("快速排序用时" + (endTime - startTime) + "ms");Write(number);}public static int partition(int[] num , int low , int high) {num[0] = num[low];int pivoKey = num[low];while(low < high) {while(low < high && num[high] >= pivoKey)high--;num[low] = num[high];while(low < high && num[low] <= pivoKey)low++;num[high] = num[low];}num[low] = num[0];return low;}public static void QSort(int[] num, int low, int high) { if(low < high) {int pivotLoc = partition(num,low,high);QSort(num,low,pivotLoc - 1);QSort(num,pivotLoc + 1,high);}}public static int[] Read() throws Exception {BufferedReader br = null;StringTokenizer st = null;String temp = null;String[] a = null;int[] num = new int[2000];br = new BufferedReader(new FileReader(dataPath));while(br.ready()) {temp = br.readLine();a = temp.split(" ");}for(int i = 0; i < a.length; i++)num[i] = Integer.parseInt(a[i]);br.close();return num;}public static void Write(int[] num) throws Exception{ BufferedWriter bw = new BufferedWriter(new FileWriter(resultsQSPath));for (int i = 1; i < num.length; i++) {bw.write(num[i] + " ");}System.out.print("排序结果成功写入文件D:/resultsQS.txt");bw.close();}}。
