浅谈各种排序与查找比较

亳州师范高等专科学校计算机应用专业论文1浅谈各种排序与查找比较容迎辉【内容摘要】排序与查找在软件基础中应是学习的重点，对于我们而言排序与查找也是重要的，应该说在生活中也会有用到这些。因排序与查找较多，在此对各种排序与查找进行讲解，并通过对它们的效率分析来比较各种排序与查找的优劣。【关键词】排序查找比较举例一、排序所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。（一）内部排序的主要算法分类及描述1、插入排序（1）直接插入排序算法思想：每次将一个带排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。算法描述：VoidInsertsort(SeqListR){inti,j;for(i=2;i=n;i++)if(r[i].keyr[i-1].key){r[0]=r[i];j=i-1;Do{r[j+1]=r[j];j--;}while(r[0].keyr[j].key);R[j+1]=r[0];}}（2）希尔排序含义：希尔排序又称为“缩小增量排序”。亳州师范高等专科学校计算机应用专业论文2算法描述：rectyper[n+d];intd[t];shellsort(rectyper[],intd[]){intI,j,k,h;rectypetemp;intmaxint=32767;for(i=0;id[0];i++)r[i].key=-maxint;k=0;do{h=d[k];for(i=h+d[0]-1;in+d[0];i++){temp=r[i];J=i-h;While(temp.keyr[j].key){r[j+h]=r[j];J=j-h;}R[j+h]=temp;}K++;}while(h!=1);}2、交换排序（1）冒泡排序算法思想：将被排序的记录数组r[1…n]垂直排列，每个记录r[i]看做是重量为r[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组r:凡扫描到违反本原则的轻气泡，就使其向上“漂浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。算法描述：Voidbubblesort(seqlistr){intI,j;Booleanexchange;For(i=1;in;i++){Exchange=false;For(j=n-1;j=I;j--)If(r[j+1].keyr[j].key){R[0]=r[j+1];R[j+1]=r[j];R[j]=r[0];Exchange=true;亳州师范高等专科学校计算机应用专业论文3}If(!Exchange)Return;}}(2)快速排序快速排序通常被称为分治法（将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些问题，然后将这些子问题的解组合为与原问题的解）。算法思想：分解、求解、组合算法描述：（快速排序）voidquicksort(seqlistr,intlow,inthigh){intpivotpos;if(lowhigh){pivotpos=partition(r,low,high);quicksort(r,low,pivotpos-1);quicksort(r,pivotpos+1,high);}}(划分算法)intpartition(seqlistr,intI,intj){recetypepivot=r[i];While(ij){While(ij&&r[j].key=pivot.key)j--;if(ij)r[i++]=r[j];while(ij&&r[j].key=pivot.key)i++;if(ij)r[j--]=r[i];}R[i]=pivot;ReturnI;}3、选择排序（1）直接选择排序算法思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录拍完为止。算法描述：selectsort（rectyper[]）{intI,j,k;Rectypetemp;For(i=0;in-1;i++)亳州师范高等专科学校计算机应用专业论文4{k=I;For(j=i+1;jn;j++)If(r[j].keyr[k].key)k=j;If(k!=i){temp=r[i];R[i]=r[k];R[k]=temp;}}}(2)归并排序算法思想：假设初始表含有n个记录，则可看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2个长度为2或1的有序子表，再两两归并，如此重复，直至得到一个长度为n的有序子表为止，这种方法称为“二路归并排序”。算法描述：merge(rectyper[],rectyper1[],intlow,intmid,inthigh){intI,j,k;I=low;j=mid+1;k=low;While((i=mid)&&(j=high)){If(r[i].key=r[j].key)R1[k++]=r[i++];ElseR1[k++]=r[j++];}While(i=mid)r1[k++]=r[i++];While(j=high)r1[k++]=r[j++];}(3)堆排序堆实质上是满足如下性质的完全二叉树：树种任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。算法描述：voidHeapSort(Recordr[],intn){for(i=n/2;i=1;i--)//初始建堆，从最后一个非终端结点至根结点进行筛选Sift(r,i,n);for(i=1;in;i++)//重复执行移走堆顶及重建堆的操作{r[1]--r[n-i+1];Sift(r,i,n-i);procedureshift(r,n:longint);//调整堆varv,k:longint;begin亳州师范高等专科学校计算机应用专业论文5v:=a[r];k:=2*r;whilek=ndobeginif(kn)and(a[k]a[k+1])theninc(k);ifa[k]vthenbreakelsebegina[r]:=a[k];r:=k;k:=2*k;end;end;a[r]:=v;end;（4）基数排序算法思想：则是属于“分配式排序”（distributionsort），基数排序法又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。算法描述：#includestdio.h#includestdlib.hintmain(){intdata[10]={73,22,93,43,55,14,28,65,39,81};inttemp[10][10]={0};intorder[10]={0};inti,j,k,n,lsd;k=0;n=1;printf(\n排序前:);for(i=0;i10;i++)printf(%d,data[i]);putchar('\n');while(n=10){for(i=0;i10;i++){lsd=((data[i]/n)%10);temp[lsd][order[lsd]]=data[i];order[lsd]++;}printf(\n重新排列:);for(i=0;i10;i++){if(order[i]!=0)for(j=0;jorder[i];j++){data[k]=temp[i][j];亳州师范高等专科学校计算机应用专业论文6printf(%d,data[k]);k++;}order[i]=0;}n*=10;k=0;}putchar('\n');printf(\n排序后:);for(i=0;i10;i++)printf(%d,data[i]);return0;}(二)各种排序方法性能比较表排序方法时间复杂度平均时间复杂度空间复杂度稳定性最好最坏直接插入排序O(n)O(n^2)O(n^2)O(1)稳定希尔排序xxO(n^1.5)O(1)不稳定冒泡排序O(n)O(n^2)O(n^2)O(1)稳定快速排序O(nlog(2)n)O(n^2)O(nlog2n)O(nlog2n)不稳定直接选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(n+rd)稳定二、查找给定一个值k,在含有n个结点的表中找出关键字等于给定值k的结点。（一）主要查找及描述1、顺序查找含义：顺序查找也称为线性查找，从数据结构线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；反之，查找失败。基本思想：从线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较。算法描述：intseqsearch(seqlistr,keytypek)亳州师范高等专科学校计算机应用专业论文7{intI;R[0].key=k;For(i=n;r[i].key!=k;i--);ReturnI;}2、二分查找含义：二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。基本思想：首先确定该区间的中点位置：mid=(low+high)/2(取不大于求出的数的整数)；然后将待查的k值与r[mid].key比较：若相等，则查找成功并返回此位置。否则需确定新的查找区间，继续二分查找：kr[mid].key,则low=mid+1;kr[mid].key,则high=mid-1。算法描述：intbinsearch(seqlistr,keytypek){intlow=1,high=n,mid;While(low=high){Mid=(low+high)/2;If(r[mid].key==k)returnmid;If(r[mid].keyk)High=mid-1;ElseLow=mid+1;}Return0;}3、分块查找含义：顺序表的分块查找又称表索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找算法。基本思想：首先查找索引表。索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。然后在已确定的块中进行顺序查找。由于块内无序，只能用顺序查找。4、散列表查找设所有可能出现的关键字集合记为U（简称全集）。实际发生（即实际存储）的关键字集合记为K(|K|比|U|小得多)。散列函数的构造方法：二次方取中法（先通过求关键字的二次方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值）、数字分析法（对亳州师范高等专科学校计算机应用专业论文8关键字进行分析，取关键字的若干位或其组合作哈希地址）、直接定址法（取关键字或关键字的某个线性函数作哈希地址，即h(key)=key）、相乘取整法（首先用关键字key乘上某个常数A(0A1),并抽取出key.A的小数部分；然后用m乘以该小数后取整）、随机数法（选择一个随机函数，取关键字的随机函数值为它的散列地址，即h(key)=random(key)）、除余法（常用方法，以表长m来除关键字，取其余数作为散列地址，即h（key）=key%m,该方法的关键是选取m，m最好为素数。）散列表会出现冲突现象（两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上，该现象称为冲突或碰撞）。处理冲突的方法：（1）开放地址法：线性探查法（探查序列Hi=(h(key)+i)%m0=i=m-1）;二次探查法（探查序列Hi=(h(key)+i*i)%m0=i=m-