C++各类排序算法介绍

2020/12/291contents•9.1概述•9.2插入排序–1.直插排序–2.二分插入排序–3.希尔排序•9.3交换排序–1.冒泡排序–2.快速排序•9.4选择排序–1.直选排序–2.堆排序•9.5归并排序–1.二路归并排序2020/12/2929.1概述•排序定义–将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~•排序分类–按待排序记录所在位置•内部排序：待排序记录存放在内存•外部排序：排序过程中需对外存进行访问的排序–按排序依据原则•插入排序：直接插入排序、折半插入排序、希尔排序•交换排序：冒泡排序、快速排序•选择排序：简单选择排序、堆排序•归并排序：2-路归并排序•基数排序2020/12/293–按排序所需工作量•简单的排序方法：T(n)=O(n²)•先进的排序方法：T(n)=O(logn)•基数排序：T(n)=O(d.n)•排序基本操作–比较两个关键字大小–将记录从一个位置移动到另一个位置2020/12/294•基本思想：每次将一个待排序的记录，按其关键字值的大小插入到已经排好序的表中，直至全部插入完成。•根据“寻找”插入位置的方法不同，插入法可分为：直插排序、二分插入排序、希尔排序。•(1)直接插入排序–若将一个未排序的元素L[i]插入到已排序的具有i-1个元素的序列的适当位置，步骤如下：•a.从右向左顺序搜索已排序的序列，若已排序序列中的元素比L[i]大，则后移一个位置，直至找到一个元素L[j-1](0≤j-1≤i-1)的关键字值比L[i]的关键字值小；•b.将L[i]插入表中第j个位置上，成为L[j]。9.2插入排序2020/12/295例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：2020/12/296voidInsertSort(inta[],constintn){for(inti=1;in;i++)//i表示插入次数，共进行n-1次插入if(a[i]a[i-1])//将a[i]插入到有序区a[0],…,a[i-1]中，//且a[i]a[i-1]{intx=a[i];//把待排序元素赋给x//从a[i-2]开始比较for(intj=i-1;(xa[j])&&(j=0);j--)a[j+1]=a[j];//从a[i-1]开始后移一位//直到找到一个元素，插入到正确位置a[j+1]=x;}}2020/12/297•算法评价–时间复杂度•若待排序记录按关键字从小到大排列(正序)关键字比较次数：112nni记录移动次数：)1(222nni•若待排序记录按关键字从大到小排列(逆序)关键字比较次数：2)1)(2(2nnini记录移动次数：2)1)(4()1(2nnini•若待排序记录是随机的，取平均值关键字比较次数：42n记录移动次数：42nT(n)=O(n²)2020/12/298•(2)折半插入排序–排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)2020/12/299–算法描述时间复杂度：T(n)=O(n²)voidBinsertSort(inta[],constintn){for(inti=1;in;i++){intb=a[i];intlow=0;inthigh=i-1;while(low=high){intm=(low+high)/2;if(ba[m])high=m-1;elselow=m+1;}for(intj=i-1;j=high+1;j--)a[j+1]=a[j];a[high+1]=b;}}2020/12/2910•(3)希尔排序(缩小增量法)–排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。2020/12/2911取d3=1三趟分组：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：1327485544938659776二趟排序：1344838274955659776取d1=5一趟分组：4938659776132748554取d2=3二趟分组：13274855449386597762020/12/2912–算法描述例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序：1327485544938659776jiji274jiji55ji38jijiji二趟排序：1344838274955659776jiji6548ji9755ji7642020/12/2913voidShellInsert(inta[],intn,intdk){for(inti=dk;in;i++)if(a[i]a[i-dk]){intb=a[i];for(intj=i-dk;(j=0)&&(ba[j]);j-=dk)a[j+dk]=a[j];a[j+dk]=b;}}voidShellSort(inta[],intn,intdlta[],intt){for(intk=0;kt;k++)ShellInsert(a,n,dlta[k]);}2020/12/2914–希尔排序特点•子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。•希尔排序可提高排序速度，因为–分组后n值减小，n²更小，而T(n)=O(n²)，所以T(n)从总体上看是减小了–关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序•增量序列取法–无除1以外的公因子–最后一个增量值必须为12020/12/2915•(0)基本思想：–两两比较待排序的数据元素的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。•(1)冒泡排序过程–将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。–对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。–重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。9.3交换排序2020/12/2916例4938659776132730初始关键字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟384976971397279730971376767627301365276530651313494930492738273830382020/12/2917voidbubble_sort(JDr[],intn){intm,i,j,flag=1;//当flag为0则停止排序JDx;m=n-1;while((m0)&&(flag==1)){//m表示趟数flag=0;//开始时元素未交换for(j=1;j=m;j++)if(r[j].keyr[j+1].key){//发生逆序flag=1;x=r[j];r[j]=r[j+1];r[j+1]=x;}//交换，并标记发生了交换m--;}//while}–冒泡算法描述2020/12/2918–算法评价•时间复杂度–最好情况（正序）比较次数：n-1移动次数：0–最坏情况（逆序）比较次数：)(21)(211nninni移动次数：)(23)(321nninniT(n)=O(n²)Ch8_4.c2020/12/2919•(2)快速排序–基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。–排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设基准值记录rp=r[s]，x=rp.key•初始时令i=s,j=t•首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换•再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换•重复上述两步，直至i==j为止•再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止关键字通常取第一个记录的值为基准值。2020/12/2920例初始关键字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849506576974927ijijij4965ji1349ij4997ij2020/12/2921voidqksort(JDr[],intt,intw){inti,j,k;JDx;if(t=w)return;i=t;j=w;x=r[i];while(ij){while((ij)&&(r[j].key=x.key))j--;if(ij){r[i]=r[j];i++;}while((ij)&&(r[i].key=x.key))i++;if(ij){r[j]=r[i];j--;}}r[i]=x;qksort(r,t,j-1);qksort(r,j+1,w);}–快速算法描述2020/12/2922–算法评价•时间复杂度–最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)–最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)T(n)=O(n²)Ch8_5.c2020/12/2923•(0)选择排序原理：–将待排序的结点分为已排序(初始为空)和未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。•(1)直接选择排序过程–首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换–再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换–重复上述操作，共进行n-1趟排序后，排序结束9.4选择排序2020/12/2924例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：132738496576972020/12/2925voidsmp_selesort(JDr[],intn){inti,j,k;JDx;for(i=1;in;i++){k=i;for(j=i+1;j=n;j++)if(r[j].keyr[k].key)k=j;if(i!=k){x=r[i];r[i]=r[k];r[k]=x;}}}–选择算法描述2020/12/2926–算法评价•时间复杂度–记录移动次数最好情况：0最坏情况：3(n-1)–比较次数：