《数据结构》 内部排序

数据结构 c语言

第十章 内部排序10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序10.6 基数排序

10.7 各种排序方法的综合比较

数据结构 c语言

学习提要：1. 了解排序的定义和各种排序方法的特点。

2.熟悉各种方法的排序过程及其依据的原则。

3. 掌握各种排序方法的时间复杂度的分析方法。 能从“关键字间的比较次数”分析排序算法的 平均情况和最坏情况的时间性能。

4. 理解排序方法“稳定”或“不稳定”的含义， 弄清楚在什么情况下要求应用的排序方法必须 是稳定的。

数据结构 c语言

重难点内容：直接插入排序、折半插入排序、起泡排序、简单选择排序等排序方 法的算法思想、实现和效率分析。

希尔排序、快速排序、堆排序、归并排序等高效方法。

数据结构 c语言

§10.1 概述一、什么是排序 二、内部排序和外部排序 三、内部排序的方法

数据结构 c语言

一、什么是排序？排序是计算机内经常进行的一种操作， 其目的是将一组“无序”的记录序列调 整为“有序”的记录序列。

例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为

14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

数据结构 c语言

一般情况下， 假设含n个记录的序列为{ R1, R2, …, Rn } 其相应的关键字序列为 { K1, K2, …,Kn } 这些关键字相互之间可以进行比较，即 在它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …,Rpn } 的操作称作排序。

数据结构 c语言

假设Ki=Kj (1≤i,j≤n,i≠ j),且在排序 前的序列中Ri领先于Rj(即i<j)。 若排序后的序列中Ri仍领先于Rj, 则称所用的排序方法是稳定的；反之，若可能排序后的序列中Rj领 先于Ri,则称使用的排序方法是不稳 定的。

数据结构 c语言

例如：排序前 (52, 49, 80, 36, 14, 49)排序后

(14, 36, 49, 49, 52, 80) (14, 36, 49, 49, 52, 80)

稳定

不稳定

数据结构 c语言

二、内部排序和外部排序若整个排序过程不需要访问外存便能

完成，则称此类排序问题为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序。

数据结构 c语言

三、内部排序的方法内部排序的过程是一个逐步扩大

记录的有序序列长度的过程。 有序序列区 无 序 序 列 区 经过一趟排序有序序列区 无 序 序 列 区

数据结构 c语言

基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分 下列几种类型：

插入类 归并类

交换类

选择类

其它方法

数据结构 c语言

1. 插入类将无序子序列中的一个或几

个记录“插入”到有序序列中，从而增加记录的有序子序列的长 度。

数据结构 c语言

2. 交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大 的记录，并将它加入到有序子序列

中，以此方法增加记

录的有序子序列的长度。

数据结构 c语言

3. 选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它 加入到有序子序列中，以此方法增

加记录的有序子序列的长度。

数据结构 c语言

4. 归并类通过“归并”两个或两个以上的 记录有序子序列，逐步增加记录有

序序列的长度。

5. 其它方法

数据结构 c语言

待排记录的数据类型定义如下:#define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲臵 int length; // 顺序表长度 } SqList; // 顺序表类型