搜索
一.选择排序1.选择排序法基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过程：【示例】：初始关键字[4938659776132749]第一趟排序后13［38659776492749]第二趟排序后1327［659776493849]第三趟排序后132738[9776496549]第四趟排序后13273849[49976576]第五趟排序后1327384949[979776]第六趟排序后132738494976[7697]第七趟排序后13273849497676[97]最后排序结果13273849497676973.voidselectionSort(Type*arr,longlen){longi=0,j=0;/*iteratorvalue*/longmaxPos;assertF(arr!=NULL,InInsertSortsort,arrisNULL\n);for(i=len-1;i=1;i--){maxPos=i;for(j=0;jI;J++)Pif(arr[maxPos]Pif(maxPos!=i)swapArrData(arr,maxPos,i);}}选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.二.直接插入排序插入排序（InsertionSort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。直接插入排序直接插入排序（StraightInsertionSort）：将一个记录插入到排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序算法哨兵（监视哨）有两个作用：一是作为临变量存放R[i]（当前要进行比较的关键字）的副本；二是在查找循环中用来监视下标变量j是否越界。当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1)，是一个就地排序。直接插入排序是稳定的排序方法。三.冒泡排序[算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。[算法]：voidBubbleSort(SeqListR){//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序inti，j；Booleanexchange；//交换标志for(i=1;iexchange=FALSE；//本趟排序开始前，交换标志应为假for(j=n-1;j=i；j--)//对当前无序区R[i..n]自下向上扫描if(R[j+1].keyR[0]=R[j+1]；//R[0]不是哨兵，仅做暂存单元R[j+1]=R[j]；R[j]=R[0]；exchange=TRUE；//发生了交换，故将交换标志置为真}if(!exchange)return；//本趟排序未发生交换，提前终止算法}//endfor(外循环)}//BubbleSort[分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。[算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。[算法]：voidBubbleSort(SeqListR){//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序inti，j；Booleanexchange；//交换标志for(i=1;iexchange=FALSE；//本趟排序开始前，交换标志应为假for(j=n-1;j=i；j--)//对当前无序区R[i..n]自下向上扫描if(R[j+1].keyR[0]=R[j+1]；//R[0]不是哨兵，仅做暂存单元R[j+1]=R[j]；R[j]=R[0]；exchange=TRUE；//发生了交换，故将交换标志置为真}if(!exchange)return；//本趟排序未发生交换，提前终止算法}//endfor(外循环)}//BubbleSort[分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。四.希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2DT-L…D2D1)，即所有记录放在同一组中进行直接插入排序为止。P该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49，55，04。增量序列的取值依次为：5，3，1Shell排序的算法实现1．不设监视哨的算法描述voidShellPass(SeqListR，intd){//希尔排序中的一趟排序，d为当前增量for(i=d+1;i=n；i++)//将R[d+1．．n]分别插入各组当前的有序区if(R[i].keyR[I-D].KEY){PR[0]=R[i];j=i-d；//R[0]只是暂存单元，不是哨兵do{//查找R[i]的插入位置R[j+d]；=R[j]；//后移记录j=j-d；//查找前一记录}while(j0&&R[0].keyR[J].KEY)；PR[j+d]=R[0]；//插入R[i]到正确的位置上}//endif}//ShellPassvoidShellSort(SeqListR){intincrement=n；//增量初值，不妨设n0do{increment=increment/3+1；//求下一增量ShellPass(R，increment)；//一趟增量为increment的Shell插入排序}while(increment1)}//ShellSort注意：当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。2．设监视哨的shell排序算法算法分析1．增量序列的选择Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征：①最后一个增量必须为1；②应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。2．Shell排序的时间性能优于直接插入排序希尔排序的时间性能优于直接插入排序的原因：①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插人排序有较大的改进。3．稳定性希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。五.堆排序1、堆排序定义n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：(1)ki≤K2i且ki≤K2i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。2、大根堆和小根堆根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆。3、堆排序特点堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。4、堆排序与直接插入排序的区别直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。5、堆排序堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（1）用大根堆排序的基本思想①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。……直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作：①初始化操作：将R[1..n]构造为初始堆；②每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意：①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。（3）堆排序的算法：voidHeapSort(SeqIAstR){//对R[1..n]进行堆排序，不妨用R[0]做暂存单元inti；BuildHeap(R)；//将R[1-n]建成初始堆for(i=n;i1；i--){//对当前无序区R[1..i]进行堆排序，共做n-1趟。R[0]=R[1]；R[1]=R[i];R[i