数据结构（第二版） 课件 包振宇 第八章 排序

《数据结构（第二版） 课件 包振宇 第八章 排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、概述选择排序直接插入排序冒泡排序希尔排序堆排序快速排序合并排序典型例题第八章排序什么是排序(Sorting)？简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来。排序是计算机中经常遇到的操作。排序的几个基本概念数据表(DataList)待排序的数据对象的有限集合。关键码(Key)作为排序依据的数据对象中的属性域。主关键码不同的数据对象若关键码互不相同，则这种关键码称为主关键码。排序的确切定义使一组任意排列的对象变成一组按关键码线性有序的对象。排序的几个基本概念排序算法的稳定性判断标准：关键码相同的数据对象在排序过程中是否保持前后次序不变。如2,2*

2、,1，排序后若为1,2*,2则该排序方法是不稳定的。内排序与外排序区分标准：排序过程是否全部在内存进行。排序的时间开销它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量8.1选择排序选择排序的基本思想是反复从还未排好的那部分线性表中选出键值最小的结点，并按从线性表中送出的顺序排列结点，重新组成线性表。直至未排序的那部分为空，则重新形成的线性表是一个有序的线性表。1.顺序存储线性表的选择排序顺序存储线性表的选择排序，若线性表用顺序存储实现，为存放选出的结点并重新组成线性表，选择排序算法可具体为：选出键值最小的结点与线性表的第1

3、个结点交换，选出键次最小的结点与线性表的第2个结点交换；依次类推，直至选出键值次最大的结点与线性的最末第2个结点交换；至此，键值最大的结点成为线性的末结点。即依次对i=0,1,2,…，n-2分别执行如下的选择交换步骤：⑴在结点序列e[i],e[i+1],…,e[n-1]中选择键值最小的结点e[k];⑵当k不等于i时，将e[i]与e[k]换。经过上述n-1次选择和交换，最终完成顺序存储线性表的排序。例8-1顺序存储线性表的选择排序流程图顺序存储线性表的选择排序函数函数如下：voidss-sort(e,n)inte[];/*存储线性表的数值*/intn;/*线

4、性表的结点个数*/{inti,j,k,t;for(i=0;ie[j])k=j;if(k!=i){/*e[i]与e[k]交换*/t=e[i];e[i]=e[k];e[k]=t;}}}n个结点线性表采用选择排序，当外循环i=0时，内循环作n-1比较；当外循环i=1时，内循环n-2比较；依此类推，当外循环i=n-2时，内循环作1次比较。因此，总是比较次数为n(n-1)/2.因为

5、相等的两元素，相对在前的可能被交换到更后面，所以选择排序是不稳定的。2.链式存储线性表选择排序对于链式存储的线性表，选择排序过程，依次选出的键值从小到大的结点，可顺序组织成有序链表，即每一次选出的键值最小的结点在已排序部分完成的有序链表的末尾。例8.2链式存储线性表选择排序流程图链式存储线性表选择排序函数structnode*ls-sort(structnode*h){structnode*t,*s,*tail,*u,*v;s=NULL;/*置有序链表头指针为空*/while(h!=NULL){/*在剩余的链接表中找键值最小的结点*/for(t=u=h;u

6、->link!=NULL;u=->link)if(u->link–)datadata){v=u;/*保留键值变小的结点的前驱结点指针*/t=u->likk;/*找到一个键值更小的结点*/}if(t==h)h=h->link;/*键值最小结点是链表的首结点*/elsev->link=t->link;/*键值最小结点脱钩*/if(s==NULL)tail=s=t;/*第一次找到键值最小结点*/elsetail=tail->link=t;}if(s!=NULL)tail->link=NULL;/*让有序链表到止结束*/returns;/*返回有序链表首结

7、指针*/}例8.3例8.3：完整程序：函数psort2()实现将含n整数的数组a[]的不同元素按从小到大顺序存于数组a[]中。函数psort2()的实现方法是从未确定的元素列中找出最小元素，并将a[]中第i最小元素交换至a[i]位置。如果该最小元素比已确定的最后一个最小元素大，则将它接在已确定的最小元素序列的后面；否则，忽视该元素。intpsort2(inta[],intn){inti,j,k,p,t;for(i=0,k=0;i<(1);i++){for(j=i+1,(2);ja[j])p=j;if(p!=i){t=a[p];

8、a[p]=a[i];a[i]=t;}if(3)k++;elseif