软件_查找和排序_排序 - 副本.ppt

《软件_查找和排序_排序 - 副本.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二节排序一、基本概念二、选择排序三、插入排序四、交换排序五、归并排序一排序基本概念1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。2、排序过程的组成步骤：首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。稳定的排序当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。如果在待排序文件中存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。评价排序算法好坏的标准执行时间所需的辅助空间算

2、法的复杂程度排序方法插入排序选择排序交换排序归并排序线性插入排序对半插入排序简单选择排序堆排序冒泡排序快速排序选择排序——简单选择排序每一趟从待排序的记录中选出关键字最小的记录，顺序存放已排好的子文件的最后(最前)，直到全部记录排序完毕。5412202731141220273513122027451342027125134527122013451227201345122027第1趟第2趟第3趟第4趟第5趟第6趟交换简单选择排序的算法如下：voidSelectSort(RedTypeL[],intn){inti,j,k,t;for(i=1

3、,i<=n;++i）//选择第i小的元素，并交换到位{j=i；for(k=i+1;k<=n;++k)if(L[k].key

4、i≥K2i+1或者Ki≤K2i且Ki≤K2i+1947017465505134212345678堆当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：任一非叶结点的关键字均不小于(或不大于)其左右孩子结点的关键字。9470174655051342123456789470174642550513堆最大值897624331510112536497856(a):堆顶元素取最大值大根堆(b):堆顶元素取最小值小根堆堆排序基本思想因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，

5、它就在序列的第一个位置上然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序区。直到排序完成。9470174642550513初始堆42701746945505131355174694420570堆的构造无序序列r[1：n]构成的完全二叉树，从它最后一个非叶子结点（第n/2个元素）

6、开始直到根结点为止，逐步进行调整即可将此完全二叉树构成堆。调整：与其左右子树根结点值比较，取其中大的进行交换。堆的构造例46551342709405174655134294051770465513429405177012345678堆的构造例465513704294051746551342709405174655134294051770465513429405177012345678对调对调465513709405174212345678对调对调1313堆的构造例4655177042940513465513429405177046551

7、7709405134212345678对调5555对调4694177042550513469417705505134212345678对调4646对调堆的构造例46551342940517709446177042550513944617705505134212345678对调4646对调9470174642550513947017465505134212345678成堆!堆的构造例4655134270940517初始无序结点,从42开始调整4655137042940517将以13为根的子树调整成堆4655177042940513将以55

8、为根的子树调整成堆4694177042550513将以46为根的子树调整成堆9470174642550513成堆4655134294051770调整成堆算法voidSIFT(intr[],inti,intn