还剩6页未读,继续阅读
文本内容:
快速排序(Quicksort)是对冒泡排序的一种改进由C.A.R.Hoare在1962年提出它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的全部数据都比此外一部分的全部数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列算法过程设要排序的数组是A
[0]A[N-1]首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将全部比它小的数都放到它前面,全部比它大的数都放到它后面,这个过程称为一趟快速排序一趟快速排序的算法是1)设置两个变量I、J排序开头的时候:1=0J=N-1;2)以第一个数组元素作为关键数据,赋值给key即key=A
[0];3)从J开头向前搜寻,即由后开头向前搜寻(J=J-1)找到第一个小于key的值A[J]并与A[I]交换;4)从I开头向后搜寻,即由前开头向后搜寻(1=1+1)找到第一个大于key的A[I]与A[J]交换;5)重复第
3、
4、5步,直到I=J;(34步是在程序中没找到时候i=i+l直至找到为止找到并交换的时候ij指针位置不变此外当i=j这过程肯定正好是i+或j+完成的最终另循环结束)例如:待排序的数组A的值分别是(初始关键数据X=49)留意关键X永久不变永久是和X进行比较,无论在什么位子,最终的目的就是把X放在中间,小的放前面大的放后面A
[0]、A[l]A⑵、A
[3]A
[4]、A⑸、A
[6]49386597761327进行第一次交换后27386597761349(依据算法的第三步从后面开头找)进行其次次交换后27384997761365(依据算法的第四步从前面开头找X的值,6549两者交换,此时1=3)进行第三次交换后27381397764965(依据算法的第五步将又一次执行算法的第三步从后开头找进行第四次交换后27381349769765(依据算法的第四步从前面开头找大于X的值,9749两者交换,此时I=4J=6)此时再执行第三步的时候就发觉I=J从而结束一趟快速排序,那么经过一趟快速排序之后的结果是27381349769765即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最终把此数据序列变成一个有序的序列,依据这种思想对于上述数组A的快速排序的全过程如图6所示初始状态(49386597761327}进行一次快速排序之后划分为{273813}49{769765)分别对前后两部分进行快速排序{273813}经第三步和第四步交换后变成{132738}完成排序{769765)经第三步和第四步交换后变成{657697)完成排序插入排序有一个己经有序的数据序列,要求在这个己经排好的数据序列中插入一个数,但要求插入后此数据序列仍旧有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间简单度为0(n八2)是稳定的排序方法插入算法把要排序的数组分成两部分第一部分包含了这个数组的全部元素,但将最终一个元素除外,而其次部分就只包含这一个元素在第一部分排序后,再把这个最终元素插入到此刻已是有序的第一部分里的位置插入排序包括直接插入排序,二分插入排序又称折半插入排序,链表插入排序,希尔排序又称缩小增量排序编辑本段基本思想将n个元素的数列分为已有序和无序两个部分,如.■■■”力”内插入排序过程示例下所示{{a2a3a
4...an}}{{alla2l}{a3la4l...9anl}}{{aln-la2n-l{ann-l}}每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中插入排序算法步骤.从有序数列和无序数列{a2a
3...an}开头进行排序;.处理第i个元素时i=
23...n数列{ala
2...ai-l是已有序的,而数列{aiai+l…an}是无序的用ai与ai-1ai-
2...al进行比较,找出合适的位置将ai插入;.重复其次步,共进行n-l次插入处理数列全部有序voidinsertSortType*arrjonglen/*InsertSortalgorithm*/longi=0j=0;/*iteratorvalue*/TypetmpData;assertFarr!=NULLnInInsertSortsortarrisNULL\nn;fori=l;ilen;i++••尸;tmpData=*arr+i;whilej0tmpDataarr[j-l]arr[j]=arr[j-l];j-Varr[j]=tmpData;插入排序算法思路假定这个数组的序是排好的,然后从头往后,假如有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a□…k]是局部有序的保证了插入过程的正确性.算法描述一般来说,插入排序都采纳in-place在数组上实现详细算法描述如下.从第一个元素开头,该元素可以认为已经被排序.取出下一个元素,在已经排序的元素序列中从后向前扫描.假如该元素已排序大于新元素将该元素移到下一位置.重复步骤3直到找到已排序的元素小于或者等于新元素的位置.将新元素插入到下一位置中.重复步骤2假如比较操作的代价比交换操作大的话,可以采纳二分查找法来削减比较操作的数目该算法可以认为是插入排序的一个变种,称为二分查找排序C语言示例代码示例代码为C语言,输入参数中,需要排序的数组为array□,起始索引为first终止索引为last示例代码的函数采纳in-place排序调用完成后,array口中从first到last处于升序排列voidinsertion_sortchararray[]unsignedintfirstunsignedintlastintij;inttemp;fori=first+1;i=last;i++temp=array;//与已排序的数逐一比较,大于temp时该数移后whilej=firstarray[j]temparray|j+l]=array[j];j--;arrayU+l]=temp;这个更好voidInsertSortchararray[]unsignedintnintij;inttemp;fori=l;in;i++temp=array!i];//storetheoriginalsortedarrayintempforj=i;j0temparray1-1];j-//comparethenewarraywithtemparray[j]=array[j-1];//alllargerelementsaremovedonepottotheright}an-ay[j]=temp;这个是C++语言版本的插入排序为了支持list使用了std::advanceo#includeiteratortemplatetypenamebiltervoidinsertion_sortbilterbeginbilterendtypedeftypenamestd::iterator_traitsbilter::value_typevalue_type;bilterbond二begin;std::advancebond1;for;bond!=end;std::advancebond1{value_typekey=*bond;bilterins=bond;bilterpre=ins;std::advancepre-1;whileins!=begin*prekey{*ins=*pre;std::advanceins-1;std::advancepre-1;*ins=key;希尔排序ShellSort是插入排序的一种是针对直接插入排序算法的改进该方法又称缩小增量排序,因DL.Shell于1959年提出而得名基本思想希尔排序基本思想先取一个小于n的整数dl作为第一个增量把文件的全部纪录分成dl个组全部距离为dl的倍数的纪录放在同一个组中先在各组内进行直接插入排序;然后,取其次个增量d2Vdi重复上述的分组和排序,直至所取的增量dt=ldtdM...d2dl即全部纪录放在同一组中进行直接插入排序为止该方法实质上是一种分组插入方法给定实例的shell排序的排序过程假设待排序文件有10个纪录,其关键字分别是49386597761327495504o增量序列的取值依次为31Shell排序Shell排序的算法实现.不设监视哨的算法描述voidShellPassSeqListRintd{〃希尔排序中的一趟排序,d为当前增量fori=d+l;i=n;i++〃将R[d+
1..n]分别插入各组当前的有序区ifR[i].keyR[i-d].key{R
[0]=R;j=i-d;〃R
[0]只是暂存单元,不是哨兵do{〃查找R的插入位置RU+d]=R[j];〃后移纪录j=j-d;〃查找前一纪录}whilejOR[O].keyR[j].key;R[j+d]=R[0|;〃插入R到正确的位置上}//endif}//ShellPassvoidShellSortSeqListRintincrement』;〃增量初值,不妨设n0do{increment二increment/3+1;〃求下一增量SheUPassRincrement;//一趟增量为increment的Shell插入排序}whileincrement1}//ShellSort留意当增量d=l时,ShellPass和InsertSort基本全都,只是由于没有哨兵而在内循环中增加了一个循环判定条件”j0\以防下标越界.设监视哨的shell排序算法详细算法【参考书目
[12]]算法分析.增量序列的选择Shell排序的执行时间依靠于增量序歹h好的增量序列的共同特征
①最终一个增量必需为1;
②应当尽量避开序列中的值尤其是相邻的值互为倍数的状况有人通过大量的试验,给出了目前较好的结果当n较大时,比较和移动的次数约在
21.25到
1.6*
21.25之间.Shell排序的时间性能优于直接插入排序,据统计分析其时间简单度为0n八
1.3希尔排序的时间性能优于直接插入排序的缘由
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少
②当n值较小时n和n2的差别也较小即直接插入排序的最好时间简单度0n和最坏时间简单度0n八2差别不大
③在希尔排序开头时增量较大,分组较多,每组的纪录数目少,故各组内直接插入较快,后来增量di渐渐缩小,分组数渐渐削减,而各组的纪录数目渐渐增多,但由于已经按di-l作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快因此,希尔排序在效率上较直接插人排序有较大的改进.稳定性希尔排序是不稳定的参见上述实例,该例中两个相同关键字49在排序前后的相对次序发生了变化交换排序所谓交换,就是依据序列中两个纪录键值的比较结果来对换这两个纪录在序列中的位置,交换排序的特点是将键值较大的纪录向序列的尾部移动,键值较小的纪录向序列的前部移动voidswapsortinta[]fori=0;i9;i++forj=i+l;j10;j++ifa[i]aU]temp=a|i|;a[i]=a[j];a[j]=temp;}选择排序每一趟从待排序的数据元素中选出最小或最大的一个元素,挨次放在已排好序的数列的最终,直到全部待排序的数据元素排完选择排序是不稳定的排序方法基本思想n个纪录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果
①初始状态无序区为R[L.n]有序区为空
②第1趟排序在无序区R[L.n]中选出关键字最小的纪录R[k]将它与无序区的第1个纪录R[l]交换,使和R[
2..n]分别变为纪录个数增加1个的新有序区和纪录个数削减1个的新无序区
③第i趟排序第i趟排序开头时,当前有序区和无序区分别为和Rlin-lo该趟排序从当前无序区中选出关键字最小的纪录Rik]将它与无序区的第1个纪录R交换,使R[Li]和R分别变为纪录个数增加1个的新有序区和纪录个数削减1个的新无序区这样,n个纪录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果常见的选择排序细分为简洁选择排序、树形选择排序锦标赛排序、堆排序上述算法仅是简洁选择排序的步骤排序过程【示例】初始关键字
[4938659776132749]第一趟排序后13
[38659776492749]其次趟排序后1327
[659776493849]第三趟排序后132738
[9776496549]第四趟排序后13273849
[76976549]第五趟排序后1327384949
[976576]第六趟排序后132738494965
[9776]第七趟排序后13273849496576
[97]最终排序结果1327384949657697示例代码#includeiostreamusingnamespacestd;intmainintnum
[10]={98103464721};coutv排序前endl;forintm=0;m10;m++cout«num[m]«nn;forinti=0;i10;i++intpos=i;forintj=i;j10;j++ifnum[pos]num[j]pos=j;inttern;tern=num[pos];num[pos]=num[i];num[i]=tern;cout«endl排序后n«endl;forintm=0;m10;m++cout«num[m]«nn;return0;二分查找■AM...■Ml■MIC•♦・•・〜•if』••M^一•・•・・・•••s•■3」二分查找法二分查找又称折半查找,它是一种效率较高的查找方法【二分查找要求】
1.必需采纳挨次存储结构
2.必需按关键字大小有序排列【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难因此,折半查找方法适用于不常常变动而查找频繁的有序列表【算法思想】首先,将表中间位置纪录的关键字与查找关键字比较,假如两者相等,则查找胜利;否则采用中间位置纪录将表分成前、后两个子表,假如中间位置纪录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表重复以上过程,直到找到满意条件的纪录,使查找胜利,或直到子表不存在为止,此时查找不胜利【算法简单度】假设其数组长度为n其算法简单度为logn下面供应一段二分查找实现的伪代码BinarySearchmaxmindesmid-max+min/2whilemin=maxmid=min+max/2ifmid二desthenreturnmidelseifmiddesthenmax=mid-1elsemin=mid+1returnmax折半查找法也称为二分查找法,它充分采用了元素间的次序关系,采纳分治策略,可在最坏的状况下用Ologn完成搜寻任务它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,假如x=a[n/2]则找到x算法终止如果xa[n/2]则我们只要在数组a的左半部连续搜寻x这里假设数组元素呈升序排列假如xa[n/2]则我们只要在数组a的右半部连续搜寻X堆排序积累排序Heapsort是指采用积累树堆这种资料结构所设计的一种排序算法,可以采用数组的特点快速定位指定索引的元素树中任一非叶结点的关键字均不大于或不小于其左右孩子若存在结点的关键字【例】关键字序列1,1556253070和705630251510分别满意堆性质1和2故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示小《2型•价构TU大根堆和小根堆根结点亦称为堆顶的关键字是堆里全部结点关键字中最小者的堆称为小根堆,又称最小堆根结点亦称为堆顶的关键字是堆里全部结点关键字中最大者,称为大根堆,又称最大堆留意
①堆中任一子树亦是堆
②以上争论的堆实际上是二叉堆BinaryHeap类似地可定义k叉堆堆的高度堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简洁下降路径上边的数目;定义堆的高度为树根的高度我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为Olgno堆排序堆排序采用了大根堆或小根堆堆顶纪录的关键字最大或最小这一特征,使得在当前无序区中选取最大或最小关键字的纪录变得简洁1用大根堆排序的基本思想
①先将初始文件R[L.n]建成一个大根堆此堆为初始的无序区
②再将关键字最大的纪录R[l]即堆顶和无序区的最终一个纪录R[n]交换,由此得到新的无序区R[L.n-l]和有序区R[n]且满意R[
1..n-1].keysR[n].key
③由于交换后新的根R[l]可能违反堆性质,故应将当前无序区R[Ln-l]调整为堆然后再次将R[L.n-l]中关键字最大的纪录R[l]和该区间的最终一个纪录R[n-1]交换,由此得到新的无序区R[l..n-2]和有序区R[n-l..n]且仍满意关系R[l..n-2].keysR[n-l..n].keys同样要将R[L.n-2]调整为堆直到无序区只有一个元素为止2大根堆排序算法的基本操作初始化操作将R[L.n]构造为初始堆;每一趟排序的基本操作将当前无序区的堆顶纪录R[l]和该区间的最终一个纪录交换,然后将新的无序区调整为堆亦称重建堆留意只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序
②用小根堆排序与采用大根堆类似,只不过其排序结果是递减有序的堆排序和直接选择排序相反在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止特点堆排序HeapSort是一树形选择排序堆排序的特点是在排序过程中,将R[Ln]看成是一棵完全二叉树的挨次存储结构,采用完全二叉树中双亲结点和孩子结点之间的内在关系参见二叉树的挨次存储结构,在当前无序区中选择关键字最大或最小的纪录堆排序与直接选择排序的区分直接选择排序中,为了从R[L.n]中选出关键字最小的纪录,必需进行n-1次比较,然后在R[
2..n]中选出关键字最小的纪录,又需要做n-2次比较事实上,后面的n-2次比较中,有很多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作堆排序可通过树形结构保存部分比较结果,可削减比较次数算法分析堆[排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的堆排序的最坏时间简单度为Onlog2no堆序的平均性能较接近于最坏性能由于建初始堆所需的比较次数较多,所以堆排序不相宜于纪录数较少的文件堆排序是就地排序,帮助空间为01它是不稳定的排序方法defineMAX100〃数据元素的最大个数typedefstructintr[MAX];intlength;}SqList;〃定义一个线性表用于存放数据元素voidHeapAdjustSqListLintsintm{//已知L.r[s…m]中纪录除L.r[s]外均满意堆的定义,本函数用于使L.r[s…m]成为一个大顶堆intj;inte=L.r[s];forj=2*s;j=m;j*=2ifjML.R[J]L.R[J+1]++j;ife=L.r[j]break;L.r[s]=L.r[j];s=j;L.r[s]=e;voidHeapSortSqListL{〃对挨次表L进行堆排序intie;fori=L.length/2;i0;i—HeapAdjustLiL-length;fori=L.length;i1;i—{〃将大顶堆的顶纪录和最终一个纪录相互交换e=L.r[l];L.r[l]=L.r[i];L.r[i]=e;HeapAdjustL1i-1;归并排序归并Merge排序法是将两个或两个以±有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的然后再把有序子序列合并为整体有序序列归并排序是建立在归并操作上的一种有效的排序算法该算法是采纳分治法DivideandConquer的一个特别典型的应用将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序若将两个有序表合并成一个有序表,称为2-路归并归并操作merge也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作如设有数列{62021003013881}初始状态⑹
[202]
[100]
[301]
[38]
[8]
[1]比较次数i=l
[6202]
[100301]
[838]
[1]3i=2
[6100202301]
[1838]4i=3
[16838100202301]4总计11次归并操作的工作原理如下申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针达到序列尾将另一序列剩下的全部元素直接复制到合并序列尾示例代码为C语言,输入参数中,需要排序的数组为array口,起始索引为first终止索引为lasto调用完成后array口中从first到last处于升序排列voidMergeSortintarray[]intfirstintlastintmid=0;iffirstlastmid=first+last/2;MergeSortarrayfirstmid;MergeSortarraymid+llast;Mergearrayfirstmidlast;}U21i$«ao♦31Mn加♦31XfiM和631Y■三【
9.fJU15而63124【才飞hi5%][I24Ce912B203f24[e9UBJUJ5」。