当前位置：文档之家 › 《数据结构》(C语言版)第十章_内部排序

《数据结构》(C语言版)第十章_内部排序

  • 格式：ppt
  • 大小：1.44 MB
  • 文档页数：115

下载文档原格式

  / 115

合集下载

数据结构-内排序

数据结构-内排序

Shell排序的性能分析
Shell排序的时间复杂度在O(nlog2n)和O(n2)间， Knuth的 统计结论是，平均比较次数和记录平均移动次数在n1.25与 1.6n1.25之间
Shell排序是一种不稳定的排序方法
最后谈一下delta的取法。 Shell最初的方案是delta=n/2， delta=delta/2，直到delta=1。Knuth的方案是delta=delta/3 +1。其它方案有：都取奇数为好；或delta互质为好等等。 而使用象1, 2, 4, 8, …或1, 3, 6, 9, …这样的增量序列就不太 合适，因为这样会使几个元素多次被分到一组中，从而造 成重复排序，产生大量无用的比较操作
另外，在无序子表中向前移动的过程中，如果没 有交换元素，则说明无序子表已有序，无须再做 排序
24
冒泡排序算法实现
1 void bubble_sort(RecType R[ ], int n) { 2 //待排序元素用一个数组R表示，数组有n个记录
3 int i, j; 4 bool swap=TRUE; //判断无序子表是否已有序的变量
内排序和外排序 按照排序过程中使用内、外存的不 同将排序方法分为内排序和外排序。若待排序记录全 部在内存中，称为内排序；若待排序记录的数量很大， 以致内存一次不能容纳全部记录，在排序过程中需要 进行内、外存交换，称为外排序。本章仅讨论内排序
内排序可分为五大类：插入排序、交换排序、选择排 序、归并排序和基数排序
直接插入排序(straight insert sort) 折半插入排序(binary insert sort) Shell排序(Shell sort)
10
10.2.1 直接插入排序举例

数据结构-第十章-内部排序

数据结构-第十章-内部排序

0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6



最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort

[新版]什么是内排序

[新版]什么是内排序

第十章综合题1.什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?2.设待排序的关键字序列为(15, 21, 6, 30, 23, 6′, 20, 17), 试分别写出使用以下排序方法每趟排序后的结果。

并说明做了多少次比较。

(1) 直接插入排序(2) 希尔排序(增量为5,2,1) (3) 起泡排序(4) 快速排序(5) 直接选择排序(6) 锦标赛排序(7) 堆排序(8) 二路归并排序(9) 基数排序3.在起泡排序过程中，什么情况下关键字会朝向与排序相反的方向移动，试举例说明。

在快速排序过程中有这种现象吗？4.快速排序在什么情况下所需关键字的比较次数最多？此时关键字比较次数应为多少？5.用直接插入排序方法对序列(94,32,40,90,80,46,21,69)进行排序（由小到大），试写出排序的过程。

6.已知初始序列为(125 ，11， 22， 34， 15， 44， 76， 66， 100， 8 ，14， 20， 2，5， 1)，写出采用希尔排序算法排序的每一趟的结果（增量为5，3，1）。

7.写出对初始序列(50,72,43,85,75,20,35，45，65，30)进行直接选择排序的过程。

8.若用冒泡排序对关键字序列(18,16,14,12,10,8),进行从小到大的排序，所需进行的关键字比较次数是多少。

9.给出关键字序列(27，18，21，77，26，45，66，34)，试写出快速排序过程。

10.无序序列为(10，2，13，15，12，14)，用堆排序方法从小到大排序，画出堆排序的初态、建堆和重建堆的过程。

11.写出对序列(28，16，32，12，60，2，5，72)进行2路归并排序的过程。

12.给出如下关键字序列(321，156，057，046，028，007，331，033，034，063)，试按链式基数排序方法，列出每一趟分配和收集的过程。

13.若参加锦标赛排序的关键字有11个，为了完成排序，至少需要多少次关键字比较？14.手工跟踪对以下各序列进行堆排序的过程。

数据结构答案 第10章 排序学习与指导

数据结构答案 第10章 排序学习与指导

第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。

（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。

（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。

2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。

4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。

然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。

5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。

每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。

6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。

第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。

第十章_排序方法(数据结构ppt-严蔚敏)

第十章_排序方法(数据结构ppt-严蔚敏)

第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并与其中 小者进行交换；重复上述操作，直至叶子结点，将得到新的 堆，称这个从堆顶至叶子的调整过程为“筛选”
例 38 50 97 76
13 27 65 49 13 38
97 27 38 50 76
2 (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
i 2 n
若待排序记录是随机的，取平均值 n2 关键字比较次数： T(n)=O(n² ) 4 记录移动次数：
空间复杂度：S(n)=O(1)
n2 4
折半插入排序
排序过程：用折半查找方法确定插入位置的排序叫~
初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp 交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录， 和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有 一个记录为止
x 例 初始关键字： 27 49 i 完成一趟排序： ( 27 38 13 49 65 i 13) 49 97 76 j 97 49 13 j 97 65 49 27 50 j 50)
13 38
76 65 27 49
堆排序：将无序序列建成一个堆，得到关键字最小 （或最大）的记录；输出堆顶的最小（大）值后，使 剩余的n-1个元素重又建成一个堆，则可得到n个元素 的次小值；重复执行，得到一个有序序列，这个过程 叫~ 堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新 的堆？
按排序所需工作量

数据结构课程设计—内部排序算法比较

数据结构课程设计—内部排序算法比较

数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。

内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。

本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

冒泡排序是一种简单直观的排序算法。

它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。

因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。

插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。

选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

以此类推，直到全部待排序的数据元素排完。

选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。

快速排序是一种分治的排序算法。

它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。

快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。

然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。

归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。

数据结构(C语言版)9-12章练习 答案 清华大学出版社

数据结构（C语言版）9-12章练习答案清华大学出版社9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A)个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。

