资源描述：
《数据结构课程辅导(4)122》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程辅导(4)1222、业精于勤，荒于嬉；行成于思，毁于随——韩愈数据结构课程辅导（4）---排序一、排序的基本概念排序(Sorting)是数据处理领域一种最常用的运算排序的目的之一是方便查找由上一章可知，对于一个顺序存储的线性表，若不经过排序而查找，则时间复杂性为O(n)，若在排序的基础上进行二分查找，则时间复杂性可提高到O(log2n)，效果是相当显著的排序就是把一组记录(元素)按照某个域的值的递增(即由小到大)或递减(即由大到小)的次序重新排列的过程通常把用于排序的域称为排序域或排序项，把该域中的每一个值（它与一个记录相对应）称为排序码为了
2、以后讨论方便，假定排序域的域名用标识符stn表示如对于具有ElemType类型的一条记录x来说，x.stn为它的排序码设待排序的一组n个记录为{R0,R1,...,Rn-1}，对应的排序码为{S0,S1,...,Sn-1}，若排序码的递增次序为{S0',S1',...,Sn-1'}，即S0'≤S1'≤...≤Sn-1'，则排序后的记录次序为{R0',R1',...,Rn-1'}，其中Ri'的排序码为Si'(0≤i≤n-1)；若排序码的递减次序为{S0",S1",...,Sn-1"}，即S0"≥S1"≥...≥Sn-1"，则排序后的记录次序为{R0",R1
3、",...,Rn-1"}，其中Ri"的排序码为Si"(0≤i≤n-1)表4-1职工登记表职工号姓名性别出生日期基本工资(元)100王大明男51/04/25348101吴进男61/03/12374102邢怀学男53/06/28324103王亚兰女41/03/26305104赵利女64/05/03429105刘小平男55/12/18348106李小敏女70/03/26284107卢明男59/12/20324例如，在表4-1中，若以每个记录的职工号为关键字，以基本工资为排序码，则所有8条记录可简记为：{(100,348),(101,374),(102,324)
4、,(103,305),(104,429),(105,348),(106,284),(107,324)}若按排序码的递增次序对记录进行重排，则得到的排序结果为：{(106,284),(103,305),(102,324),(107,324),(100,348),(105,348),(101,374),(104,429)}若以每个记录的出生日期为排序码（出生日期为8位字符串，其中前两位数字代表出生年份，中间两位数字代表月份，最后两位数字代表月内日号)，并按出生日期从前到后的次序(即递增次序)对记录进行重新排列，则得到的排序结果为：{(103,41/03/26
5、),(100,51/04/25),(102,53/06/28),(105,55/12/18),(107,59/12/20),(101,61/03/12),(104,64/05/03),(106,70/03/26)}一组记录按排序码的递增或递减次序排列得到的结果称之为有序表，相应地，把排序前的状态称为无序表递增次序又称为升序或正序，递减次序又称为降序、逆序或反序若有序表是按排序码升序排列的，则称为升序表或正序表，若按相反次序排列，则称为降序表或逆序表因为将无序表排列成正序表或逆序表的方法相同，只是排列次序正好相反而已，所以通常均按正序讨论之，并且若不特别指
6、明，所说的有序均指正序，所说的有序表均指正序表记录的排序码可以是记录的关键字，也可以是任何非关键字，所以排序码相同的记录可能只有一个，也可能有多个对于具有同一排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的如假定一组记录的排序码为(23,15,72,18,23,40)，其中排序码同为23的记录有两个，为了加以区别，后一个记录的排序码23带有下画线若一种排序方法使排序后的结果必为(15,18,23,23,40,72)，则称此方法是稳定的；若一种排序方法使排序后的结果可能为(15,18,23,23,4
7、0,72)，则称此方法是不稳定的按照排序过程中所使用的内、外存情况不同，可把排序分为内排序和外排序两大类若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序显然，外排序速度比内排序速度要慢得多对于一些较大的文件，由于内存容量的限制，不能一次装入内存进行内排序，只得采用外排序来完成内排序和外排序各有许多不同的排序方法，本书主要对内排序的各种方法进行讨论，对外排序仅介绍适应于磁盘文件的二路归并排序算法内排序方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择排序、交换排序、归并排序和分配排序本章将讨论
8、前四类中的一些常用的方法在内排序中，待排序的n个记录或n个记录的索引项（每个记录
