第十章数据结构之排序.ppt

§:每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录简单选择排序8325916[1]325986[12]35986[123]5986[1235]986[12356]89[12356]89[123568]9[1235689]voidselectsort(sqlist&l){for(i=1;i<;i++){ minloc=i; for(j=i+1;j<=;j++) if([j].key<[minloc].key) minloc=j; if(i!=minloc){ x=[i]; [i]=[minloc]; [minloc]=x;}}}二、堆排序堆是满足下列性质的数列{r1,r2,…,rn}:或堆的定义:{12,36,27,65,40,34,98,81,73,55,49}例如:是小顶堆(小顶堆)(大顶堆)8173554965403498362712不是堆123627654981735540349814而数列{12,36,27,65,40,14,98,81,73,55,49}堆排序思路:,,并将其与队尾元素交换,筛选(所谓“筛选”指的是,对一棵左/右子树均为堆的完全二叉树,调整根结点使整个二叉树也成为一个堆。)。例如:{40,55,49,73,12,27,98,81,64,36}:从最后一个非终端结点(n/2)处开始筛选;i=i-1,筛选,直至堆形成。二、堆排序voidheapadjust(sqlist&h,ints,intm)//[s..m][s].key之外均满足堆的定义,本函数调整//h,r[s],[s..m]成为一个大顶堆{rc=[s];for(j=2*s;j<=m;j*=2){if(j<m&&[j].key<[j+1].key)j++;//j为左右孩子中较大者下标if([j].key>){ [s]=[j];s=j;//大的孩子上移,s记录下可插入位置 } elsebreak;//,强制结束循环 }[s]=rc;}voidheapsort(sqlist&h){for(i=;i>0;i--) heapadjust(h,i,);//初建堆 for(i=;i>1;i--){ printf(“%5d”,[1].key); t=[1];[1]=[i];[i]=t;//堆顶和堆尾交换 heapadjust(h,1,i-1); } printf(“%5d”,[1].key);}时间复杂度:O(nlogn)(最好、最坏情况均是)。在堆排序中,除初建堆以外,其余调整堆的过程最多需要比较树深次,因此,与简单选择排序相比时间效率提高了很多;另外,不管原始记录如何排列,堆排序的比较次数变化不大,所以说,堆排序对原始记录的排列状态并不敏感。空间复杂度O(1)。在堆排序算法中只需要一个暂存被筛选记录内容的单元,所以堆排序是一种速度快且省空间的排序方法。堆排序不稳定。§“归并”是指两个或两个以上的有序表组合成一个新的有序表例:2-路归并排序:原序列n个记录,看成n个有序子表(每子表长1)然后两两归并,得到┏n/2┓个长度为2或1的有序子表,然后再两两归并…,直到得到一个长度为n的有序表为止。初始 [49][38][65][97][76][13][27]一趟归并后[3849][6597][1376][27]二趟归并后[38496597][132776]三趟归并后[13273849657697]共进行┏log2n┓趟,每趟n(所有子表长度和)∴时间复杂度O(nlogn)空间复杂度O(n)归并排序是稳定的§。多关键字排序例:***牌,设“花色”高于“面值”。可按花色分为四组,然后对每一组按“面值”排序,最后把这四堆合起来。 MSD最高位优先法也可先分为13堆(同面值为一堆),然后13堆牌由小到大叠在一起(“A”在最上面),然后再分成4堆(按花色),最后把这4堆牌合起来。 LSD最低位优先法基数排序把关键字看成若干个关键字的复合,例:0<=k<=999,k看成由3个关键字(k2,k1,k0)组成,0<=ki<=9。若k是由5个大写字母组成的字符串,k看成由5个关键字(k4,k3,k2,k1,k0)组