浅谈各种排序与查找比较

1、浅谈各种排序与查找比较容迎辉k内容扌商要】排序与查找在软件基础中应是学习的重点，对于我们而言 排序与查找也是重要的，应该说在生活中也会有用到这些。因排序与查找较多， 在此对各种排序与查找进行讲解，并通过对它们的效率分析来比较各种排序与查 找的优劣。【关键词】排序查找比较举例一、排序所谓排序，就是要整理文件屮的记录，使之按关键字递增(或递减)次序 排列起来。(-)内部排序的主要算法分类及描述1、插入排序(1) 直接插入排序算法思想:每次将一个带排序的记录,按其关键字人小插入到前面已经排好序的子文件屮的适当位置，直到全部记录插入完成为止。 算法描述：void insertsort(seqlist

2、r)int i, j;for(i=2;i<=n;i+)if (ri.key<ril. key) r0=ri;j=i-l; dorj+l=rj;j；while(r0. key<rj. key); rj+1二 r0;(2) 希尔排序含义：希尔排序又称为“缩小增量排序”。算法描述:rectype rn+d; int dt;shel1 sort (rectype r, ini d) int t, j, k, h;rectype tcmp; int maxint=32767;for (i=0;i<d0;i+) ri.key 二-maxint;k 二0;doh=dk;for (i=

3、h+d0-l;i<n+d0;i+) temperi;j二i-h;while (temp. kcy<rj key) rj+h=rj;j二j-h；rj+h=temp;k+; while(h!=l);2、交换排序(1)冒泡排序算法思想：将被排序的记录数组讥1n垂直排列，每个记录讥i看做是重量为ri.kcy的气泡。根据轻气泡不能在重气泡z下的原则，从下往上扫描数组r:凡扫描到违反本原则的轻气泡，就使其向上“漂浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。算法描述：void bubblesort(seqlist r) int i, j;boolean exchange;

