文档介绍：数据结构(shù jù jié ɡòu)c语言5
第一页，共92页。
排序是指将一组数据元素按某个数据项值的大小排列成一个有序序列的过程。
排序是计算机程序设计中经常使用的一种重要操作，是组织数据和处理数据的最基本最重要的运算之一。
排序被广泛应用于数据处理、情报检索、商业金融(jīnróng)等许多领域。
第1页/共92页
第二页，共92页。
分配(fēnpèi)排序（基数排序）
第2页/共92页
第三页，共92页。
1．记录、关键码和排序表：
记录： 数据元素
关键码（或排序码）：作为排序依据的数据项称为数据元素的关键码。
排序表：若干个（n个）排序纪录组成的集合。
排序表也称成为文件，主要操作是排序。
2．非递减(dìjiǎn)序列、递减(dìjiǎn)序列、非递增序列、递增有序
3．稳定排序和非稳定排序
稳定排序 ：记录的相对位置在排序前后不发生变化
不稳定排序：
第3页/共92页
第四页，共92页。
4．内部排序和外部排序
待排序的表完全放在内存中称为内排序
5．对排序方法的评价
空间性能：除排序表以外的内存占用情况。
时间性能：比较关键码的次数，数据移动的次数。
它们往往(wǎngwǎng)是排序表规模（n）的函数
第4页/共92页
第五页，共92页。
6. 记录和排序表的数据结构
在本章的讨论中，除特殊声明外，一般采用顺序结构存储排序表。
记录和排序表的类型定义如下(rúxià)：
#define MAXNUM … /* MAXNUM 为足够大的数*/
typedef struct
{ keytype key; /*关键码字段*/
…… /*其它信息*/
} datatype; /*记录类型 RecNode*/
datatype R[MAXNUM]; /*定义排序表的存储*/
如不加特别说明，排序表中的记录R1…Rn存放在R[1]…R[n]分量中，R[0]分量闲置或做监视哨（n是排序表中记录的个数）。
第5页/共92页
第六页，共92页。
分配(fēnpèi)排序（基数排序）
第6页/共92页
第七页，共92页。
1 直接插入排序
2 折半(zhébàn)插入排序
3 *表插入排序
3 希尔排序
插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小(dàxiǎo)插入到前面已经排好序的子表的适当位置，直到全部记录插入完成，整个表有序为止。
第7页/共92页
第八页，共92页。
直接插入排序
直接插入排序是一种简单的插入排序方法，基本(jīběn)思想为：在R[1]至R[i-1]长度为i-1的子表已经有序的情况下，将R[i]插入，得到R[1]至R[i]长度为i 的子表有序，这样通过n-1趟（i=2..n）之后，R[1]至R[n]有序。
第8页/共92页
第九页，共92页。
例如，对于以下序列（为简便起见，每一个记录只列出其排序码，用排序码代表记录）：
[ 10 18 20 36 60 ] 25 30 18 12 56
其中，前5个记录组成的子序列是有序的，这时要将第6个记录插入到前5个记录组成的有序子序列中去，得到一个含有6个记录的新有序序列。完成这个插入首先需要(xūyào)找到插入位置：20<25<36，因此25应插入到记录20和记录36之间，从而得到以下新序列：
[ 10 18 20 25 36 60] 30 18 12 56
这就是一趟直接插入排序的过程。
直接插入排序：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个(zhúgè)向有序表中进行插入操作，从而得到n个记录按关键码有序的表。
第9页/共92页
第十页，共92页。