各种经典排序算法.ppt

《各种经典排序算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、本节基本内容与要求基本内容顺序查找、二分查找、二叉树查找以及散列表上查找及算法思想排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法要求掌握线性表、树和散列表(或称哈希表)的查找方法及算法实现以及各种查找方法的应用熟练掌握选择、插入、交换和归并四类排序的基本思想和算法1.4内部排序一、基本概念二、插入排序三、交换排序四、选择排序五、归并排序一、基本概念1.排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。例如：下列是一组记录对应的关键字序列(52,49,80,36,14,58,61,23,97,

2、75)调整为(14,23,36,49,52,58,61,75,80,97)2.排序的定义假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。3、排序的基本操作排序的概念：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。排序过程的组成步骤：首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。对记录的关键字大

3、小进行比较将记录从一个位置移动到另一个位置当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。4、排序的稳定性若有：{R1,...,Ri,...,Rj,.....}且关键字：Ki=Kji<>j排序后：{Ri,Rj,.....}则称该排序结果具有稳定性。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。内部排序：是指在排序的整个过程中，数据全部存放在计算机的内存储器里，

4、并且在内存储器里调整数据的位置；当文件很大以致内存不足以存放全部数据时，在排序过程中需要对外存进行存取访问，称这种借助于外存储器进行排序的方法为外部排序。注意：①内排序适用于记录个数不很多的小文件②外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。5、排序的分类每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。把新元素（未排序的元素的关键字）逐个插入正在增长的顺序表中。寻找插入位置的方法：线性插入排序对半插入排序希尔排序二、插入排序有序序列L.r[1..i-1]L.r

5、[i]无序序列L.r[i..n]有序序列L.r[1..i]无序序列L.r[i+1..n]1、线性插入排序基本思想：每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置。重复该工作，直至有序区包含所有元素。方法：具体方法：先将第一个数据看成是一个有序的子序列，然后从第2个数据起逐个插入到这个有序的子序列中去，相应的元素要移动。3．将L.r[i]插入到L.r[j+1]的位置上。2．将L.r[j+1..i-1]中的所有记录均后移一个位置；1．在L.r[1..i-1]中查找L.r[i]的插入位置，L.r[1..j]L.r[i]

6、r[j+1..i-1]；该算法适合于n较小的情况，时间复杂度为O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]线性插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次例：voidinsertSort(RedTypeL[],intn){inti,j;for(i=2;i<=n;i++){L[0]=L[i];//作为监视哨for(

7、j=i-1;L[0].key

8、ntar[n];intc,t;voidd_insort(a)inta[n];{inti,j;for(i=2;i<=n;i++){t=a[i];j=i-1;while((j>0)&&(t