各种排序算法介绍.doc

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。算法过程设要排序的数组是A0AN-1，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即 key=A0； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值AJ，并与AI交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的AI，与AJ交换； 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束) 例如：待排序的数组A的值分别是：（初始关键数据：X=49） 注意关键X永远不变，永远是和X进行比较，无论在什么位子，最后的目的就是把X放在中间，小的放前面大的放后面。 A0 、 A1、 A2、 A3、 A4、 A5、 A6： 49 38 65 97 76 13 27 进行第一次交换后： 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找) 进行第二次交换后： 27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找X的值，6549,两者交换，此时：I=3 ) 进行第三次交换后： 27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后： 27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于X的值，9749,两者交换，此时：I=4,J=6 ) 此时再执行第三步的时候就发现I=J，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。 快速排序就是递归调用此过程在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示： 初始状态 49 38 65 97 76 13 27 进行一次快速排序之后划分为 27 38 13 49 76 97 65 分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序。 76 97 65 经第三步和第四步交换后变成 65 76 97 完成排序。插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置插入排序：包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。 编辑本段基本思想将n个元素的数列分为已有序和无序两个部分，如 插入排序过程示例下所示： ，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1) ,an(1) a1(n-1)，a2(n-1) ，, an(n-1) 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。 插入排序算法步骤1.从有序数列和无序数列a2,a3,an开始进行排序； 2.处理第i个元素时(i=2,3,n) , 数列a1,a2,ai-1是已有序的,而数列ai,ai+1,an是无序的。用ai与ai-1，a i-2,a1进行比较,找出合适的位置将ai插入； 3.重复第二步，共进行n-1次插入处理，数列全部有序。 void insertSort(Type* arr,long len)/*InsertSort algorithm*/ long i=0,j=0;/*iterator value*/ Type tmpData; assertF(arr!=NULL,In InsertSort sort,arr is NULLn); for(i=1;i 0 & tmpData arrj-1) arrj=arrj-1; j-; arrj=tmpData; 插入排序算法思路假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a1k是局部有序的,保证了插入过程的正确性. 算法描述一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到下一位置中 6. 重复步骤2 如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。 C语言示例代码示例代码为C语言，输入参数中，需要排序的数组为array,起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array中从first到last处于升序排列。 void insertion_sort(char array, unsigned int first, unsigned int last) int i,j; int temp; for (i = first+1; i=first) & (arrayj temp) arrayj+1 = arrayj; j-; arrayj+1 = temp; 这个更好: void InsertSort(char array,unsigned int n) int i,j; int temp; for(i=1;i0 & temp arrayj-1 ; j-)/compare the new array with temp arrayj=arrayj-1;/all larger elements are moved one pot to the right arrayj=temp; 这个是c+语言版本的插入排序。为了支持list使用了std:advance()。 #include template void insertion_sort(biIter begin, biIter end) typedef typename std:iterator_traits:value_type value_type; biIter bond = begin; std:advance(bond, 1); for(; bond!=end; std:advance(bond, 1) value_type key = *bond; biIter ins = bond; biIter pre = ins; std:advance(pre, -1); while(ins!=begin & *prekey) *ins = *pre; std:advance(ins, -1); std:advance(pre, -1); *ins = key; 希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DLShell于1959年提出而得名。基本思想希尔排序基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。 给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1 Shell排序Shell排序的算法实现: 1 不设监视哨的算法描述 void ShellPass(SeqList R，int d) /希尔排序中的一趟排序，d为当前增量 for(i=d+1;i=n；i+) /将Rd+1n分别插入各组当前的有序区 if(R i .key0&R0.key0 do increment=increment/3+1； /求下一增量 ShellPass(R，increment)； /一趟增量为increment的Shell插入排序 while(increment1) /ShellSort 注意： 当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。 2设监视哨的shell排序算法 具体算法【参考书目12 】 算法分析 1增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： 最后一个增量必须为1； 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6*n1.25之间。 2Shell排序的时间性能优于直接插入排序，据统计分析其时间复杂度为O(n1.3) 希尔排序的时间性能优于直接插入排序的原因： 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。 3稳定性 希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。交换排序所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。void swapsort(int a) for(i=0;i9;i+) for(j=i+1;j10;j+) if(aiaj) temp=ai; ai=aj; aj=temp; 选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。基本思想n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 初始状态：无序区为R1.n，有序区为空。 第1趟排序 在无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R1.i-1和R(1in-1)。该趟排序从当前无序区中选出关键字最小的记录 Rk，将它与无序区的第1个记录R交换，使R1.i和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 常见的选择排序细分为简单选择排序、树形选择排序（锦标赛排序）、堆排序。上述算法仅是简单选择排序的步骤。 排序过程【示例】： 初始关键字 49 38 65 97 76 13 27 49 第一趟排序后 13 38 65 97 76 49 27 49 第二趟排序后 13 27 65 97 76 49 38 49 第三趟排序后 13 27 38 97 76 49 65 49 第四趟排序后 13 27 38 49 76 97 65 49 第五趟排序后 13 27 38 49 49 97 65 76 第六趟排序后 13 27 38 49 49 65 97 76 第七趟排序后 13 27 38 49 49 65 76 97 最后排序结果 13 27 38 49 49 65 76 97示例代码： #include using namespace std; int main() int num10 = 9,8,10,3,4,6,4,7,2,1; cout排序前：endl; for (int m = 0;m 10;m+) coutnumm ; for (int i = 0;i 10;i+) int pos = i; for (int j = i;j numj) pos = j; int tem; tem = numpos; numpos = numi; numi = tem; coutendl排序后：endl; for (int m = 0;m 10;m+) coutnumm ; return 0; 二分查找 二分查找法二分查找又称折半查找，它是一种效率较高的查找方法。 【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n） 下面提供一段二分查找实现的伪代码: BinarySearch(max,min,des) mid-(max+min)/2 while(mindes then max=mid-1 else min=mid+1 return max 折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如 果xan/2，则我们只要在数组a的右 半部继续搜索x。堆排序堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。 大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 堆的高度堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）。 堆排序堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 （1）用大根堆排序的基本思想 先将初始文件R1.n建成一个大根堆,此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。 直到无序区只有一个元素为止。 （2）大根堆排序算法的基本操作： 初始化操作：将R1.n构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。 注意： 只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止 特点堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将Rl.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录 堆排序与直接选择排序的区别直接选择排序中，为了从R1.n中选出关键字最小的记录，必须进行n-1次比较，然后在R2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较结果，可减少比较次数。 算法分析堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。 堆排序的最坏时间复杂度为O(nlog2n)。堆序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。#define MAX 100/数据元素的最大个数 typedef struct int rMAX; int length; SqList;/定义一个线性表用于存放数据元素 void HeapAdjust(SqList &L,int s,int m) /已知L.rs.m中记录除L.rs外均满足堆的定义，本函数用于使L.rs.m成为一个大顶堆 int j; int e=L.rs; for(j=2*s;j=m;j*=2) if(jM&L.RJ=L.rj) break; L.rs=L.rj; s=j; L.rs=e; void HeapSort(SqList &L) /对顺序表L进行堆排序 int i,e; for(i=L.length/2;i0;i-) HeapAdjust(L,i,L.length