数据结构、算法与应用 C++语言描述排序总结课件.ppt

《数据结构、算法与应用 C++语言描述排序总结课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Agenda名次排序选择排序冒泡排序插入排序基数排序堆排序归并排序快速排序1、名次排序元素在队列中的名次(rank)可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。例如，给定一个数组a=[4,3,9,3,7]作为队列，则各元素的名次为r=[2,0,4,1,3]。1、名次排序templatevoidRank(Ta[],intn,intr[]){//计算a[0:n-1]中n个元素的排名for(inti=0;i

2、intj=0;jvoidRearrange(T*&a,intn,intr[]){//按序重排数组a中的元素，使用附加数组uT*u=newT[n+1];//在u中移动到正确的位置for(inti=0;i

3、作次数为：n1、名次排序2、选择排序思想：首先找出最大的元素，把它移动到a[n-1]，然后在余下的n-1个元素中寻找最大的元素并把它移动到a[n-2]，如此进行下去。templateintMax(Ta[],intn){//寻找a[0:n-1]中的最大元素intpos=0;for(inti=1;ivoidSelectionSort(Ta[],in

4、tn){//对数组a[0:n-1]中的n个元素进行排序for(intsize=n;size>1;size--){intj=Max(a,size);//size-1次比较Swap(a[j],a[size-1]);//移动3次}}按照元素的比较次数来估算函数的时间复杂性。每次调用Max(a,size)需要执行size-1次比较，所以总的比较次数为：1+2+3+…+n-1=(n-1)n/2。移动次数为：3（n-1）2、选择排序上述程序中选择排序函数的一个缺点是：即使元素已经按序排列，程序仍然继续运行。为了终止不必要的循环，在查找最大元素期间，可以顺便检查

5、数组是否已按序排列。2、选择排序templatevoidSelectionSort(Ta[],intn){//及时终止的选择排序boolsorted=false;for(intsize=n;!sorted&&(size>1);size--){intpos=0;sorted=true;//找最大元素for(inti=1;i

6、元素在首位，其他元素已经有序。最好最坏比较n-1n(n-1)/2移动33(n-1)2、选择排序3、冒泡排序采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中，对相邻的元素进行比较，如果左边的元素大于右边的元素，则交换这两个元素。在一次冒泡过程结束后，可以确信最大的元素肯定在最右边的位置上。例:[11，15,3,9，20，7,1]，在第一次冒泡过程结束后，得到？3、冒泡排序templatevoidBubble(Ta[],intn){//把数组a[0:n-1]中最大的元素通过冒泡移到右边for(inti=0;i

7、a[i]>a[i+1])Swap(a[i],a[i+1]);}3、冒泡排序templatevoidBubbleSort(Ta[],intn){//对数组a[0:n-1]中的n个元素进行冒泡排序for(inti=n;i>1;i--)Bubble(a,i);}3、冒泡排序如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列，没有必要再继续进行冒泡过程。3、冒泡排序templateboolBubble(Ta[],intn){//把a[0:n-1]中最大元素冒泡至右端boolswapped=false;//尚未发生交

8、换for(inti=0;ia[i+1]){Swap(a[i],a[i+1]);swapp