内部排序-数据结构datastructure

《内部排序-数据结构datastructure》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(DATASTRUCTURE)计算机科学与技术学院第十章排序概述插入排序交换排序选择排序归并排序基数排序210.1概述1)基本概念排序：将一组记录按相应关键字的值递增或递减次序重新排列的过程。关键字(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键字k[i]==k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。32）排序方法的分类

2、根据排序时使用的存储器不同，分为：内部排序:在内存实现，数据对象全部存放在内存，无内外存数据交换；适合少量数据，速度快。外部排序:排序期间全部对象太多，不能同时存放在内存，必须根据排序过程的要求，不断在内外存之间移动；适合大量数据，速度慢。按实现策略，内排序分五大类：插入排序:直接插入、shell排序交换排序：冒泡、快速排序选择排序：简单选择、树型选择、堆排序归并排序：基数排序：4按排序所需工作量，内排序分为：简单排序方法:O(n2)简单排序先进排序方法:O(nlogn)堆排序、快速排序…基数排序方法:O(dn)基数排序3）排序算法的评价标准时间复杂度:排序的时间开销用算法执行中的数据比较

3、次数与数据移动次数来衡量。空间复杂度:算法执行时所需的附加空间。稳定性:简单性:54）本书中待排序数据表的数据类型描述#defineMaxsize50//待排序序列中记录的最大个数待排序表中每个数据元素的数据类型定义typedefstruct{intkey;//表示排序关键字elemtypeotherinfo;//排序记录中的其他所有数据项}Snode;待排序数据表的数据类型定义typedefstruct{SnodeR[Maxsize+1];//存放待排序全体记录intlength;//排序记录个数}SList;610.2插入排序(InsertSorting)1)基本思想：将一个记录插入到

4、已排好序的有序表中，从而得到一个新的、记录数增1的有序表。将顺序存储的n个待排序记录划分为两个区间：一个有序区，一个无序区;初始时：有序区为[R1]，无序区为[R2….Rn]，令i指向无序区中第一个记录，初值i=2。当i≤n时，重复执行：将当前无序区中第一个记录Ri插入到有序区的适当位置，使有序区变为：[R1’….Ri’]，无序区变为[Ri+1….Rn]。当i〉n时，有序区变为[R1’….Rn’]，排序结束。10.2.1直接插入排序72）逐步求精：将Ri插入到有序区[R1….Ri-1]中适当位置，即保持仍然有序。具体做法：当插入第i个对象时，前面的R1,R2….Ri-1已经排好序。这时，用

5、R[i]的关键字与R[i-1],R[i-2],…的关键字顺序进行比较，若比R[i]的关键字大，就后移一个位置，如此重复，直到找到适当的插入位置，即将R[i]插入。8排序过程演示：93）算法实现：voidInsertSort(SqList&L){for(i=2；i<=L.length；i++)if(L.R[i].key

6、位置*/}}104)算法分析时间复杂度：设待排序对象个数为n，则共需n-1趟插入排序。每趟排序过程中关键字比较次数和对象移动次数与对象的初始排列有关。最好情况(正序):最坏情况(逆序):空间复杂度：使用了一个临时空间O(1)稳定性：直接插入排序是一种稳定的排序方法。1110.2.2希尔排序(缩小增量法）1）基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。排序过程：先将整个待排序记录以d1为步长分成若干子序列，把所有相隔为d1的记录放在同一组内；在每个分组内进行直接插入排序；在将整个待排序记录序列以d2(d2<

7、d1