算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-排序

計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告學(xué)號(hào)：2011211773姓名：呂功建班級(jí)：0411103實(shí)驗(yàn)一快速排序一、實(shí)驗(yàn)?zāi)康?）以排序（分類）問題為例，掌握分治法的基本設(shè)計(jì)策略。2）熟練掌握一般插入排序算法的實(shí)現(xiàn)；3）熟練掌握快速排序算法的實(shí)現(xiàn)；4)理解常見的算法經(jīng)驗(yàn)分析方法；二、算法思想基本描述分治算法思想：把規(guī)模為n的問題分成k個(gè)規(guī)模較小的子問題，且每個(gè)子問題相互獨(dú)立且于原問題性質(zhì)相同，遞歸的求解子問題，最后合并得到原問題的解。插入算法思想：在無序的數(shù)組中，先將序列中的第一個(gè)數(shù)字看作是有序子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至將整個(gè)序列變成有序序列為止。 快速排序算法思想：快速算法是一種基于分治技術(shù)的重要排序算法，把對(duì)n個(gè)對(duì)象的排序看作是對(duì)1到n的n個(gè)整數(shù)的排序?？焖倥判蛩惴ǖ幕舅枷胧菑闹腥∫贿m合的關(guān)鍵字k，以k為標(biāo)準(zhǔn)把需要排序的n個(gè)對(duì)象分成兩部分，一部分比k小，另一部分比k大，即：(小于k的部分)k（大于k的部分）然后對(duì)兩部分分別進(jìn)行快速排序，排序完畢后，簡單的合并連接起來即可，算法還可遞歸的進(jìn)行。三、算法流程圖插入排序：number[0]=number[i];number[i]=number[i-1];循環(huán)開始number[0]>number[j]？？number[0]=number[i];number[i]=number[i-1];循環(huán)開始number[0]>number[j]？？開始Number[j+1]與number[j]交換j--循環(huán)是否結(jié)束Number[0]與number[j]交換 否是Number[j+1]與number[j]交換j--循環(huán)是否結(jié)束Number[0]與number[j]交換結(jié)束否 是結(jié)束四、算法執(zhí)行結(jié)果及分析1、生成的隨機(jī)數(shù)：2、運(yùn)行時(shí)間插入排序：快速排序：3、排序結(jié)果：結(jié)論：從上圖中結(jié)果可見，完成2000個(gè)相同隨機(jī)數(shù)的排序，插入排序的時(shí)間為5ms，而快速排序只用了1ms，之間相差4ms，而且當(dāng)排序的數(shù)量增加時(shí)，快速排序用時(shí)要遠(yuǎn)遠(yuǎn)少于插入排序，由此可見，快速排序比插入排序更優(yōu)。五、實(shí)驗(yàn)的心得體會(huì)、經(jīng)驗(yàn)

快速排序的運(yùn)行時(shí)間與劃分是否對(duì)稱有關(guān)，其最壞情況發(fā)生在劃分過程中產(chǎn)生的兩個(gè)區(qū)域分別包含n-1個(gè)元素和1個(gè)元素的時(shí)候。其算法的時(shí)間復(fù)雜度為O(n2),在最好的情況下每次劃分的基準(zhǔn)恰好為中值，可得其算法時(shí)間復(fù)雜度為O(n㏒n)。 算法的實(shí)現(xiàn)和理解和代碼實(shí)現(xiàn)完全是兩回事，想要完全掌握一種算法，需要?jiǎng)邮謱?shí)踐，用代碼實(shí)現(xiàn)，才能理解透徹，真正掌握。附：算法實(shí)現(xiàn)代碼：因?yàn)殡S機(jī)數(shù)的生成是在InsertionSort.java中，所以需要先運(yùn)行此程序。插入排序代碼：packagesort;importjava.io.BufferedReader;importjava.io.BufferedWriter;importjava.io.FileReader;importjava.io.FileWriter;importjava.util.Random;importjava.util.StringTokenizer;publicclassInsertionSort{ staticRandomran=newRandom(); staticStringdataPath="D:/data.txt"; staticStringresultsISPath="D:/resultsIS.txt"; publicstaticvoidmain(String[]args)throwsException{ ceratRanNumber(); int[]number=Read(); inti,j; longstartTime=System.currentTimeMillis();//排序算法開始時(shí)間 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]; } longendTime=System.currentTimeMillis();//排序算法結(jié)束時(shí)間 System.out.println("插入排序用時(shí)"+(endTime-startTime)+"ms"); Write(number); } publicstaticvoidceratRanNumber()throwsException{ BufferedWriterbw=newBufferedWriter(newFileWriter(dataPath)); for(inti=0;i<2000;i++){ intt=ran.nextInt(2000); bw.write(t+""); } System.out.println("成功生成2000個(gè)隨機(jī)數(shù)，存放路徑：D:/data.txt"); bw.close(); } publicstaticint[]Read()throwsException{ BufferedReaderbr=null; StringTokenizerst=null; Stringtemp=null; String[]a=null; int[]num=newint[2000]; br=newBufferedReader(newFileReader(dataPath)); while(br.ready()){ temp=br.readLine(); a=temp.split(""); } for(inti=0;i<a.length;i++) num[i]=Integer.parseInt(a[i]); br.close(); returnnum; } publicstaticvoidWrite(int[]num)throwsException{ BufferedWriterbw=newBufferedWriter(newFileWriter(resultsISPath)); for(inti=1;i<num.length;i++){ bw.write(num[i]+""); } System.out.print("排序結(jié)果成功寫入文件D:/resultsIS.txt"); bw.close(); } }快速排序代碼：packagesort;importjava.io.BufferedReader;importjava.io.BufferedWriter;importjava.io.FileReader;importjava.io.FileWriter;importjava.util.StringTokenizer;publicclassQuickSort{ staticStringdataPath="D:/data.txt"; staticStringresultsQSPath="D:/resultsQS.txt"; publicstaticvoidmain(String[]args)throwsException{ int[]number=Read(); longstartTime=System.currentTimeMillis();//排序開始時(shí)間 QSort(number,1,1999); longendTime=System.currentTimeMillis();//排序結(jié)束時(shí)間 System.out.println("快速排序用時(shí)"+(endTime-startTime)+"ms"); Write(number); } publicstaticintpartition(int[]num,intlow,inthigh){ num[0]=num[low]; intpivoKey=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]; returnlow; } publicstaticvoidQSort(int[]num,intlow,inthigh){ if(low<high){ intpivotLoc=partition(num,low,high); QSort(num,low,pivotLoc-1); QSort(num,pivotLoc+1,high); } } publicstaticint[]Read()throwsException{ BufferedReaderbr=null; StringTokenizerst=null; Stringtemp=null; String[]a=null; int[]num=newint[2000]; br=newBufferedReader(newFileReader(dataPath)); while(br.ready()){ temp=br.readLine(); a=temp.split(""); } for(inti=0;i<a.length;i++) num[i]=Integer.parseInt(a[i]); br.close(); returnnum; } publicstaticvoidWrite(