(错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。

（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。

要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

数据结构(严蔚敏)第10章


一、什么是排序？
排序是计算机内经常进行的一种操作， 其目的是将一组“无序”的记录序列调 整为“有序”的记录序列。
例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75
调整为
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 .页 08.06.2020
10. 2 插入排序
.页 08.06.2020
一趟直接插入排序的基本思想：
有序序列R[1..i-1]
无序序列 R[i..n]
R[i]
有序序列R[1..i]
无序序列 R[i+1..n]
.页 08.06.2020
实现“一趟插入排序”可分三步进行：
1．在R[1..i-1]中查找R[i]的插入位置，
R[1..j].key R[i].key < R[j+1..i-1].key；
有序序列区 无 序 序 列 区
经过一趟排序
08.06.2020
有序序列区 无 序 序 列 区
.页
基于不同的“扩大” 有序序列长 度的方法，内部排序方法大致可分 下列几种类型：
插入类 交换类 选择类
归并类 其它方法
.页 08.06.2020
#待de排fin记e M录A的XS数IZ据E 类10型00定// 义待排如顺下序:表最大长度
第十章 排序
.页 08.06.2020
【课前思考】
1. 你熟悉排序吗？你过去曾经学过哪些排序方法？ 在第一章中曾以选择排序和起泡排序为例讨论算 法实践复杂度，不知你还记得吗？ 2. 你自己有没有编过排序的程序？是用的什么策 略？
.页 08.06.2020
【学习目标】

数据结构 排序

选择排序种类： 简单选择排序 树形选择排序 堆排序
2019/9/7
30
10.4.1 简单选择排序
待排记录序列的状态为：
有序序列R[1..i-1] 无序序列 R[i..n]
有序序列中所有记录的关键字均小于无序序列中记 录的关键字，第i趟简单选择排序是从无序序列 R[i..n]的n-i+1记录中选出关键字最小的记录加入 有序序列
2019/9/7
5
排序的类型定义
#define MAXSIZE 20 // 待排序记录的个数
typedef int KeyType;
typedef struct
{ KeyType key;
InfoType otherinfo; ∥记录其它数据域
} RecType;
typedef struct {
RecType r[MAXSIZE+1];
分别进行快速排序：[17] 28 [33] 结束 结束
[51 62] 87 [96] 51 [62] 结束
结束
快速排序后的序列： 17 28 33 51 51 62 87 96
2019/9/7
26
自测题 4 快速排序示例
对下列一组关键字 （46,58,15,45,90,18,10,62） 试写出快速排序的每一趟的排序结果

final↑ ↑first
i=8
[51 51 62 87 96 17 28 33]

final↑ ↑first
2019/9/7
14
希尔(shell )排序
基本思想：从“减小n”和“基本有序”两 方面改进。
将待排序的记录划分成几组，从而减少参 与直接插入排序的数据量，当经过几次分 组排序后，记录的排列已经基本有序，这 个时候再对所有的记录实施直接插入排序。

数据结构(C语言版)实验报告 (内部排序算法比较)

《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。

数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData { int num; //存放关键字}Data; typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE]; //用数组存放所有的随机数} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数void InitLinkList(LinkList* L) //初始化链表BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小void Display(LinkList* L) //显示输出函数void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/void RandomNum(){int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;}/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum();for(i=0; i小于<MAXSIZE; i++)L->Record[i].num<=RandArray[i]; L->Length<=i;}BOOL LT(int i, int j,int* CmpNum){(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;若打开文件的指令不为空则//通过文件指针f打开文件为条件判断{ //是否应该打开文件输出“can't open file”;exit(0); }for (i=0; i小于L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);通过文件指针f关闭文件;三、调试分析1.调试过程中遇到的问题及经验体会:在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

§10.2 插入排序
一、直接插入排序 二、折半插入排序 三、表插入排序 希尔（ 四、希尔（Shell）排序 ）
一趟插入排序的基本思想：
有序序列R[1..i-1] R[i] 无序序列 R[i..n]
有序序列R[1..i]
无序序列 R[i+1..n]
实现“一趟插入排序”可分三步进行： 实现“一趟插入排序”可分三步进行： 1．在R[1..i-1]中查找R[i]的插入位置， ．
例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75
调整为
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97
一般情况下， 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即 在它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn ≤ 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作 操作称作排序 排序。 操作 排序
从记录的无序子序列中“选择” 关键字最小或最大的记录，并将它 加入到有序子序列中，以此方法增 加记录的有序子序列的长度。
4. 归并类
通过“归并”两个或两个以上的 “归并” 记录有序子序列，逐步增加记录有 序序列的长度。
5. 其它方法
待排记录的数据类型定义如下: 待排记录的数据类型定义如下
#define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 闲置 int length; // 顺序表长度 } SqList; // 顺序表类型
时间复杂度： 时间复杂度：
稳定的
折半插入排序比直接插入排序明显地 减少了关键字间的“比较”次数，但记 录“移动”的次数不变。 T(n)=O(n²) 空间复杂度： 空间复杂度：S(n)=O(1)
三、表插入排序
为了减少在排序过程中进行的 “移动”记录的操作，必须改变排序 过 程中采用的存储结构。利用静态链表 静态链表 进行排序，并在排序完成之后，一次 在排序完成之后， 在排序完成之后 性地调整各个记录相互之间的位置， 性地调整各个记录相互之间的位置 即将每个记录都调整到它们所应该在 的位置上。
内部排序的过程是一个逐步扩大 逐步扩大 记录的有序序列长度 有序序列长度的过程。 有序序列长度 有序序列区 无 序 序 列 区 经过一趟排序 有序序列区 无 序 序 列 区
基于不同的“扩大 有序序列长 扩大” 扩大 度的方法，内部排序方法 方法， 方法 内部排序方法大致可分 下列几种类型：
插入类 归并类
R[1..j].key ≤ R[i].key < R[j+1..i-1].key；
2．将R[j+1..i-1]中的所有记录均后移 ．
一个位置；
3．将R[i] 插入(复制)到R[j+1]的位置上。 ．
一、直接插入排序
利用 “顺序查找”实现 顺序查找” “在R[1..i-1]中查找R[i]的插入位置”
重难点内容： 重难点内容：
直接插入排序、折半插入排序、 起泡排序、简单选择排序等排序方 法的算法思想、实现和效率分析。 希尔排序、快速排序、堆排序、 归并排序等高效方法。
§10.1 概述
一、什么是排序 二、内部排序和外部排序 三、内部排序的方法
什么是排序？ 一、什么是排序？
排序是计算机内经常进行的一种操作， 其目的是将一组“无序”的记录序列调 “无序” 整为“有序” 整为“有序”的记录序列。
交换类
选择类
其它方法
1. 插入类
将无序子序列中的一个或几 个记录“插入 插入”到有序序列中， 插入 从而增加记录的有序子序列的长 度。
2. 交换类
通过“交换”无序序列中的记 “交换” 录从而得到其中关键字最小或最大 的记录，并将它加入到有序子序列 中，以此方法增加记录的有序子序 列的长度。
3. 选择类
如何在排序之后调整记录序列？ 如何在排序之后调整记录序列？ 算法中使用了三个指针： 其中：p指示第i个记录的当前位置 i指示第i个记录应在的位置 q指示第i+1个记录的当前位置
例如： 例如：
表表表排序 .swf
void Arrange ( SLinkListType &SL, int n ) { p = SL.r[0].next; // p指示第一个记录的当前位置 for ( i=1; i<n; ++i ) { while (p<i) p = SL.r[p].next; q = SL.r[p].next; // q指示尚未调整的表尾 if ( p!= i ) { SL.r[p]←→SL.r[i]; // 交换记录，使第 个记录到位 交换记录，使第i个记录到位 SL.r[i].next = p; // 指向被移走的记录 } p = q; // p指示尚未调整的表尾，
假设Ki=Kj (1≤i,j≤n,i≠ j)，且在排序 前的序列中Ri领先于Rj（即i<j）。 若排序后的序列中Ri仍领先于Rj， 则称所用的排序方法是稳定 稳定的； 稳定 反之，若可能排序后的序列中Rj领 先于Ri，则称使用的排序方法是不稳 不稳 定的。
例如：
排序前 （52, 49, 80, 36, 14, 49） ） 排序后 （14, 36, 49, 49, 52, 80） ） （14, 36, 49, 49, 52, 80） ）
void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。
for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) {
直直表表排序.swf
L.r[0] = L.r[i]; // 复制为监视哨 L.r[i] = L.r[i-1]; for ( j=i-2; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置
稳定的
最好的情况（关键字在记录序列中顺序有序）： 最好的情况（关键字在记录序列中顺序有序）： 的情况
“移动”的次数： 移动” 移动
∑1 = n −1
i =2
n
0
“移动”的次数： 移动” 移动
最坏的情况（关键字在记录序列中逆序有序）： 最坏的情况（关键字在记录序列中逆序有序）： 的情况
“比较”的次数： 比较” 比较
low = 1; high = i-1; while (low<=high) { m = (low+high)/2; // 折半
if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 }
例如: 例如
稳定 不稳定
二、内部排序和外部排序
若整个排序过程不需要访问外存 不需要访问外存便能 不需要访问外存 完成，则称此类排序问题为内部排序 内部排序； 内部排序 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 外部排序。 完成，则称此类排序问题为外部排序 外部排序
三、内部排序的方法
对于在查找过程中找到的那些关键 字不小于R[i].key的记录，并在查找的 同时实现记录向后移动； for (j=i-1; R[0].key<R[j].key; --j); R[j+1] = R[j]
R[0] R[i]
j
j= i-1 插入位置
上述循环结束后可以直接进行“插入”
例：待排序序列 （56，38，49，40，95） ， ， ， ， ）
#define SIZE 100 //静态链表容量 Typedef struct{ //表结点类型 表结点类型 RcdType rc; //记录项 int next; //指针项 }SLNode; Typedef struct{ //静态链表类型 静态链表类型 SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 }SLinkListType;
第十章 内部排序
10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的综合比较
学习提要： 学习提要：
1. 了解排序的定义 定义和各种排序方法的特点。 定义 2.熟悉各种方法的排序过程及其依据的原则 方法的排序过程及其依据的原则。 方法的排序过程及其依据的原则 3. 掌握各种排序方法的时间复杂度 时间复杂度的分析方法。 时间复杂度 能从“关键字间的比较次数”分析排序算法的 “关键字间的比较次数” 平均情况和最坏 最坏情况的时间性能。 平均 最坏 4. 理解排序方法“稳定”或“不稳定”的含义， 弄清楚在什么情况下要求应用的排序方法必须 是稳定的。
void BiInsertionSort ( SqList &L ) { for ( i=2; i<=L.length; ++i ) { L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] 中折半查找插入位置； 在 L.r[1..i-1]中折半查找插入位置； 中折半查找插入位置 for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } // for } // BInsertSort