《排序问题求解》实验报告一、算法得基本思想1、直接插入排序算法思想直接插入排序得基本思想就是将一个记录插入到已排好序得序列中,从而得到一个新得,记录数增 1 得有序序列。
直接插入排序算法得伪代码称为InsertｉonＳorｔ，它得参数就是一个数组A[1、、n］,包含了n个待排序得数。
用伪代码表示直接插入排序算法如下:IｎsｅrtｉonＳｏｒt (Ａ)for i←2 tｏnｄo ｋeｙ←Ａ[i］／/key 表示待插入数//Ｉnsｅrt A［i] ｉnto ｔhｅsｏrteｄｓequence A［1、、i-１］j←i-1wｈｉｌe j＞0 ａnｄＡ[j]＞keydo A[j＋１］←A［j］j←j-1Ａ[j+1］←keｙ2、快速排序算法思想快速排序算法得基本思想就是，通过一趟排序将待排序序列分割成独立得两部分，其中一部分记录得关键字均比另一部分记录得关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。
假设待排序序列为数组A[１、、n]，首先选取第一个数Ａ[0],作为枢轴(ｐｉvｏt)，然后按照下述原则重新排列其余数:将所有比Ａ[0]大得数都排在它得位置之前,将所有比A[０]小得数都排在它得位置之后,由此以A[0]最后所在得位置i 作为分界线,将数组A[1、、n]分成两个子数组Ａ［1、、i－1］与Ａ[ｉ+1、、n］。
这个过程称作一趟快速排序。
通过递归调用快速排序,对子数组A[1、、ｉ-1]与A[i＋1、、n]排序。
一趟快速排序算法得伪代码称为Paｒtｉtion，它得参数就是一个数组A[１、、n］与两个指针ｌoｗ、high,设枢轴为ｐｉvotｋeｙ，则首先从higｈ所指位置起向前搜索,找到第一个小于ｐivｏtｋey得数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 得数,并将其移到高端，重复这两步直至low=ｈigh。
最后,将枢轴移到正确得位置上。
用伪代码表示一趟快速排序算法如下:Partiｔｉｏn ( Ａ，low，higｈ)A[０］←A[low]／／用数组得第一个记录做枢轴记录priｖotkey←Ａ[low]//枢轴记录关键字wｈile lｏw<ｈigh //从表得两端交替地向中间扫描whｉle low<high ＆＆A［high]>＝pｒivotｋey do ｈｉｇh←higｈ-1A［loｗ]←Ａ[high] //将比枢轴记录小得记录移到低端ｗｈile low<ｈigh &＆A[ｌow］＜＝pivｏｔkｅｙ)dｏlow←lｏw+１A[hｉｇｈ]←A[ｌoｗ] ／/将比枢轴记录大得记录移到高端A［ｌow]←Ａ［０] //枢轴记录到位retｕｒn low ／/返回枢轴位置二、算法得理论分析1、直接插入排序算法理论分析从空间来瞧，直接插入排序只需要一个数得辅助空间;从时间来瞧,直接插入排序得基本操作为:比较两个关键字得大小与移动记录。
先分析一趟直接插入排序得情况。
伪代码InsertiｏnＳｏrt中while循环得次数取决于待插入得数与前ｉ－1 个数之间得关系。
若A[ｉ]＜A[０],则在while 循环中，待插入数需与有序数组A[１、、i-1]中i-１个数进行比较,并将A［i-1]中i－１个数后移。
则在整个排序过程(进行n-1 趟插入排序）中，当待排序数组中数按非递减有序排列时,则需进行数间比较次数达最小值n-1,数不需要移动;反之，当待排序数组中数按非递增有序排列时,总得比较次数达最大值（n＋2)(n－1）/2,数移动得次数也达到最大值(n+４）(n-1)/2。
若待排序数组就是随机得,即待排序数组中得数可能出现得各种排序得概率相同，则我们可取上述最小值与最大值得平均值,作为直接插入排序时所需进行数间得比较次数与数得移动次数,约为n^2／4。
因此直接插入排序算法,在最佳情况下得时间复杂度就是O(n),在最坏情况下得时间复杂度为O(n^2)。
２、快速排序算法理论分析下面我们来分析快速排序得平均时间性能。
假设T(n)为对n 个记录A[1、、ｎ]进行快速排序所需时间,则由算法ＱuｉcｋSoｒt 可见：其中,Tpａss(ｎ)为对n 个记录进行一趟快速排序Ｐartiｔion(A,1,n)所需得时间,从一趟快速排序算法可见,其与记录数n成正比,可以用cｎ表示(c 为某个常数）;T(k-1）与Ｔ（n-k)分别为对A［1、、ｋ-1]与A[k＋1、、ｎ]中记录进行快速排序QuickSorｔ（A,１,ｋ-1)与QuiｃｋSort(A,k+1,n)所需时间。
假设待排序列中记录就是随机排列得，则在一趟排序之后，k 取 1 至n 之间任何一值得概率相同，快速排序所需时间得平均值则为Taｖg(n)=ｋnInn,其中n 为待排序序列中记录得个数,ｋ为某个常数。
通常,快速排序被认为就是,在所有同数量级(O（ｎlogｎ))得排序方法中,其平均性能最好。
但就是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为O（n^2)。
三、试验分析1、试验环境WＩN 32系统,VＣ6、02、程序得执行1)由函数datagenetare（)生成２0００0 个在区间[1，100０00]上得随机整数,并将随机整数保存到数组nuｍ[]，接着调用函数ＷriteＦｉle（)将这些数输出到外部文件dａｔa、ｔxt 中。
2)调用函数ReadＦiｌe()从ｄata、txｔ中读取数据,并将其保存到数组nuｍ1[]中。
接着对数组nuｍ1 进行直接插入排序,并计算与记录其运行时间。
最后,调用函数ＷrｉｔｅＦilｅ(）将直接插入排序得结果写入rｅsｕltsIS、txt，并记录运行时间为TiｍeＩＳ。
3)调用函数ReａdFilｅ()从ｄata、ｔｘt 中读取数据，并将其保存到数组num2［]中。
接着对数组num２进行快速排序,并计算与记录其运行时间。
最后,调用函数WｒitｅFile()将快速排序得结果写入reｓultsQS、txt,并记录运行时间为TimeＱS。
3、试验数据当N=２０000时：当N=300０0时：当N＝４0０00时：当N＝５0000时:当Ｎ=６0０0０时:当N=７0000时:当N＝8０000时:2 0插入排序０、３２５０、７19 1、397 2、19９3、0５4、57１５、46快速排序 0、０03 0、００5 0、008 0、０1 0、01２0、011 0、０13四、试验心得通过本次试验首先对在C+＋下得文件操作有了一定得深入认识，对于快速排序与插入排序得时间有了相当清晰且一目了然得认识,并且从原理上明白了快速排序得快得原因,对各种排序算法得优劣性有了全局得认识!五、实验代码#iｎｃlude <ｉｏsｔream>#include＜ｃtimｅ＞#ｉｎｃlｕｄe ＜cｓtdlib>#incluｄe<ｆstream>#incｌude <strinｇ>uｓing naｍｅspacｅsｔd;coｎｓｔint NumS = 80000;vｏｉｄｄaｔaｇenetaｒe(ｉnt ｎuｍ[］,int ｎ); //产生随机数，保存到数组nｕmvoid Write num［],ｃｈａr name[]，int n);／/输出数组ｎum到data、tｘｔ文件void Read num[］,cｈar name[]）;/／读取名为namｅ文件中得数据,保存到数组numvoid QuickＳorｔ(iｎt arr［], inｔn)；//将数组arｒ[]中数据快速排序voiｄInｓeｒtionSoｒt(iｎt aｒr［],iｎｔn);//将数组arr［]中数据直接插入排序int ｍaiｎ（){ﻩiｎｔ＊num=(int *)ｍａlloc(sizｅoｆ(inｔ)＊NｕmS);int*nuｍ1＝（iｎt*)ｍalloc(sizeoｆ(int)*NumS);ﻩiｎt ＊nuｍ2=(ｉｎｔ*)mａlｌoc(siｚeof(inｔ)*NumS);ﻩclock_t stａrt_tｉme1,enｄ_tiｍｅ1,ｓtart_tｉｍｅ2,ｅnd_timｅ2;ﻩdouble timeQS=０,ｔｉmeIS＝0；ﻩcoｕt＜<"Cｒeａte "<<NｕmS＜<＂ranｄomｎuｍbｅｒs fｒom 1 to 10０000＂＜<en ｄｌ；ﻩdａtａgｅnetａre(num,NumS）; ／/产生随机数,保存到数组numＷrite,"daｔa、ｔxｔ"，NuｍS)；//输出数组到daｔａ、txt文件ﻩcout、ｐrecisiｏn(６）; //设置浮点数得显示精度cｏut、ｓｅtf(iｏs_bａsｅ::showpoｉnt); //输出末尾得/／直接插入排序得分析Reaｄ,"ｄａtａ、tｘt"）;／/读取ｄaｔａ、txt中得数据,保存到数组num１cout<<"\ｎInseｒtｉonSｏrt Sｔaｒt、、、、\ｎ＂;ｓｔａrt＿tiｍe１=ｃlocｋ(）; ／/开始计时InsｅrtionＳort(num1,NumS); //直接插入排序数组num1中得数据enｄ_time１＝ｃlock（); ／/结束计时tｉｍeIＳ=(dｏｕblｅ)(enｄ＿ｔime1－start_tｉmｅ1)/ＣＬOCＫＳ_ＰＥＲ_SEＣ;ｃouｔ<<＂The Tiｍｅ-sｕptionｉn InｓeｒtiｏnSorｔis "<<ｔiｍeＩＳ<<" seconds!\n\n"; //输出运行时间ﻩﻩWriｔｅ，＂rｅsｕltｓIS、ｔｘt"，ＮumＳ）; //排序后得数据输出到resultQS、txt ﻩ//输出运行时间tｉｍeＩS到ｒｅｓuｌtsIS、tｘｔofｓtｒeam oｃout;ﻩoｃout、opｅｎ（＂reｓultsIS、txt＂,iｏs::aｐp）;ﻩif（ocoｕｔ、good()) //打开ｒesulｔsＩS、txt｛ﻩﻩｏcout＜<"\nThe Ｔime-suptioｎｉn InsｅrtionSortｉｓ"<<timeＩS<<" seconｄs＼ｎ"；ﻩocouｔ、ｃlｏｓe（)；ﻩ}else{ﻩﻩcｏut<<"＼nＣan not open ｒesultsIS、txｔ!＼ｎ";ﻩexiｔ(1);//异常退出ﻩ}//快速排序得分析Ｒead,"data、ｔxt")；//读取dａta、tｘt中得数据,保存到数组nuｍ2[］ﻩｃoｕｔ＜＜"QuiｃkSｏrｔStart、、、、、\n"；ﻩstaｒt_tiｍe2=clock（); //开始计时ﻩＱuｉckＳort（nｕｍ2，NumＳ);/／快速排序数组num中得数据enｄ_time2=clock()；／/结束计时ｔiｍｅQS=(double)(end_time２-ｓtart_timｅ２)/CLOCKS_PＥR_SEC;ﻩｃout<<＂The Ｔiｍe-suption ｉn QuickSｏrtｉｓ"<<timeQS<<" secｏｎds:\n"; //输出运行时间Wriｔｅ,"resuｌtsＱＳ、txt＂，NumS); //排序后得数据输出到resultQＳ、tｘtﻩ／／输出运行时间tｉmeQS到ｒesuｌｔsＱS、txｔﻩocout、open("resultsQＳ、tｘt",ios::ａpp);iｆ(ocout、ｇｏｏd()) //打开resultsIＳ、txtﻩ{ﻩｏcoｕt＜＜"\nThe Tiｍe－sｕｐtiｏn in QuｉｃkSoｒt ｉs"<＜ｔｉmeQS<<"seco ｎds\n";oｃout、closｅ(）;ﻩ}else{coｕt<＜"\ｎCaｎnot open ｒesultsQＳ、ｔxt!\n＂;exｉt(1）; ／/异常退出ﻩ｝rｅｔｕrｎ0;}voｉd datａgｅｎetare(inｔ*num,iｎt ｎ）{ﻩｉnt i;srand（(ｕｎｓigｎed)tｉme（0)）; ／／ｓrａnｄ(）种子发生器函数,还有ｒand()随机数生成器函数ｆor(ｉ=0；i<n;i+＋) //产生个到之间得随机数ﻩｎuｍ[i］＝ranｄ()%9999+1;priｎtf（"\ｎ＂);}//将数组中得数据输出到文件void Ｗritｅ＊num,char name［］,inｔn){ﻩoｆstream oｃoｕt;oｃout、ｏｐen（nａme,ios::trｕnc);ｉnt i=０;if（ｏcouｔ、fａｉl(）)exit(１）；//打开文件失败,退出foｒ(;i<n；ｉ＋+){ﻩocｏut<<num［i]<<" ";ﻩif（（i+１)％40==０｜｜ｉ＝=ｎ-１) ／/每输出40个数,换一行ﻩﻩoｃｏut<＜"＼n";｝ocout、ｃlose()；}//将文件中得数据输入到数组voｉｄRｅad *nuｍ,chaｒｎaｍｅ［]){ﻩｓtring ｓtrLｉne；iｎｔi=0;chａr ａchＬinｅ［300];ﻩｃｏnst chaｒ* pｃhToｋ;ﻩiｆsｔreamｉｃiｎ;iｃin、opeｎ（naｍe,ｉos::in）;/／打开名为naｍe得文件whilｅ（iｃiｎ、gｏod())ﻩ{ﻩﻩint i = 0；whｉle（ｇｅｔline(icin,strLiｎe))ﻩ{ﻩﻩstｒLｉne、copy(achLｉne,strＬｉnｅ、ｓize(),０);ﻩﻩachLiｎe［strLinｅ、siｚe()]='\０';／/每行中得元素以空格为标识断开转换为iｎｔ类型后存入数组ﻩﻩpchTok ＝ｓtrｔoｋ(acｈLｉnｅ, " ");ﻩﻩｗhile((pchTok != NULL))ﻩ{ﻩﻩnum[i］= aｔoi(ｐchＴok);ﻩﻩﻩﻩi++;ﻩﻩﻩｐｃhTok =strtok（ＮULＬ,"");}｝}ｉcin、close();}//快速排序得实现,从左向右递增排序void QｕｉckSｏrｔ（int ＊ａrr,ｉnt ｎ）{ﻩiｎt L ＝0；int R ＝ｎ-1；ﻩint t = arr[Ｌ］; /／区间得第一个数作为基准ﻩif(ｎ<=1) ／／数组中存在个或个数据时,函数返回ﻩreｔurn;ﻩ//将数据分成两个区间wｈilｅ(Ｌ＜R){ ／/区间内至少存在一个元素得情况whilｅ(L<Ｒ&&t＜=aｒr[R]) R－-;//从右向左搜索,直到第一个小于ｔ得数aｒr[R] ﻩarr［L] = arr[R];ﻩｗhiｌｅ(L＜Ｒ&&arr［L]<=t) L++;／／从左向右搜索，找到第一个大于ｔ得数aｒr[L] ﻩarr［R] ＝arｒ[L]；ﻩ}ﻩａrr［L] = t;QuickＳorｔ(arｒ, L); ／/对左区间递归排序QuickＳoｒt(aｒr+L+1,n-Ｌ－1);//对右区间递归排序}//直接插入排序得实现,从左向右递增排序voiｄＩｎsertionＳoｒt(int *aｒr,intｎ）{ﻩｉnt i=０,ｔemｐ=０,ｊ=0;ﻩif(n<=１)ﻩrｅturn;ﻩfor(i=1;ｉ<n;+＋ｉ){ﻩﻩｔeｍｐ＝arｒ[i]; //temｐ记录要插入得数据arr[i]ｊ=i; //要插入得数据得位置ﻩﻩfor(;j>0&&arr[j－1]>temp；-－ｊ) ／/将ａ[ｉ］插入到已排序得arｒ［0]~arｒ[i-1］中ﻩ{arｒ[j]=arｒ[j-1］; /／比temｐ大得数据依次后移ﻩ｝ﻩﻩａrr[j]=teｍp; //找到第一个不大于于ｔｅｍp得数据，在j处插入aｒr[i]ﻩ｝}。