4、for (i = l;i<n;i+) exchange=falsc; for(j=n-l;j>=l;j)if (rj+l. key<rj. key) r0二讥 j+1; rj+1二讥j;rj=r0;exchange=true;if(! exchange) return; (2)快速排序 快速排序通常被称为分治法(将原问题分解为若干个规模更小但结构与原问 题相似的了问题。递归地解这些问题，然后将这些了问题的解组合为与原问题的解o算法思想：分解、求解、组合算法描述：(快速排序)void quicksort (seqlist r, int low, int high) int pi

5、votpos;if (low<high)pivotpos=partition(r, 1 ow, high);quicksort (r, 1 ow, pi votpost);quicksort (r, pivotpos+1, high);(划分算法)int partition(seql ist r, int t, int j) recetype pivot二ri;wh订e(i<j) while(i<j&&rj. key>二pivot, key)j；if(i<j)ri+=rj;while(ij&&rj key<=pivot.key

6、) i+；rj=ri;ri二pivot;return 1;3>选择排序(1)直接选择排序算法思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录拍完为止。 算法描述： selectsort (rectype r) int t, j, k;rcctype temp;for (i=0;i<nl;i+) k=i;for(j=i+1;j<n;j+) if (rj. key<rk. key) k=j;if (k!二i) temp=ri;ri二讥 k; rk=temp;(2) 归并排序算法思想：假设初始表含冇n个记录，则可看成是n个冇序的子

7、表，每个子 表的长度为1,然后两两归并，得到n/2个长度为2或1的有序了表，再两两归 并，如此重复，直至得到一个长度为n的有序子表为止，这种方法称为“二路归 并排序”。算法描述：merge (rec type r , rec type rl , int low, int mid, int high) int t, j, k;t=low;j二mid+1;k=low;wh订c(i二mid)&&(j二high) if(ri. key<=rj.key)rlk+=ri+;el serlk+二rj+;while(i<=mid) rlk+=ri+;while(j<=high

8、) rlk+=rj+;(3) 堆排序堆实质上是满足如下性质的完全二叉树：树种任一非叶子结点的关键字均不 大于(或不小于)其左右孩子(若存在)结点的关键字(即如果按照线性存储该 树，可得到一个不下降序列或不上升序列)。算法描述：void heapsort(record r, int n)for(i二n/2; i>二1; i-)/初始建堆，从最后一个非终端结点至根结点 进行筛选sift (r, i, n);for(i=l; in; i+)/重复执行移走堆顶及重建堆的操作r1-rn-i+1;sift (r, i, ni);procedure shift (r, n: longint) ;/调整

9、堆varv, k:longint;beginv:=ar;k:=2*r;while k二n dobeginif (k<n)and (ak>ak+1) then inc (k);if ak>v then breakelse begina er:二ak;r :=k;k:=2*k;end;end;a er:二v;end;(4) 基数排序算法思想:则是属于“分配式排序”(distribution sort),基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义，它是透过键值的部份资 讯，将要排序的元素分配至某些“桶”屮，藉以达到排序的作用，基数排序法是 属于稳

10、定性的排序，其时间复杂度为0 (nlog(r)m),其中r为所采取的基数,而m为堆数，在某些时候，基数排序法的效率高丁其它的比较性排序法。算法描述:ttincludc <stdio. h>ttinclude <stdlib. h> int main() int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010=0;int order10=0;int i, j, k, n, lsd;k二0;n二1;printf (，zn 排序前：“)；for (i二0; i10; i+) printf (z，%d

11、datai); putchar (? n');while (n<=10) for (i二0;i<10;i+) 1sd=(datai/n)%10);templsdorderlsd=datai; orderlsd+;printf (n 重新排列：);for (i二0;i<10;i+) if (orderi!=0)for (j=0;j<orderi;j+) datak=tempij;printf(，z%d ",datak);k+;orderi=0;n*=10;k=0; putchar c n'); printf ("n 排序后：)； for

12、 (i=0; i<10; i+) printf (，z%d ", datai); return 0;（二）各种排序方法性能比较表排序方法时间复杂度平均时间复杂度空间复杂度稳定性最好最坏直接插入排序0(n)0(r/2)0(2)0(1)稳定希尔排序xx0(n 1. 5)0(1)不稳定冒泡排序0(n)0(12)0(rt2)0(1)稳定快速排序0(nlog(2)n)0(n2)0(nlog2n)0(nlog2n)不稳定直接选择排序0(rt2)0(12)0(rt2)0(1)不稳定堆排序0(nlog2n)0(nlog2n)0(nlog2n)0(1)不稳定归并排序0(nlog2n)0(nlog

13、2n)0(nlog2n)0(n)稳定基数排序0(d(n+rd)0(d(n+rd)0(d(n+rd)0 (n+rd)稳定二、查找给定一个值k,在含有n个结点的表屮找出关键字等于给定值k的结点。（-）主要查找及描述1、顺序查找含义：顺序查找也称为线性查找，从数据结构线性表的一端开始，顺序扫描, 依次将扫描到的结点关键字与给定值k相比较，若相等则表示杳找成功；反z, 查找失败。基本思想：从线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与 给定值k相比较。算法描述： int seqsearch（seqlist r, keytype k） int i;ro.key=k;for（i=n;ri key

14、!二k;i-）;return i;2、二分查找含义：二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要 求线性表是有序表，即表中结点按关键字有序，并且耍用向量作为表的存储 结构。基本思想：首先确定该区间的屮点位置：mid二（low+high）/2（取不大于求出 的数的整数）；然后将待查的k值与rmid, key比较：若相等，则查找成功 并返回此位置。否则需确定新的查找区间，继续二分查找：k>rmid.key, 则 low=mid+l;k<rmid, key,则 high二midt。算法描述： int binsearch （seqlist r, key type k） in

15、t low =1,high=n, mid;while （low<=high）mid二（low+high）/2;if （rmid. key=k）return mid;if （rmid. key>k）high=mid-1;elselow二mid+1;return 0;3、分块查找含义：顺序表的分块查找乂称表索引顺序查找。它是一种性能介于顺序查 找和二分查找z间的查找算法。基本思想：首先杳找索引表。索引表是有序表，可采用二分查找或顺序查 找，以确定待查的结点在哪一块。然后在已确定的块中进行顺序查找。出于块内 无序，只能用顺序查找。4、散列表查找设所有可能出现的关键字集合记为u （简称全集

16、）。实际发生（即实际存储） 的关键字集合记为k （| k |比| u |小得多）o散列函数的构造方法：二次方取中法（先通过求关键字的二次方值扩大相近 数的差别，然后根据表长度取中间的几位数作为散列函数值）、数字分析法（对关键字进行分析，取关键字的若干位或其组合作哈希地址)、直接定址法(取关 键字或关键字的某个线性函数作哈希地址，即h(key)二key)、相乘取整法(首 先用关键字key乘上某个常数a(o<a<1),并抽取出key. a的小数部分；然后用m 乘以该小数后取整)、随机数法(选择一个随机函数，取关键字的随机函数值为 它的散列地址，即h (key) =random (key

17、)、除余法(常用方法,以表长m来除 关键字，取其余数作为散列地址，即h (key) =key%m,该方法的关键是选取m, m 最好为索数。)散列表会出现冲突现象(两个不同的关键字，由于散列函数值相同，因而被 映射到同一表位置上，该现彖称为冲突或碰撞)。处理冲突的方法：(1) 开放地址法：线性探查法(探查序列hi=(h(key)+i)%m0=<i=<m-l);二次探查法(探査序列 hi=(h(key)+i*i)%m 0=<i=<m-l)(2) 拉链法：将所有关键字为同义词的结点链接在同一个单链表 中。优点：拉链法处理冲突简单，口无堆积现彖，即非同义词决不会发 生冲突，因此

18、平均查找长度较短；由于拉链法屮各链表上的结点空间是 动态屮请的，故它更适合于造表前无法确定表长的情况；开放地址法为 减少冲突，要求装填因子a较小，故当结点规模较人时会浪费很多空间。 而拉链法屮可取小二1,且结点较大吋，拉链法屮增加的指针域可忽略不 计，因此节省空间；再用拉链法构造的散列表中，删除结点的操作易于 实现。缺点：指针需要额外的空间，故当结点规模较小时，开放地址法较 为节省空间，而若将节省的指针空间用來扩大散列表的规模，可使装填 因子变小，这又减少了开放地址法屮的冲突，从而提高平均查找速度。(-)各种查找方法的优缺点1>顺序查找：优点：算法简单，11对表的结构无任何要求，无论是用向量还是用链表来存 放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点：查找效率低，当n较大时不宜采用顺序查找。2、二分查找：优点：效率高。缺点：只适用于