武汉理工大学华夏学院 -信息工程系第八章 排序一、排序的定义二、内部排序三、内部排序方法的分类基本概念武汉理工大学华夏学院 -信息工程系一 排序基本概念排序（ sort） 或分类所谓排序，就是要整理文件中的记录,使之按关键字递增 (或递减 )次序排列起来。其确切定义如下：
输入,n个记录 R1,R2,…,Rn,其相应的关键字分别为 K1,K2,…,Kn。
输出,Ril,Ri2,…,Rin,使得
Ki1≤Ki2≤…≤ Kin。 (或 Ki1≥Ki2≥…≥ Kin)。
武汉理工大学华夏学院 -信息工程系
1．被排序对象 --文件被排序的对象 --文件由一组记录组成。
记录则由若干个数据项 (或域 )组成。其中有一项可用来标识一个记录，称为关键字项。
该数据项的值称为关键字 (Key)。
注意,在不易产生混淆时，将关键字项简称为关键字。
2．排序运算的依据 --关键字用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
关键字的选取应根据问题的要求而定。
武汉理工大学华夏学院 -信息工程系
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用 "准考证号 "作为关键字。若要按照考生的总分数排名次，
则需用 "总分数 "作为关键字。
武汉理工大学华夏学院 -信息工程系排序的稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
武汉理工大学华夏学院 -信息工程系排序方法的分类
1．按是否涉及数据的内、外存交换分在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换,则称之为内部排序 (简称内排序 )；反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。
注意：
① 内排序适用于记录个数不很多的小文件
② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。
武汉理工大学华夏学院 -信息工程系
2．按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
排序算法分析
1．排序算法的基本操作大多数排序算法都有两个基本的操作：
(1) 比较两个关键字的大小；
(2) 改变指向记录的指针或移动记录本身。
注意：
第 (2)种基本操作的实现依赖于待排序记录的存储方式武汉理工大学华夏学院 -信息工程系
2．待排文件的常用存储方式
（ 1）以顺序表 (或直接用向量 )作为存储结构排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）
（ 2） 以链表作为存储结构排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表 (或链式 )排序；
（ 3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表 (如包括关键字和指向记录位置的指针组成的索引表 )
排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。
武汉理工大学华夏学院 -信息工程系
3．排序算法性能评价
（ 1） 评价排序算法好坏的标准评价排序算法好坏的标准主要有两条：
① 执行时间和所需的辅助空间
② 算法本身的复杂程度
（ 2） 排序算法的空间复杂度若排序算法所需的辅助空间并不依赖于问题的规模 n，
即辅助空间是 O(1),则称之为就地排序 (In-PlaceSou)。
非就地排序一般要求的辅助空间为 O(n)。
（ 3） 排序算法的时间开销大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
武汉理工大学华夏学院 -信息工程系二、插入排序插入排序 (Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
本节介绍两种插入排序方法：直接插入排序和希尔排序。
（一）直接插入排序基本思想
1、基本思想假设待排序的记录存放在数组 R[1..n]中。
初始时,R[1]自成 1个有序区,无序区为 R[2..n]。
从 i=2起直至 i=n为止，依次将 R[i]插入当前的有序区 R[1..i-1]中，生成含 n个记录的有序区。
武汉理工大学华夏学院 -信息工程系
2、第 i-1趟直接插入排序：
通常将一个记录 R[i](i=2,3,…,n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第 i-1趟直接插入排序。
排序过程的某一中间时刻,R被划分成两个子区间 R [1．,i-1 ]（ 已排好序的有序区）和
R[i．,n]（ 当前未排序的部分,可称无序区）。
直接插入排序的基本操作是将当前无序区的第 1个记录 R[i]插人到有序区 R[1．,i-1]中适当的位置上,使 R[1．,i]变为新的有序区。因为这种方法每次使有序区增加 1个记录,通常称增量法。
武汉理工大学华夏学院 -信息工程系插入排序与打扑克时整理手上的牌非常类似。摸来的第 1 张牌无须整理，此后每次从桌上的牌 (无序区 )中摸最上面的 1
张并插入左手的牌 (有序区 )中正确的位置上。为了找到这个正确的位置，须自左向右 (或自右向左 )将摸来的牌与左手中已有的牌逐一比较。
武汉理工大学华夏学院 -信息工程系
1．简单方法首先在当前有序区 R[1..i-1]中查找 R[i]的正确插入位置 k(1≤k≤i -1)； 然后将 R[k．,i-1]中的记录均后移一个位置，腾出 k位置上的空间插入 R[i]。
若 R[i]的关键字大于等于 R[1．,i-1] 中所有记录的关键字，则 R[i]就是插入原位置。
注意：
武汉理工大学华夏学院 -信息工程系
2．改进的方法一种查找比较操作和记录移动操作交替地进行的方法。
具体做法：
将待插入记录 R[i]的关键字从右向左依次与有序区中记录 R[j](j=i-1,i-2,…,1)的关键字进行比较：
① 若 R[j]的关键字大于 R[i]的关键字，则将 R[j]后移一个位置；
② 若 R[j]的关键字小于或等于 R[i]的关键字，则查找过程结束,j+1即为 R[i]的插入位置。
关键字比 R[i]的关键字大的记录均已后移，所以 j+1的位置已经腾空，只要将 R[i]直接插入此位置即可完成一趟直接插入排序。
武汉理工大学华夏学院 -信息工程系直接插入排序算法
1．算法描述
void lnsertSort(SeqList R)
{
//对顺序表 R中的记录 R[1..n]按递增序进行插入排序
int i,j；
for(i=2;i<=n； i++)//依次插入 R[2],…,R[n]
if(R[i].key<R[i-1].key)
{
//若 R[i].key大于等于有序区中所有的 keys,则 R[i]
//应在原有位置上
R[0]=R[i];j=i-1; //R[0]是哨兵，且是 R[i]的副本武汉理工大学华夏学院 -信息工程系
do{ //从右向左在有序区 R[1．,i-1]中查找 R[i]的插入位置
R[j+1]=R[j]； //将关键字大于 R[i].key的记录后移
j-- ；
}while(R[0].key<R[j].key)；
//当 R[i].key≥R[j].key时终止
R[j+1]=R[0]；
//R[i]插入到正确的位置上
}//endif
}//InsertSort
武汉理工大学华夏学院 -信息工程系
2．哨兵的作用算法中引进的附加记录 R[0]称监视哨或哨兵
(Sentinel)。
哨兵有两个作用：
① 进人查找 (插入位置 ) 循环之前，它保存了 R[i]的副本，使不致于因记录后移而丢失 R[i]
的内容；
② 它的主要作用是：在查找循环中,监视,
下标变量 j是否越界。一旦越界 (即 j=0),因为
R[0].key 和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测 j是否越界 (即省略了循环判定条件 "j>=1")。
武汉理工大学华夏学院 -信息工程系注意：
① 实际上，一切为简化边界条件而引入的附加结点 (元素 )均可称为哨兵。
【例】单链表中的头结点实际上是一个哨兵
② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。
武汉理工大学华夏学院 -信息工程系给定输入实例的排序过程设待排序的文件有 8个记录，其关键字分别为,49,38,65,97,76,13,27,49。
为了区别两个相同的关键字 49，后一个 49的下方加了一下划线以示区别。其排序过程见
3．直接插入排序的稳定性直接插入排序是稳定的排序方法。
武汉理工大学华夏学院 -信息工程系
（ 二 ） 希尔排序希尔排序 (Shell Sort)是插入排序的一种。因
D,L,Shell于 1959年提出而得名。
希尔排序基本思想基本思想：
先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1个组。所有距离为 dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量 d2<d1重复上述的分组和排序，直至所取的增量 dt=1 (dt<dt-l<…<d 2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
武汉理工大学华夏学院 -信息工程系给定实例的 shell排序的排序过程假设待排序文件有 10个记录，其关键字分别是：
49,38,65,97,76,13,27,49,55,04。
增量序列的取值依次为 5,3,1
武汉理工大学华夏学院 -信息工程系
1,不设监视哨的算法描述
void ShellPass(SeqList R,int d)
{//希尔排序中的一趟排序,d为当前增量
for(i=d+1;i<=n； i++)
//将 R[d+1．,n]分别插入各组当前的有序区
if(R[i].key<R[i-d].key){
R[0]=R[i];j=i-d；
//R[0]只是暂存单元，不是哨兵
do {//查找 R[i]的插入位置
R[j+d]； =R[j]； //后移记录
j=j-d； //查找前一记录
}while(j>0&&R[0].key<R[j].key)；
Shell排序的算法实现武汉理工大学华夏学院 -信息工程系
R[j+d]=R[0]； //插入 R[i]到正确的位置上
} //endif
} //ShellPass
void ShellSort(SeqList R)
{
int increment=n； //增量初值，不妨设 n>0
do {
increment=increment/3+1； //求下一增量
ShellPass(R,increment)；
//一趟增量为 increment的 Shell插入排序
}while(increment>1)
} //ShellSort
稳定性希尔排序是不稳定的。参见上述实例，该例中两个相同关键字 49在排序前后的相对次序发生了变化。
武汉理工大学华夏学院 -信息工程系简 单 选 择 排 序堆 排 序选择排序武汉理工大学华夏学院 -信息工程系
1.基本思想,它每次从待排序的区间中选择出具有最小排序码的元素，把该元素与该区间的第一个元素交换位置。
即第一次待排序区间包含所有元素 A[0]-A[n-1],经过选择和交换后,A[0]为具有最小排序码的元素；
第二次待排序区间为 A[1]-A[n-1],经过选择和交换后,A[1]为仅次于 A[0]的具有最小排序码的元素；
第三次待排序区间为 A[2]-A[n-1],经过选择和交换后,A[2]为仅次 A[0]和 A[1]的具有最小排序码的元素；依次类推,经过 N-1次选择和交换后，就成为了有序表，整个排序过程结束。
简单选择排序武汉理工大学华夏学院 -信息工程系
(0) [36 25 48 12 65 43 20 58]
⑴ 12 [25 48 36 65 43 20 58]
⑵ 12 20 [48 36 65 43 25 58]
⑶ 12 20 25 [36 65 43 48 58]
⑷ 12 20 25 36 [65 43 48 58]
⑸ 12 20 25 36 43 [65 48 58]
⑹ 12 20 25 36 43 48 [65 58]
⑺ 12 20 25 36 43 48 58 65
2.排序实现过程武汉理工大学华夏学院 -信息工程系
3,简单选择排序的实现算法
void SelectSort(ElemType A[],int n)
{ElemType x;
int i,j,k;
for(i=1;i<=n-1;i++)
{k=i-1;
for(j=i;j<=n-1;j++)
{if(A[j].stn<A[k].stn)
k=j;}
if(k!=i-1)
{x=A[i-1];A[i-1]=A[k];A[k]=x;}}}
武汉理工大学华夏学院 -信息工程系堆 排 序
1,堆的定义堆是一棵具有特定性质的顺序二叉树。该特定性质是：每个非终端结点的关键字值都大于或等于其左右孩子结点的值。
例如：序列 63,60,59,40,45,10,46,35,30就是一个堆。用下图表示之。
武汉理工大学华夏学院 -信息工程系序列 63,60,59,40,45,10,46,35,30 形成的堆是
63
60 59
40 45 10 45
35 30
武汉理工大学华夏学院 -信息工程系显然，堆中的第一个元素一定为序列中的最大数。注意：上述定义的堆又称为大根堆。若每个非终端结点的关键字值都小于或等于其左右孩子结点的值，形成的堆，即堆中的第一个元素一定为序列中的最小数称为小根堆。
武汉理工大学华夏学院 -信息工程系
2,堆基本思想：
利用大根堆的特性进行排序的过程。通过 构成初始堆和利用堆排序两个阶段。
筛运算,首先把 Ri的排序码 Si与两个孩子中排序码较大者 Sj进行比较，若 Si≥Sj,则以 Si为根的子树成为堆，筛运算完毕，否则 Ri与 Rj互换，
互换后可能破坏以 Rj为根的堆，接着再把 Rj与它的两个孩子中排序码较大者进行比较，依此类推，直到父结点的排序码大于等于孩子结点中较大的排序码或者是孩子结点为空时止。
武汉理工大学华夏学院 -信息工程系
3,堆排序的实现过程设有一个序列为 45,34,78,56,12,90对其实现堆排序。步骤为：首先建堆
45
34 78
56 12 90
90
56 78
34 12 45
建堆交换
45
56 78
34 12 90
调整堆
78
56 45
34 12 90
武汉理工大学华夏学院 -信息工程系
12
56 45
34 78 90
再交换 再建堆 56
34 45
12 78 90
再交换
12
34 45
56 78 90
再建堆
45
34 12
56 78 90
武汉理工大学华夏学院 -信息工程系再交换 12
34 45
56 78 90
再建堆 34
12 45
56 78 90
再交换
12
34 45
56 78 90
形成已排好序的序列
12 34 45
56 78 90
武汉理工大学华夏学院 -信息工程系
4,堆排序实现的算法
void HeapSort(ElemType A[],int n)
{ElemType x;
int i;
for(i=n/2-1;i>=0;i--)
Sift(A,n,i);
for(i=1;i<=n-1;i++)
{ x=A[0];A[0]=A[n-1];A[n-1]=x;
Sift(A,n-i,0);}}
武汉理工大学华夏学院 -信息工程系
int sift(JD r[],int t,int w)
{ int I,j ;
JD x;
I=t ; x=r[I] ; j=2*I ;
While ( j<=w)
{ if (( j<w)&&(r[j] >r[j+1]))
j++;
If(x>r[j])
{r[I]=r[j] ; I=j; j*=2;}
Else j=w+1 ;}
R[I]=x ; }
武汉理工大学华夏学院 -信息工程系性能分析共需进行 n+[n/2]-1次筛运算每次筛运算比较次数和移动记录次数不 会超过完全二叉树的高度，所以每次筛运算的时间复杂度为 O(log2n)
堆排序的最坏时间复杂度为 O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为 O(1)，
它是不稳定的排序方法。
武汉理工大学华夏学院 -信息工程系交 换 排 序一、气泡排序二、一趟快速排序三、快速排序四、快速排序的时间分析武汉理工大学华夏学院 -信息工程系气泡排序（冒泡排序）
一、冒泡排序的基本思想首先将 A [n-1]元素的排序码同 A [n-2] 元素的排序码进行比较，若 A [n-1].stn< A[n-2].stn,则交换两元素的位置，使轻者上浮，重者下沉,接着比较 A[n-2]
同 A [n-3]元素的排序码,同样使轻者上浮，重者下沉，
依此类推，直到比较 A [1] 同 A [0] 元素的排序码，并使轻者上浮重者下沉后，第一趟排序结束，此时 A [0]
为具有最小排序码的元素。然后在 A[n-1]~A [1]排序区间内进行第二趟排,使次最小排序码的元素被上浮到第
1单元中。至多重复进行 n-1 趟后，整个气泡排序结束。
武汉理工大学华夏学院 -信息工程系二、冒泡法排序 示例下一趟区间 0 1 2 3 4 5 6
初始关键字 [6,0] [ 91 67 35 62 29 72 46 ]
第一趟冒泡后 [6,1] 29 [91 67 35 62 46 72 ]
第三趟冒泡后 [6,3] 29 35 46 [ 91 67 62 72 ]
第二趟冒泡后 [6,2] 29 35 [ 91 67 46 62 72 ]
第四趟冒泡后 [6,4] 29 35 46 62 [ 91 67 72 ]
第五趟冒泡后 [6,5] 29 35 46 62 67 [ 91 72 ]
第六趟冒泡后 29 35 46 62 67 72 91有序序列形成。
武汉理工大学华夏学院 -信息工程系三,实现算法
void BubbleSort(ElemType A[],int n)
{ElemType x;
int i,j,flag;
for(i=1;i<=n-1;i++)
{flag=0;
for(j=n-1;j>=i;j--)
if(A[j].stn<A[j-1].stn){
x=A[j];A[j]=A[j-1];A[j-1]=x;
flag=1;}
if(flag==0) return;}}
注意：算法中引入了交换标志 fla g,以减少排序的趟数 。
武汉理工大学华夏学院 -信息工程系四、算法分析最好：只需一趟，比较 n-1次最坏：进行 n-1趟比较次数：最多为 n*(n－ 1)/2次最少为 0次移动次数：最多为 n*(n－ 1)/2次最少为 0次所以算法的时间复杂度为 O(n2)
武汉理工大学华夏学院 -信息工程系快速排序快速排序 又称划分排序一、基本思想
– 首先从待排序区间中选取一个元素作为比较的基准元素。
– 按这个基准元素分为前后两个子区间，第一个区间中值小于等于基准元素的值，第二个区间的值大于等于基准元素值（一次划分）。
– 然后对每个区间再进行快速排序。
武汉理工大学华夏学院 -信息工程系二、快速排序示例设设有一个序列 26,5,37,8,63,12,59,15,48,19
对其惊醒快速排序，第一遍排序过程为
26 5 37 8 63 12 59 15 48 19
26
i
26 26 5 37 8 63 12 59 15 48 19
j
ji
武汉理工大学华夏学院 -信息工程系
26
i
19 5 37 8 63 12 59 15 48 19
26 19 5 37 8 63 12 59 15 48 37
26 19 5 37 8 63 12 59 15 48 37
26 19 5 15 8 63 12 59 15 48 37
i
i
i
j
j
j
j
武汉理工大学华夏学院 -信息工程系
26 19 5 15 8 63 12 59 15 48 37
26 19 5 15 8 63 12 59 63 48 37
26 19 5 15 8 12 12 59 63 48 37
19 5 15 8 12 26 59 63 48 37
第一段：由小于 26的结点组成第二段：由大于 26的结点组成
ji
i
i
j
j
武汉理工大学华夏学院 -信息工程系三、快速排序算法
void QuickSort(ElemType A[],int s,int t)
{int i=s,j=t+1;
ElemType x=A[s];
do{
do i++; while(A[i].stn < x.stn);
do j--; wile(A[j].stn >x.stn);
if(i<j){
ElemType temp = A[i];
A[i] = A[j]; A[j] = temp;
}
}while (i<j);
A[s] = A[j]; A[j] = x ;
if(s<j-1) QuickSort(A,s,j-1);
if(j+1<t) QuickSort(A,j+1,t);
}
武汉理工大学华夏学院 -信息工程系四、快速排序的算法分析
对每一层所有区间划分时，需要比较记录的总次数为 n+1次
比较总次数 C为 (n+1)*(h-1)
h-1≤log2n
所以它的时间复杂度为 O(nlog2n)
最差的情况下是最好情况的 1.39倍，因此时间复杂度也为 O(nlog2n)
空间复杂度为 O(log2n)
武汉理工大学华夏学院 -信息工程系归 并 排 序归并排序的过程基于下列 基本思想 进行：
将两个或两个以上的有序子序列,归并,
为一个有序序列。
武汉理工大学华夏学院 -信息工程系归并排序一、归并排序的基本思想
归并就是将两个或多个有序表合并成一个有序表的过程。
将两个有序表合并成一个有序表称为二路归并二、两个有序表合并的算法武汉理工大学华夏学院 -信息工程系
void TwoMerge(ElemType A[],ElemType R[],
int s,int m,int t)
{ int i,j,k;
i=s; j=m+1; k=s;
while(i<=m && j<=t)
if(A[i].stn <= A[j].stn){
R[k]=A[i];i++; k++;
}
else{
R[k]=A[j];j++; k++;
}
while(i<=m){
R[k]=A[i];i++; k++;
}
while(j<=t){
R[k]=A[j];j++; k++;
} }
武汉理工大学华夏学院 -信息工程系三、两个有序表合并的实现过程设有 表 A（ 2,10,15,18,21,30)
表 B (5,20,35,40)
具体操作是：设 I=1;J=1;K=1：
将 A[I]与 B[J]比较若 A[I]<B[J]
则 A[I]送入 C[K] 且 I++,K++
否则 B[J]送入 C[K] 且 J++,K++
直到 A,B序列中有一个序列为空或两个序列为空时为止。当有一个序列为空后,就可以把另一个序列中剩余的元素加入到 C序列中排序即可结束。
合并后形成的序列为 C(2,5,10,15,18,20,21,30,35,40)
武汉理工大学华夏学院 -信息工程系四、归并排序
1,基本思想就是利用归并操作把一个无序表排列成一个有序表的过程。若利用二路归并操作则称为二路归并排序。
2,过程：
首先把待排序区间中的每一个元素看做是一个有序表，进行两两归并。
然后再进行两两归并，只到得到一个长度为 n
的有序表为止。
武汉理工大学华夏学院 -信息工程系
(0) [45] [53] [18] [36] [72] [30] [48] [93] [15] [36]
(1) [45 53] [18 36] [30 72] [48 93] [15 36]
(2) [18 36 45 53] [30 48 72 93] [15 36]
(3) [18 30 36 45 48 53 72 93] [15 36]
(4) [15 18 30 36 36 45 48 53 72 93]
3.归并排序实现过程示例设 待排序列为 45,53,18,36,72,30,48,93,15,36
武汉理工大学华夏学院 -信息工程系算 法二路归并排序的算法
void MergeSort(ElemType A[],int n)
{
ElemType * R = new ElemType [n];
int len =1;
while(len < n){
MergePass(A,R,n,len);
len*=2;
MergePass(R,A,n,len);
len*=2;
}
delete [] R;
}
武汉理工大学华夏学院 -信息工程系五、算法分析归并的趟数为,[log2n](当为 [log2n]奇数时则为 [log2n]+1)
第一趟归并的移动次数均等于数组中记录的个数 n,即每一趟归并的时间复杂度为 O(n)
二路归并排序的时间复杂度为 O(nlog2n)
二路归并排序时需要一个同待排序数组一样大小的数组，所以其空间复杂度为 O(n)
输入,n个记录 R1,R2,…,Rn,其相应的关键字分别为 K1,K2,…,Kn。
输出,Ril,Ri2,…,Rin,使得
Ki1≤Ki2≤…≤ Kin。 (或 Ki1≥Ki2≥…≥ Kin)。
武汉理工大学华夏学院 -信息工程系
1．被排序对象 --文件被排序的对象 --文件由一组记录组成。
记录则由若干个数据项 (或域 )组成。其中有一项可用来标识一个记录，称为关键字项。
该数据项的值称为关键字 (Key)。
注意,在不易产生混淆时，将关键字项简称为关键字。
2．排序运算的依据 --关键字用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
关键字的选取应根据问题的要求而定。
武汉理工大学华夏学院 -信息工程系
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用 "准考证号 "作为关键字。若要按照考生的总分数排名次，
则需用 "总分数 "作为关键字。
武汉理工大学华夏学院 -信息工程系排序的稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
武汉理工大学华夏学院 -信息工程系排序方法的分类
1．按是否涉及数据的内、外存交换分在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换,则称之为内部排序 (简称内排序 )；反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。
注意：
① 内排序适用于记录个数不很多的小文件
② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。
武汉理工大学华夏学院 -信息工程系
2．按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
排序算法分析
1．排序算法的基本操作大多数排序算法都有两个基本的操作：
(1) 比较两个关键字的大小；
(2) 改变指向记录的指针或移动记录本身。
注意：
第 (2)种基本操作的实现依赖于待排序记录的存储方式武汉理工大学华夏学院 -信息工程系
2．待排文件的常用存储方式
（ 1）以顺序表 (或直接用向量 )作为存储结构排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）
（ 2） 以链表作为存储结构排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表 (或链式 )排序；
（ 3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表 (如包括关键字和指向记录位置的指针组成的索引表 )
排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。
武汉理工大学华夏学院 -信息工程系
3．排序算法性能评价
（ 1） 评价排序算法好坏的标准评价排序算法好坏的标准主要有两条：
① 执行时间和所需的辅助空间
② 算法本身的复杂程度
（ 2） 排序算法的空间复杂度若排序算法所需的辅助空间并不依赖于问题的规模 n，
即辅助空间是 O(1),则称之为就地排序 (In-PlaceSou)。
非就地排序一般要求的辅助空间为 O(n)。
（ 3） 排序算法的时间开销大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
武汉理工大学华夏学院 -信息工程系二、插入排序插入排序 (Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
本节介绍两种插入排序方法：直接插入排序和希尔排序。
（一）直接插入排序基本思想
1、基本思想假设待排序的记录存放在数组 R[1..n]中。
初始时,R[1]自成 1个有序区,无序区为 R[2..n]。
从 i=2起直至 i=n为止，依次将 R[i]插入当前的有序区 R[1..i-1]中，生成含 n个记录的有序区。
武汉理工大学华夏学院 -信息工程系
2、第 i-1趟直接插入排序：
通常将一个记录 R[i](i=2,3,…,n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第 i-1趟直接插入排序。
排序过程的某一中间时刻,R被划分成两个子区间 R [1．,i-1 ]（ 已排好序的有序区）和
R[i．,n]（ 当前未排序的部分,可称无序区）。
直接插入排序的基本操作是将当前无序区的第 1个记录 R[i]插人到有序区 R[1．,i-1]中适当的位置上,使 R[1．,i]变为新的有序区。因为这种方法每次使有序区增加 1个记录,通常称增量法。
武汉理工大学华夏学院 -信息工程系插入排序与打扑克时整理手上的牌非常类似。摸来的第 1 张牌无须整理，此后每次从桌上的牌 (无序区 )中摸最上面的 1
张并插入左手的牌 (有序区 )中正确的位置上。为了找到这个正确的位置，须自左向右 (或自右向左 )将摸来的牌与左手中已有的牌逐一比较。
武汉理工大学华夏学院 -信息工程系
1．简单方法首先在当前有序区 R[1..i-1]中查找 R[i]的正确插入位置 k(1≤k≤i -1)； 然后将 R[k．,i-1]中的记录均后移一个位置，腾出 k位置上的空间插入 R[i]。
若 R[i]的关键字大于等于 R[1．,i-1] 中所有记录的关键字，则 R[i]就是插入原位置。
注意：
武汉理工大学华夏学院 -信息工程系
2．改进的方法一种查找比较操作和记录移动操作交替地进行的方法。
具体做法：
将待插入记录 R[i]的关键字从右向左依次与有序区中记录 R[j](j=i-1,i-2,…,1)的关键字进行比较：
① 若 R[j]的关键字大于 R[i]的关键字，则将 R[j]后移一个位置；
② 若 R[j]的关键字小于或等于 R[i]的关键字，则查找过程结束,j+1即为 R[i]的插入位置。
关键字比 R[i]的关键字大的记录均已后移，所以 j+1的位置已经腾空，只要将 R[i]直接插入此位置即可完成一趟直接插入排序。
武汉理工大学华夏学院 -信息工程系直接插入排序算法
1．算法描述
void lnsertSort(SeqList R)
{
//对顺序表 R中的记录 R[1..n]按递增序进行插入排序
int i,j；
for(i=2;i<=n； i++)//依次插入 R[2],…,R[n]
if(R[i].key<R[i-1].key)
{
//若 R[i].key大于等于有序区中所有的 keys,则 R[i]
//应在原有位置上
R[0]=R[i];j=i-1; //R[0]是哨兵，且是 R[i]的副本武汉理工大学华夏学院 -信息工程系
do{ //从右向左在有序区 R[1．,i-1]中查找 R[i]的插入位置
R[j+1]=R[j]； //将关键字大于 R[i].key的记录后移
j-- ；
}while(R[0].key<R[j].key)；
//当 R[i].key≥R[j].key时终止
R[j+1]=R[0]；
//R[i]插入到正确的位置上
}//endif
}//InsertSort
武汉理工大学华夏学院 -信息工程系
2．哨兵的作用算法中引进的附加记录 R[0]称监视哨或哨兵
(Sentinel)。
哨兵有两个作用：
① 进人查找 (插入位置 ) 循环之前，它保存了 R[i]的副本，使不致于因记录后移而丢失 R[i]
的内容；
② 它的主要作用是：在查找循环中,监视,
下标变量 j是否越界。一旦越界 (即 j=0),因为
R[0].key 和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测 j是否越界 (即省略了循环判定条件 "j>=1")。
武汉理工大学华夏学院 -信息工程系注意：
① 实际上，一切为简化边界条件而引入的附加结点 (元素 )均可称为哨兵。
【例】单链表中的头结点实际上是一个哨兵
② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。
武汉理工大学华夏学院 -信息工程系给定输入实例的排序过程设待排序的文件有 8个记录，其关键字分别为,49,38,65,97,76,13,27,49。
为了区别两个相同的关键字 49，后一个 49的下方加了一下划线以示区别。其排序过程见
3．直接插入排序的稳定性直接插入排序是稳定的排序方法。
武汉理工大学华夏学院 -信息工程系
（ 二 ） 希尔排序希尔排序 (Shell Sort)是插入排序的一种。因
D,L,Shell于 1959年提出而得名。
希尔排序基本思想基本思想：
先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1个组。所有距离为 dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量 d2<d1重复上述的分组和排序，直至所取的增量 dt=1 (dt<dt-l<…<d 2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
武汉理工大学华夏学院 -信息工程系给定实例的 shell排序的排序过程假设待排序文件有 10个记录，其关键字分别是：
49,38,65,97,76,13,27,49,55,04。
增量序列的取值依次为 5,3,1
武汉理工大学华夏学院 -信息工程系
1,不设监视哨的算法描述
void ShellPass(SeqList R,int d)
{//希尔排序中的一趟排序,d为当前增量
for(i=d+1;i<=n； i++)
//将 R[d+1．,n]分别插入各组当前的有序区
if(R[i].key<R[i-d].key){
R[0]=R[i];j=i-d；
//R[0]只是暂存单元，不是哨兵
do {//查找 R[i]的插入位置
R[j+d]； =R[j]； //后移记录
j=j-d； //查找前一记录
}while(j>0&&R[0].key<R[j].key)；
Shell排序的算法实现武汉理工大学华夏学院 -信息工程系
R[j+d]=R[0]； //插入 R[i]到正确的位置上
} //endif
} //ShellPass
void ShellSort(SeqList R)
{
int increment=n； //增量初值，不妨设 n>0
do {
increment=increment/3+1； //求下一增量
ShellPass(R,increment)；
//一趟增量为 increment的 Shell插入排序
}while(increment>1)
} //ShellSort
稳定性希尔排序是不稳定的。参见上述实例，该例中两个相同关键字 49在排序前后的相对次序发生了变化。
武汉理工大学华夏学院 -信息工程系简 单 选 择 排 序堆 排 序选择排序武汉理工大学华夏学院 -信息工程系
1.基本思想,它每次从待排序的区间中选择出具有最小排序码的元素，把该元素与该区间的第一个元素交换位置。
即第一次待排序区间包含所有元素 A[0]-A[n-1],经过选择和交换后,A[0]为具有最小排序码的元素；
第二次待排序区间为 A[1]-A[n-1],经过选择和交换后,A[1]为仅次于 A[0]的具有最小排序码的元素；
第三次待排序区间为 A[2]-A[n-1],经过选择和交换后,A[2]为仅次 A[0]和 A[1]的具有最小排序码的元素；依次类推,经过 N-1次选择和交换后，就成为了有序表，整个排序过程结束。
简单选择排序武汉理工大学华夏学院 -信息工程系
(0) [36 25 48 12 65 43 20 58]
⑴ 12 [25 48 36 65 43 20 58]
⑵ 12 20 [48 36 65 43 25 58]
⑶ 12 20 25 [36 65 43 48 58]
⑷ 12 20 25 36 [65 43 48 58]
⑸ 12 20 25 36 43 [65 48 58]
⑹ 12 20 25 36 43 48 [65 58]
⑺ 12 20 25 36 43 48 58 65
2.排序实现过程武汉理工大学华夏学院 -信息工程系
3,简单选择排序的实现算法
void SelectSort(ElemType A[],int n)
{ElemType x;
int i,j,k;
for(i=1;i<=n-1;i++)
{k=i-1;
for(j=i;j<=n-1;j++)
{if(A[j].stn<A[k].stn)
k=j;}
if(k!=i-1)
{x=A[i-1];A[i-1]=A[k];A[k]=x;}}}
武汉理工大学华夏学院 -信息工程系堆 排 序
1,堆的定义堆是一棵具有特定性质的顺序二叉树。该特定性质是：每个非终端结点的关键字值都大于或等于其左右孩子结点的值。
例如：序列 63,60,59,40,45,10,46,35,30就是一个堆。用下图表示之。
武汉理工大学华夏学院 -信息工程系序列 63,60,59,40,45,10,46,35,30 形成的堆是
63
60 59
40 45 10 45
35 30
武汉理工大学华夏学院 -信息工程系显然，堆中的第一个元素一定为序列中的最大数。注意：上述定义的堆又称为大根堆。若每个非终端结点的关键字值都小于或等于其左右孩子结点的值，形成的堆，即堆中的第一个元素一定为序列中的最小数称为小根堆。
武汉理工大学华夏学院 -信息工程系
2,堆基本思想：
利用大根堆的特性进行排序的过程。通过 构成初始堆和利用堆排序两个阶段。
筛运算,首先把 Ri的排序码 Si与两个孩子中排序码较大者 Sj进行比较，若 Si≥Sj,则以 Si为根的子树成为堆，筛运算完毕，否则 Ri与 Rj互换，
互换后可能破坏以 Rj为根的堆，接着再把 Rj与它的两个孩子中排序码较大者进行比较，依此类推，直到父结点的排序码大于等于孩子结点中较大的排序码或者是孩子结点为空时止。
武汉理工大学华夏学院 -信息工程系
3,堆排序的实现过程设有一个序列为 45,34,78,56,12,90对其实现堆排序。步骤为：首先建堆
45
34 78
56 12 90
90
56 78
34 12 45
建堆交换
45
56 78
34 12 90
调整堆
78
56 45
34 12 90
武汉理工大学华夏学院 -信息工程系
12
56 45
34 78 90
再交换 再建堆 56
34 45
12 78 90
再交换
12
34 45
56 78 90
再建堆
45
34 12
56 78 90
武汉理工大学华夏学院 -信息工程系再交换 12
34 45
56 78 90
再建堆 34
12 45
56 78 90
再交换
12
34 45
56 78 90
形成已排好序的序列
12 34 45
56 78 90
武汉理工大学华夏学院 -信息工程系
4,堆排序实现的算法
void HeapSort(ElemType A[],int n)
{ElemType x;
int i;
for(i=n/2-1;i>=0;i--)
Sift(A,n,i);
for(i=1;i<=n-1;i++)
{ x=A[0];A[0]=A[n-1];A[n-1]=x;
Sift(A,n-i,0);}}
武汉理工大学华夏学院 -信息工程系
int sift(JD r[],int t,int w)
{ int I,j ;
JD x;
I=t ; x=r[I] ; j=2*I ;
While ( j<=w)
{ if (( j<w)&&(r[j] >r[j+1]))
j++;
If(x>r[j])
{r[I]=r[j] ; I=j; j*=2;}
Else j=w+1 ;}
R[I]=x ; }
武汉理工大学华夏学院 -信息工程系性能分析共需进行 n+[n/2]-1次筛运算每次筛运算比较次数和移动记录次数不 会超过完全二叉树的高度，所以每次筛运算的时间复杂度为 O(log2n)
堆排序的最坏时间复杂度为 O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为 O(1)，
它是不稳定的排序方法。
武汉理工大学华夏学院 -信息工程系交 换 排 序一、气泡排序二、一趟快速排序三、快速排序四、快速排序的时间分析武汉理工大学华夏学院 -信息工程系气泡排序（冒泡排序）
一、冒泡排序的基本思想首先将 A [n-1]元素的排序码同 A [n-2] 元素的排序码进行比较，若 A [n-1].stn< A[n-2].stn,则交换两元素的位置，使轻者上浮，重者下沉,接着比较 A[n-2]
同 A [n-3]元素的排序码,同样使轻者上浮，重者下沉，
依此类推，直到比较 A [1] 同 A [0] 元素的排序码，并使轻者上浮重者下沉后，第一趟排序结束，此时 A [0]
为具有最小排序码的元素。然后在 A[n-1]~A [1]排序区间内进行第二趟排,使次最小排序码的元素被上浮到第
1单元中。至多重复进行 n-1 趟后，整个气泡排序结束。
武汉理工大学华夏学院 -信息工程系二、冒泡法排序 示例下一趟区间 0 1 2 3 4 5 6
初始关键字 [6,0] [ 91 67 35 62 29 72 46 ]
第一趟冒泡后 [6,1] 29 [91 67 35 62 46 72 ]
第三趟冒泡后 [6,3] 29 35 46 [ 91 67 62 72 ]
第二趟冒泡后 [6,2] 29 35 [ 91 67 46 62 72 ]
第四趟冒泡后 [6,4] 29 35 46 62 [ 91 67 72 ]
第五趟冒泡后 [6,5] 29 35 46 62 67 [ 91 72 ]
第六趟冒泡后 29 35 46 62 67 72 91有序序列形成。
武汉理工大学华夏学院 -信息工程系三,实现算法
void BubbleSort(ElemType A[],int n)
{ElemType x;
int i,j,flag;
for(i=1;i<=n-1;i++)
{flag=0;
for(j=n-1;j>=i;j--)
if(A[j].stn<A[j-1].stn){
x=A[j];A[j]=A[j-1];A[j-1]=x;
flag=1;}
if(flag==0) return;}}
注意：算法中引入了交换标志 fla g,以减少排序的趟数 。
武汉理工大学华夏学院 -信息工程系四、算法分析最好：只需一趟，比较 n-1次最坏：进行 n-1趟比较次数：最多为 n*(n－ 1)/2次最少为 0次移动次数：最多为 n*(n－ 1)/2次最少为 0次所以算法的时间复杂度为 O(n2)
武汉理工大学华夏学院 -信息工程系快速排序快速排序 又称划分排序一、基本思想
– 首先从待排序区间中选取一个元素作为比较的基准元素。
– 按这个基准元素分为前后两个子区间，第一个区间中值小于等于基准元素的值，第二个区间的值大于等于基准元素值（一次划分）。
– 然后对每个区间再进行快速排序。
武汉理工大学华夏学院 -信息工程系二、快速排序示例设设有一个序列 26,5,37,8,63,12,59,15,48,19
对其惊醒快速排序，第一遍排序过程为
26 5 37 8 63 12 59 15 48 19
26
i
26 26 5 37 8 63 12 59 15 48 19
j
ji
武汉理工大学华夏学院 -信息工程系
26
i
19 5 37 8 63 12 59 15 48 19
26 19 5 37 8 63 12 59 15 48 37
26 19 5 37 8 63 12 59 15 48 37
26 19 5 15 8 63 12 59 15 48 37
i
i
i
j
j
j
j
武汉理工大学华夏学院 -信息工程系
26 19 5 15 8 63 12 59 15 48 37
26 19 5 15 8 63 12 59 63 48 37
26 19 5 15 8 12 12 59 63 48 37
19 5 15 8 12 26 59 63 48 37
第一段：由小于 26的结点组成第二段：由大于 26的结点组成
ji
i
i
j
j
武汉理工大学华夏学院 -信息工程系三、快速排序算法
void QuickSort(ElemType A[],int s,int t)
{int i=s,j=t+1;
ElemType x=A[s];
do{
do i++; while(A[i].stn < x.stn);
do j--; wile(A[j].stn >x.stn);
if(i<j){
ElemType temp = A[i];
A[i] = A[j]; A[j] = temp;
}
}while (i<j);
A[s] = A[j]; A[j] = x ;
if(s<j-1) QuickSort(A,s,j-1);
if(j+1<t) QuickSort(A,j+1,t);
}
武汉理工大学华夏学院 -信息工程系四、快速排序的算法分析
对每一层所有区间划分时，需要比较记录的总次数为 n+1次
比较总次数 C为 (n+1)*(h-1)
h-1≤log2n
所以它的时间复杂度为 O(nlog2n)
最差的情况下是最好情况的 1.39倍，因此时间复杂度也为 O(nlog2n)
空间复杂度为 O(log2n)
武汉理工大学华夏学院 -信息工程系归 并 排 序归并排序的过程基于下列 基本思想 进行：
将两个或两个以上的有序子序列,归并,
为一个有序序列。
武汉理工大学华夏学院 -信息工程系归并排序一、归并排序的基本思想
归并就是将两个或多个有序表合并成一个有序表的过程。
将两个有序表合并成一个有序表称为二路归并二、两个有序表合并的算法武汉理工大学华夏学院 -信息工程系
void TwoMerge(ElemType A[],ElemType R[],
int s,int m,int t)
{ int i,j,k;
i=s; j=m+1; k=s;
while(i<=m && j<=t)
if(A[i].stn <= A[j].stn){
R[k]=A[i];i++; k++;
}
else{
R[k]=A[j];j++; k++;
}
while(i<=m){
R[k]=A[i];i++; k++;
}
while(j<=t){
R[k]=A[j];j++; k++;
} }
武汉理工大学华夏学院 -信息工程系三、两个有序表合并的实现过程设有 表 A（ 2,10,15,18,21,30)
表 B (5,20,35,40)
具体操作是：设 I=1;J=1;K=1：
将 A[I]与 B[J]比较若 A[I]<B[J]
则 A[I]送入 C[K] 且 I++,K++
否则 B[J]送入 C[K] 且 J++,K++
直到 A,B序列中有一个序列为空或两个序列为空时为止。当有一个序列为空后,就可以把另一个序列中剩余的元素加入到 C序列中排序即可结束。
合并后形成的序列为 C(2,5,10,15,18,20,21,30,35,40)
武汉理工大学华夏学院 -信息工程系四、归并排序
1,基本思想就是利用归并操作把一个无序表排列成一个有序表的过程。若利用二路归并操作则称为二路归并排序。
2,过程：
首先把待排序区间中的每一个元素看做是一个有序表，进行两两归并。
然后再进行两两归并，只到得到一个长度为 n
的有序表为止。
武汉理工大学华夏学院 -信息工程系
(0) [45] [53] [18] [36] [72] [30] [48] [93] [15] [36]
(1) [45 53] [18 36] [30 72] [48 93] [15 36]
(2) [18 36 45 53] [30 48 72 93] [15 36]
(3) [18 30 36 45 48 53 72 93] [15 36]
(4) [15 18 30 36 36 45 48 53 72 93]
3.归并排序实现过程示例设 待排序列为 45,53,18,36,72,30,48,93,15,36
武汉理工大学华夏学院 -信息工程系算 法二路归并排序的算法
void MergeSort(ElemType A[],int n)
{
ElemType * R = new ElemType [n];
int len =1;
while(len < n){
MergePass(A,R,n,len);
len*=2;
MergePass(R,A,n,len);
len*=2;
}
delete [] R;
}
武汉理工大学华夏学院 -信息工程系五、算法分析归并的趟数为,[log2n](当为 [log2n]奇数时则为 [log2n]+1)
第一趟归并的移动次数均等于数组中记录的个数 n,即每一趟归并的时间复杂度为 O(n)
二路归并排序的时间复杂度为 O(nlog2n)
二路归并排序时需要一个同待排序数组一样大小的数组，所以其空间复杂度为 O(n)
