? 概述
插入排序 （直接插入、折半插入、表插入排序、
希尔排序）
交换排序 （起泡排序、快速排序）
选择排序 （简单选择排序、树形选择排序、堆排序）
归并排序
基数排序
小结第 9章 内部排序概述
排序,将一组杂乱无章的数据排列成一个按关键字有序的序列 。
数据表 (datalist),它是待排序数据对象的有限集合 。
关键字 (key),通常数据对象有多个 属性域,
即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据 。 该域即为关键字 。
每个数据表用哪个属性域作为关键字,要视具体的应用需要而定 。 即使是同一个表,在解决不同问题的场合也可能取不同的域做关键字 。
主关键字,如果在数据表中各个对象的关键字互不相同，这种关键字即主关键字。按照主关键字进行排序，排序的结果是唯一的。
次关键字,数据表中有些对象的关键字可能相同，这种关键字称为次关键字。按照次关键字进行排序，排序的结果可能不唯一。
排序算法的稳定性,如果在对象序列中有两个对象 r[i]和 r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对象 r[i]排在 r[j]前面。如果在排序之后，对象 r[i]仍在对象 r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。
内排序与外排序,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序的时间开销,排序的时间开销是衡量算法好坏的最重要的标志。 排序的时间开销可用算法执行中的 数据比较次数 与 数据移动次数 来衡量 。各节给出算法运行时间代价的大略估算一般都 按平均情况 进行估算。对于那些 受对象关键字序列初始排列及对象个数影响较大的,需要 按最好情况 和 最坏情况 进行估算 。
静态排序,排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。
动态排序,给每个对象增加一个链接指针，
在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。
算法执行时所需的附加存储,评价算法好坏的另一标准。
衡量排序方法的标准
排序时所需要的平均比较次数
排序时所需要的平均移动
排序时所需要的平均辅助存储空间待排记录的数据类型定义为：
#define MAXSIZE 20
Typedef int KeyType
Typedef struct
{KeyType key; //关键字项
InfoType otherinfo; //其它数据项
}RedType;
Typedef struct
{RedType r[MAXSIZE+1] //r[0]闲置或用作哨兵
int length;
}Sqlist;
插入排序 (Insert Sorting)
直接插入排序的基本思想是：当插入第 i (i? 1) 个对象时，前面的 V[0],V[1],…,v[i-1]已经排好序。这时，用
v[i]的关键字与 v[i-1],v[i-2],… 的关键字顺序进行比较，
找到插入位置即将 v[i]插入，原来位置上之后的所有对象依次向后顺移。
插入排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
直接插入排序 (Insert Sort)
各趟排序结果
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 49 25* 16 08 25i = 1
0 1 2 3 4 5 temp
21 25 49 25* 16 08 49i = 2
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 16 08i = 4
0 1 2 3 4 5 temp
21 25 4925*16 08i = 5
i = 3 25*
16
08
16
4916
16
21 25 4925*1608
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 08
i = 4 时的排序过程
0 1 2 3 4 5 temp
21 25 4925*
完成
16
08 16
i = 4
j = 3
i = 4
j = 2
25
25*16
16
21 25 4925* 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 4925* 08
0 1 2 3 4 5 temp
21 25 4925*
16
08 16
16
25
21
i = 4
j = 1
i = 4
j = 0
i = 4
j = -1 16
直接插入排序的算法
void InsertSort(SqList &L)
{ for (int i=2;i<=L.length;++i)
if (LT(L.r[i].key,L.r[i-1].key))
{ L.r[0]=L.r[i]; // L.r[0]为监视哨
for (int j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
算法分析
若设待排序的对象个数为 L.length= n，则该算法的主程序执行 n-1趟。
关键字比较次数和对象移动次数与对象关键字的初始排列有关。
最好情况下,排序前对象已经按关键字大小从小到大有序,每趟只需与前面的有序对象序列的最后一个对象的关键字比较 1 次,移动 2 次对象,总的关键字比较次数为 n-1,对象移动次数为 2(n-1)。
直接插入排序是一种 稳定 的排序方法。
直接插入排序算法的时间复杂度为 O(n2)
折半插入排序 (Binary Insertsort)
折半插入排序基本思想是：设在顺序表中有一个对象序列 V[0],V[1],…,v[n-1]。其中,v[0],
V[1],…,v[i-1] 是已经排好序的对象。在插入
v[i] 时，利用折半搜索法寻找 v[i] 的插入位置。
折半插入排序的算法
void BInsertSort(SqList &L)
{ int low,high,mid;
for (int i=2;i<=L.length;++i)
{ L.r[0]=L.r[i];
low = 1; high=i-1;
while (low <= high)
{ mid = (low+high)/2;
if (LT(L.r[0].key,L.r[mid].key)) high=mid-1;
else low=mid+1; }
for (int j=i-1; j>=high+1;--j) L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
说明,low 或者 high+1为插入点 稳定排序算法分析
对分查找比顺序查找快，所以对分插入排序就平均性能来说比直接插入排序要快。
它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。
当 n 较大时，总关键字比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。
对分插入排序是一个 稳定 的排序方法。
希尔排序 (Shell Sort)
希尔排序方法又称为“缩小增量”排序。
该方法的基本思想是：先将整个待排对象序列按照一定间隔分割成为若干子序列，分别进行直接插入排序，然后缩小间隔，对整个对象序列重复以上的划分子序列和分别排序工作，直到最后间隔为 1，此时整个对象序列已,基本有序”，进行最后一次直接插入排序。
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*
i = 1
08
49
gap = 3
25 16
4925 16
08
49 25*
0821
2521 25* 16
21 25 4925*16 08
0 1 2 3 4 5
21
i = 2
08
49
gap = 2
25
16
4916 25*
0821 25
4925*
08 16 21 25* 25
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
gap = 1
2516 4925*
开始时 gap（间隔值） 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，
gap 值逐渐变小，子序列中对象个数逐渐变多，
由于前面工作的基础，大多数对象已基本有序，
所以排序速度仍然很快。
希尔排序的算法
void ShellSort(SqList &L,int dlta[],int t){
for (int k=0;k<t;++k){
ShellInsert(L,dlta[k]);
}
}
说明,dlta[3]={5,3,1}
//一趟希尔排序,按间隔 dk划分子序列
void ShellInsert(SqList &L,int gap)
{
for (int i=gap+1;i<=L.length;++i)
{if (LT(L.r[i].key,L.r[i-gap].key))
{ L.r[0]=L.r[i];
for (int j=i-gap;j>0 &&
LT(L.r[0].key,L.r[j].key); j-=gap)
L.r[j+gap]=L.r[j];
L.r[j+gap]=L.r[0];
}
}
}
算法分析
对特定的待排序对象序列,可以准确地估算关键字的比较次数和对象移动次数 。
但想要弄清关键字比较次数和对象移动次数与增量选择之间的依赖关系,并给出完整的数学分析,还没有人能够做到 。
gap的取法有多种 。 最初 shell 提出取 gap =
n/2?,gap =?gap/2?,直到 gap = 1。 后来
Knuth 提出取 gap =?gap/3? +1。 还有人提出都取奇数为好,也有人提出各 gap互质为好 。
交换排序 ( Exchange Sort )
起泡排序的基本方法是：设待排序对象序列中的对象个数为 n。最多作 n-1 趟 排序。在第 i
趟中顺次两两 比较 r[j-1].Key和 r[j].Key,j = i,
i+1,?,n-i-1。 如果发生逆序，则交换 r[j-1]和
r[j]。
交换排序的基本思想是两两比较待排序对象的关键字，如果发生逆序 (即排列顺序与排序后的次序正好相反 )，则交换之，直到所有对象都排好序为止。
起泡排序 (Bubble Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25 16 49
chang=1
08
25*
chang=1
i = 2
i = 3 0816
chang=1
25*2521
4921 25 16 08
25*
0 1 2 3 4 5
i = 4 4916
chang=108
2521
25*
0 1 2 3 4 5
i = 5 4916
chang=008
2521
void BubbleSort(SqList &L)
{ int i,j,tag;
j = L.length-1;
do{ tag=1;
for(i=1; i<=j; i++)
if( L.r[i+1].key< L.r[i].key )
{ L.r[0]= L.r[i+1]; L.r[i+1]= L.r[i];
L.r[i]= L.r[0]; tag=0;
}
if( !tag ) j--;
} while( !tag &&j );
return;
}
起泡排序的算法 —— 1
void BubbleSort(SqList &L)
{for (int i=L.length,change=TRUE;i>1 && change; --i)
{ change = FALSE;
for (int j=1; j<i; ++j)
if (LT(L.r[j+1].key,L.r[j].key))
{ ElemType temp=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=temp;
change = TRUE;
}
}
}
起泡排序的算法 —— 2
算法分析
在对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟起泡，做 n-1 次关键字比较，不移动对象。这是最好的情形。
最坏的情形是算法执行了 n-1趟起泡，第 i 趟
(1? i? n) 做了 n- i 次关键字比较，执行了 n-i
次对象交换。这样在最坏情形下总的关键字比较次数 KCN和对象移动次数 RMN为：
起泡排序需要一个附加对象以实现对象值的对换。
起泡排序是一个稳定的排序方法。
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninR M N
nninKCN
)()(
)()(
快速排序 (Quick Sort)
快速排序方法的基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象 ) 作为枢轴 (pivot)，按照该对象的关键字大小，将整个对象序列划分为左右两个子序列：
左侧子序列中所有对象的关键字都小于或等于 枢轴 对象的关键字
右侧子序列中所有对象的关键字都大于 枢轴 对象的关键字
枢轴对象则排在这两个子序列中间 (这也是该对象最终应安放的位置 )。
然后分别对这两个子序列重复施行上述方法，
直到所有的对象都排在相应位置上为止。
算法描述
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
2516
2516
08
49
pivot
08
25*4921i = 2
i = 3
08 16 25*2521
pivotpivot
pivot
快速排序的算法
void QSort(SqList &L,int low,int high){
if (low < high)
{
int pivotloc = Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L){
QSort(L,1,L.length);
}
int Partition(SqList &L,int low,int high)
{ L.r[0] = L.r[low];
int pivotkey = L.r[low].key;
while (low < high)
{ while (low<high && L.r[high].key >= pivotkey) --high;
L.r[low] = L.r[high];
while (low<high && L.r[low].key <= pivotkey) ++low;
L.r[high] = L.r[low];
}
L.r[low]=L.r[0];
return low;
}
算法 quicksort是一个递归的算法，其递归树如图所示。
算法 partition利用序列第一个对象作为枢轴，
将整个序列划分为左右两个子序列。算法中执行了一个循环，只要是关键字小于枢轴对象关键字的对象都移到序列左侧，最后枢轴对象安放到位，函数返回其位置。
21
25*
25
49
08
16
算法分析
从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。
如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。
可以证明，函数 quicksort的平均计算时间也是
o(nlog2n)。实验结果表明,就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个 。
快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数 。
在最坏的情况,即待排序对象序列已经按其关键字从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列 。 这样,必须经过 n-1 趟才能把所有对象定位,而且第 i 趟需要经过
n-i 次关键字比较才能找到第 i 个对象的安放位置,总的关键字比较次数将达到
212
1 21
1
nnninn
i
)()(
选择排序的基本思想是：每一趟 (例如第 i 趟，
i = 1,…,n-1) 在后面的 n-i+1 个待排序对象中选出关键字最小的对象,作为有序对象序列的第 i 个对象。待到第 n-1 趟作完，待排序对象只剩下 1个
，就不用再选了。
选择排序 (Selection Sort)
基本步骤为,i从 1开始，直到 n-1，进行 n-1趟排序，第 i 趟的排序过程为,在一组对象 r[i]～ r[n]
(i=1,2,…,n -1)中选择具有最小关键字的对象；
并和第 i 个对象进行交换；
简单选 择排序 (Simple Selection Sort)
简单选择排序的算法
void SelectSort(SqList &L)
{ for (int i=1; i<L.length;++i)
{ int k=i;
for (int j=i+1;j<=L.length;++j)
if (L.r[k].key > L.r[j].key) k=j;
if (i!=k){ ElemType temp=L.r[i];
L.r[i]=L.r[k];
L.r[k]=temp;
}
}
}
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25 16
25 16
08
49
08
25*49 21i = 2
i = 3
08 16
25* 25 21
初始最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
4925*
0 1 2 3 4 5
25*i = 5
251608
49
25* 4921结果
i = 4
08 16 2521
最小者 25*
无交换最小者 25
无交换252116
08
各趟排序后的结果
0 1 2 3 4 5
49
1608 25*49 21
08 25*
25
21
i =2时选择排序的过程
i k j
4925
08 25* 16 21
i k j
49? 25
25*? 25
1625
i k j 16 < 25
4925
08 25* 16 21
0 1 2 3 4 5
i k j 21? 16
k 指示当前序列中最小者算法分析
直接选择排序的关键字比较次数 KCN与对象的初始排列无关。第 i 趟选择具有最小关键字对象所需的比较次数总是 n-i-1 次，此处假定整个待排序对象序列有 n 个对象。因此，总的关键字比较次数为
对象的移动次数与对象序列的初始排列有关。
当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数 RMN = 0，
达到最少。
最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN = 3(n-1)。
直接选择排序是一种 不稳定 的排序方法。
2
0 2
11n
i
nninKC N )()(
锦标赛排序 (Tournament Tree Sort)
树形选择排序 (Tree Selection Sort)
它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，
得到?n/2?个比较的优胜者 (关键字小者 )，
作为第一步比较的结果保留下来。然后对这?n/2?个对象再进行关键字的两两比较,…,如此重复，直到选出一个关键字最小的对象为止。
在图例中，最下面是对象排列的初始状态，
相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。
如果 n 不是 2的 k 次幂,则让叶结点数补足到满足 2k-1 < n? 2k 的 2k个 。 叶结点上面一层的非叶结点是叶结点关键字两两比较的结果 。
最顶层是树的根 。
08
Winner
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
胜者树的概念
每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点,称这种比赛树为胜者树 。
位于最底层的叶结点叫做胜者树的外结点,
非叶结点称为胜者树的内结点 。 每个结点除了存放对象的关键字 key 外,还存放了此对象是否要参选的标志 Active 和此对象在满二叉树中的序号 index。
胜者树最顶层是树的根，表示最后选择出来的具有最小关键字的对象。
08
Winner (胜者 )
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
形成初始胜者树（最小关键字上升到根）
a[0]
关键字比较次数,6
16
Winner (胜者 )
21 16
16 6325*21
21 25 49 25* 16 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出冠军并调整胜者树后树的状态
a[1]
关键字比较次数,2
21
Winner (胜者 )
21 63
6325*21
21 25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出亚军并调整胜者树后树的状态
a[2]
关键字比较次数,2
25
Winner (胜者 )
25 63
6325*25
25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第三名并调整胜者树后树的状态
a[3]
关键字比较次数,2
25*
Winner (胜者 )
25* 63
6325*
49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第四名并调整胜者树后树的状态
a[4]
关键字比较次数,2
63
Winner (胜者 )
63
63
63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
全部比赛结果输出时树的状态
a[6]
关键字比较次数,2
归并排序 (Merge Sort)
归并，是将两个或两个以上的有序表合并成一个新的有序表。
对象序列 initList 中有两个有序表 V[l] … V[m]
和 V[m+1] … V[n]。它们可归并成一个有序表，
存于另一对象序列 mergedList 的 V[l] … V[n]中。
这种归并方法称为 2-路归并 (2-way merging)。
其基本思想是：设两个有序表 A和 B的对象个数 (表长 )分别为 al 和 bl，变量 i 和 j 分别是表
A和表 B的当前检测指针。设表 C是归并后的新有序表，变量 k 是它的当前存放指针。
08 21 25 25* 49 62 72 93 16 37 54
l m m+1 n
initList
i j
08 16 21 25 25* 37 49 54 62 72 93
l n
k
mergeList
当 i 和 j 都在两个表的表长内变化时，根据
A[i]与 B[j]的关键字的大小，依次把关键字小的对象排放到新表 C[k]中；
当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表 C[k]中。
归并排序算法
迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：
假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项 )，先做两两归并，得到?n / 2?个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为
1)；再做两两归并,…,如此重复，最后得到一个长度为 n 的有序序列。
此算法的关键字比较次数和对象移动次数均为
(m - l + 1) + (n - m) = n - l + 1。
两路归并算法
void Merge(ElemType SR[],ElemType TR[],int i,
int m,int n)
//将有序表的 SR[i..m]和 SR[m+1..n]归并为有序的 TR[I..n]
{
for (int j=m+1,k=i;i<=m && j<=n; ++k)
{
if (LQ(SR[i].key,SR[j].key))
TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i<=m)
for (int n1=k,n2=i;n1<=n && n2<=m;n1++,n2++)
TR[n1]=SR[n2];
if (j<=n)
for (int n1=k,n2=j;n1<=n && n2<=n;n1++,n2++)
TR[n1]=SR[n2];
}
归并排序算法
21 25
25*
25* 93 62 72 08 37 16 5449
21 25 49 62 93 08 72 16 37 54
21 25 25* 49 08 62 72 93 16 37 54
08
08
21
16
25
21
25*
25
49
25*
62
37
72
49
93
54
16 37 54
62 72 93
len=1
len=2
len=4
len=8
len=16
算法分析
归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组 。 这是这个算法的缺点 。
归并排序是一个稳定的排序方法 。
基数排序 (Radix Sort)
基数排序是采用,分配,与,收集,的办法，
用对多关键字进行排序的思想实现对单关键字进行排序的方法。 多关键字排序
以扑克牌排序为例 。 每张扑克牌有两个,关键字,,花色和面值 。 其有序关系为：
花色,
面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J <
Q < K < A
如果我们把所有扑克牌排成以下次序：
2,…,?A,?2,…,?A,?2,…,?A,?
2,…,?A
这就是 多关键字排序 。排序后形成的有序序列叫做词典有序序列。
对于上例两关键字的排序，可以先按花色排序，
之后再按面值排序；也可以先按面值排序，再按花色排序。
一般情况下，假定有一个 n 个对象的序列 {V0,
V1,…,Vn-1 }，且每个对象 Vi 中含有 d 个关键字
如果对于序列中任意两个对象 Vi 和 Vj ( 0? i< j
n-1 ) 都满足：
diii KKK,,,?21
djjjdiii KKKKKK,,,,,, 2121?
则称序列对关键字 (K1,K2,…,Kd) 有序。其中，
K1 称为最高位关键字,Kd 称为最低位关键字。
如果关键字是由多个数据项组成的数据项组，
则依据它进行排序时就需要利用多关键字排序。
实现多关键字排序有两种常用的方法
最高位优先 MSD (Most Significant Digit first)
最低位优先 LSD (Least Significant Digit first)
最高位优先法 通常是一个递归的过程：
先根据 最高位关键字 K1排序,得到若干对象组，
对象组中每个对象都有相同 关键字 K1。
再分别对每组中对象根据 关键字 K2进行排序,
按 K2值的不同,再分成若干个更小的子组,
每个子组中的对象具有相同的 K1和 K2值 。
依此重复,直到对 关键字 Kd完成排序为止 。
最后,把所有子组中的对象依次连接起来,
就得到一个有序的对象序列 。
最低位优先法 首先依据 最低位关键字 Kd对所有对象进行一趟排序,再依据 次低位关键字 Kd-1对上一趟排序的结果再排序,依次重复,直到依据 关键字 K1最后一趟排序完成,就可以得到一个有序的序列 。 使用这种排序方法对每一个关键字进行排序时,不需要再分组,而是整个对象组都参加排序 。
基数排序是典型的 LSD排序方法,利用,分配,
和,收集,两种运算对单关键字进行排序 。 在这种方法中,把 单关键字 Ki 看成是一个 d元组,
其中的每一个分量 ( 1? j? d ) 也可看成是一个关键字 。
diii KKK,,,?21
LSD和 MSD方法也可应用于对一个关键字进行的排序。此时可将 单关键字 Ki 看作是一个子关键字组：
diii KKK,,,?21
链式基数排序
jiK
jiK
分量 (1? j? d ) 有 radix种取值,则称 radix为基数 。 例如,关键字 984可以看成是一个 3元组
(9,8,4),每一位有 0,1,…,9等 10种取值,基数
radix = 10。 关键字 ‘ data’可以看成是一个 4元组 (d,a,t,a),每一位有 ‘ a’,‘b’,…,‘z’等 26种取值,radix = 26。
针对 d元组中的每一位分量,把对象序列中的所有对象,按 的取值,先,分配,到 rd个队列中去 。 然后再按各队列的顺序,依次把对象从队列中,收集,起来,这样所有对象按取值排序完成 。
jiK
jiK
jiK
如果对于所有对象的关键字 K0,K1,…,Kn-1，依次对各位的分量，让 j = d,d-1,…,1,分别用这种,分配,、“收集”的运算逐趟进行排序，
在最后一趟“分配”、,收集,完成后，所有对象就按其关键字的值从小到大排好序了。
各队列采用链式队列结构，分配到同一队列的关键字用链接指针链接起来。每一队列设置两个队列指针,int front [radix]指示队头,int
rear [radix] 指向队尾。
为了有效地存储和重排 n 个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。
基数排序的“分配”与“收集”过程 第一趟614 921 485 637738 101 215 530 790 306
第一趟分配（按最低位 i = 3 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738921 485 637
101 215
530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第一趟收集
530 790 921 101 614 485 215 306 637 738
基数排序的“分配”与“收集”过程 第二趟 614921 485 637 738101 215530 790 306
第二趟分配（按次低位 i = 2 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614
738
921 485
637
101
215
530 790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第二趟收集
530 790921101 614 485215306 637 738
基数排序的“分配”与“收集”过程 第三趟 614 921 485637 738101 215 530 790306
第三趟分配（按最高位 i = 1 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738 921485
637
101 215 530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第三趟收集
530 790 921101 614485215 306 637 738
小结 需要复习的知识点
排序的基本概念
排序的基本概念
关键字、初始关键字排列
关键字比较次数、数据移动次数
稳定性
附加存储
插入排序
直接插入排序、折半插入排序的过程
直接插入排序和折半插入排序的算法
排序的性能分析
当待排序的关键字序列已经基本有序时，
用直接插入排序最快
选择排序
直接选择排序、锦标赛排序、堆排序的过程
直接选择排序和堆排序的算法
三种选择排序的性能分析
用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。
交换排序
起泡排序和快速排序的过程
起泡排序的算法
快速排序的 递归算法 和用栈实现的 非递归算法
快速排序是一个递归的排序法
当待排序关键字序列已经基本有序时，
快速排序显著变慢。
二路归并排序
二路归并排序的过程
二路归并排序的非递归算法
该算法的性能分析
归并排序可以递归执行
归并排序需要较多的附加存储。
归并排序对待排序关键字的初始排列不敏感，故排序速度较稳定。
思考题：
1,已知一组记录为 (46,74,53,14,26,38,86,65,27,34),给出采用下列排序时每一趟的排序结果：
1） 直接插入排序
2） 快速排序法
3） 归并排序法
2,试以单链表为存储结构实现简单选择排序的算法 。
作业
1；直接插入法：
第一趟,46 74 53 14 26 38 86 65 27 34
第二趟,46 53 74 14 26 38 86 65 27 34
第三趟,14 46 53 74 26 38 86 65 27 34
第四趟,14 26 46 53 74 38 86 65 27 34
第五趟,14 26 38 46 53 74 86 65 27 34
第六趟,14 26 38 46 53 74 86 65 27 34
第七趟,14 26 38 46 53 65 74 86 27 34
第八趟,14 26 27 38 46 53 65 74 86 34
第九趟,14 26 27 34 38 46 53 65 74 86
2；归并排序法：
第一趟 (46 74),(14 53) (26 38),(65 86) (27 34)
第二趟（ 14 46 53 74），（ 26 38 65 86） （ 27 34）
第三趟（ 14 26 38 46 53 65 74 86），（ 27 34）
第四趟,14 26 27 34 38 46 53 65 74 86
插入排序 （直接插入、折半插入、表插入排序、
希尔排序）
交换排序 （起泡排序、快速排序）
选择排序 （简单选择排序、树形选择排序、堆排序）
归并排序
基数排序
小结第 9章 内部排序概述
排序,将一组杂乱无章的数据排列成一个按关键字有序的序列 。
数据表 (datalist),它是待排序数据对象的有限集合 。
关键字 (key),通常数据对象有多个 属性域,
即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据 。 该域即为关键字 。
每个数据表用哪个属性域作为关键字,要视具体的应用需要而定 。 即使是同一个表,在解决不同问题的场合也可能取不同的域做关键字 。
主关键字,如果在数据表中各个对象的关键字互不相同，这种关键字即主关键字。按照主关键字进行排序，排序的结果是唯一的。
次关键字,数据表中有些对象的关键字可能相同，这种关键字称为次关键字。按照次关键字进行排序，排序的结果可能不唯一。
排序算法的稳定性,如果在对象序列中有两个对象 r[i]和 r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对象 r[i]排在 r[j]前面。如果在排序之后，对象 r[i]仍在对象 r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。
内排序与外排序,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序的时间开销,排序的时间开销是衡量算法好坏的最重要的标志。 排序的时间开销可用算法执行中的 数据比较次数 与 数据移动次数 来衡量 。各节给出算法运行时间代价的大略估算一般都 按平均情况 进行估算。对于那些 受对象关键字序列初始排列及对象个数影响较大的,需要 按最好情况 和 最坏情况 进行估算 。
静态排序,排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。
动态排序,给每个对象增加一个链接指针，
在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。
算法执行时所需的附加存储,评价算法好坏的另一标准。
衡量排序方法的标准
排序时所需要的平均比较次数
排序时所需要的平均移动
排序时所需要的平均辅助存储空间待排记录的数据类型定义为：
#define MAXSIZE 20
Typedef int KeyType
Typedef struct
{KeyType key; //关键字项
InfoType otherinfo; //其它数据项
}RedType;
Typedef struct
{RedType r[MAXSIZE+1] //r[0]闲置或用作哨兵
int length;
}Sqlist;
插入排序 (Insert Sorting)
直接插入排序的基本思想是：当插入第 i (i? 1) 个对象时，前面的 V[0],V[1],…,v[i-1]已经排好序。这时，用
v[i]的关键字与 v[i-1],v[i-2],… 的关键字顺序进行比较，
找到插入位置即将 v[i]插入，原来位置上之后的所有对象依次向后顺移。
插入排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
直接插入排序 (Insert Sort)
各趟排序结果
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 49 25* 16 08 25i = 1
0 1 2 3 4 5 temp
21 25 49 25* 16 08 49i = 2
21 25 49 25* 16 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 16 08i = 4
0 1 2 3 4 5 temp
21 25 4925*16 08i = 5
i = 3 25*
16
08
16
4916
16
21 25 4925*1608
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 25 4925* 08
i = 4 时的排序过程
0 1 2 3 4 5 temp
21 25 4925*
完成
16
08 16
i = 4
j = 3
i = 4
j = 2
25
25*16
16
21 25 4925* 08
0 1 2 3 4 5
0 1 2 3 4 5 temp
21 4925* 08
0 1 2 3 4 5 temp
21 25 4925*
16
08 16
16
25
21
i = 4
j = 1
i = 4
j = 0
i = 4
j = -1 16
直接插入排序的算法
void InsertSort(SqList &L)
{ for (int i=2;i<=L.length;++i)
if (LT(L.r[i].key,L.r[i-1].key))
{ L.r[0]=L.r[i]; // L.r[0]为监视哨
for (int j=i-1; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
算法分析
若设待排序的对象个数为 L.length= n，则该算法的主程序执行 n-1趟。
关键字比较次数和对象移动次数与对象关键字的初始排列有关。
最好情况下,排序前对象已经按关键字大小从小到大有序,每趟只需与前面的有序对象序列的最后一个对象的关键字比较 1 次,移动 2 次对象,总的关键字比较次数为 n-1,对象移动次数为 2(n-1)。
直接插入排序是一种 稳定 的排序方法。
直接插入排序算法的时间复杂度为 O(n2)
折半插入排序 (Binary Insertsort)
折半插入排序基本思想是：设在顺序表中有一个对象序列 V[0],V[1],…,v[n-1]。其中,v[0],
V[1],…,v[i-1] 是已经排好序的对象。在插入
v[i] 时，利用折半搜索法寻找 v[i] 的插入位置。
折半插入排序的算法
void BInsertSort(SqList &L)
{ int low,high,mid;
for (int i=2;i<=L.length;++i)
{ L.r[0]=L.r[i];
low = 1; high=i-1;
while (low <= high)
{ mid = (low+high)/2;
if (LT(L.r[0].key,L.r[mid].key)) high=mid-1;
else low=mid+1; }
for (int j=i-1; j>=high+1;--j) L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
说明,low 或者 high+1为插入点 稳定排序算法分析
对分查找比顺序查找快，所以对分插入排序就平均性能来说比直接插入排序要快。
它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。
当 n 较大时，总关键字比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。
对分插入排序是一个 稳定 的排序方法。
希尔排序 (Shell Sort)
希尔排序方法又称为“缩小增量”排序。
该方法的基本思想是：先将整个待排对象序列按照一定间隔分割成为若干子序列，分别进行直接插入排序，然后缩小间隔，对整个对象序列重复以上的划分子序列和分别排序工作，直到最后间隔为 1，此时整个对象序列已,基本有序”，进行最后一次直接插入排序。
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*
i = 1
08
49
gap = 3
25 16
4925 16
08
49 25*
0821
2521 25* 16
21 25 4925*16 08
0 1 2 3 4 5
21
i = 2
08
49
gap = 2
25
16
4916 25*
0821 25
4925*
08 16 21 25* 25
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
gap = 1
2516 4925*
开始时 gap（间隔值） 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，
gap 值逐渐变小，子序列中对象个数逐渐变多，
由于前面工作的基础，大多数对象已基本有序，
所以排序速度仍然很快。
希尔排序的算法
void ShellSort(SqList &L,int dlta[],int t){
for (int k=0;k<t;++k){
ShellInsert(L,dlta[k]);
}
}
说明,dlta[3]={5,3,1}
//一趟希尔排序,按间隔 dk划分子序列
void ShellInsert(SqList &L,int gap)
{
for (int i=gap+1;i<=L.length;++i)
{if (LT(L.r[i].key,L.r[i-gap].key))
{ L.r[0]=L.r[i];
for (int j=i-gap;j>0 &&
LT(L.r[0].key,L.r[j].key); j-=gap)
L.r[j+gap]=L.r[j];
L.r[j+gap]=L.r[0];
}
}
}
算法分析
对特定的待排序对象序列,可以准确地估算关键字的比较次数和对象移动次数 。
但想要弄清关键字比较次数和对象移动次数与增量选择之间的依赖关系,并给出完整的数学分析,还没有人能够做到 。
gap的取法有多种 。 最初 shell 提出取 gap =
n/2?,gap =?gap/2?,直到 gap = 1。 后来
Knuth 提出取 gap =?gap/3? +1。 还有人提出都取奇数为好,也有人提出各 gap互质为好 。
交换排序 ( Exchange Sort )
起泡排序的基本方法是：设待排序对象序列中的对象个数为 n。最多作 n-1 趟 排序。在第 i
趟中顺次两两 比较 r[j-1].Key和 r[j].Key,j = i,
i+1,?,n-i-1。 如果发生逆序，则交换 r[j-1]和
r[j]。
交换排序的基本思想是两两比较待排序对象的关键字，如果发生逆序 (即排列顺序与排序后的次序正好相反 )，则交换之，直到所有对象都排好序为止。
起泡排序 (Bubble Sort)
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25 16 49
chang=1
08
25*
chang=1
i = 2
i = 3 0816
chang=1
25*2521
4921 25 16 08
25*
0 1 2 3 4 5
i = 4 4916
chang=108
2521
25*
0 1 2 3 4 5
i = 5 4916
chang=008
2521
void BubbleSort(SqList &L)
{ int i,j,tag;
j = L.length-1;
do{ tag=1;
for(i=1; i<=j; i++)
if( L.r[i+1].key< L.r[i].key )
{ L.r[0]= L.r[i+1]; L.r[i+1]= L.r[i];
L.r[i]= L.r[0]; tag=0;
}
if( !tag ) j--;
} while( !tag &&j );
return;
}
起泡排序的算法 —— 1
void BubbleSort(SqList &L)
{for (int i=L.length,change=TRUE;i>1 && change; --i)
{ change = FALSE;
for (int j=1; j<i; ++j)
if (LT(L.r[j+1].key,L.r[j].key))
{ ElemType temp=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=temp;
change = TRUE;
}
}
}
起泡排序的算法 —— 2
算法分析
在对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟起泡，做 n-1 次关键字比较，不移动对象。这是最好的情形。
最坏的情形是算法执行了 n-1趟起泡，第 i 趟
(1? i? n) 做了 n- i 次关键字比较，执行了 n-i
次对象交换。这样在最坏情形下总的关键字比较次数 KCN和对象移动次数 RMN为：
起泡排序需要一个附加对象以实现对象值的对换。
起泡排序是一个稳定的排序方法。
1
1
1
1
1
2
3
3
1
2
1
n
i
n
i
nninR M N
nninKCN
)()(
)()(
快速排序 (Quick Sort)
快速排序方法的基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象 ) 作为枢轴 (pivot)，按照该对象的关键字大小，将整个对象序列划分为左右两个子序列：
左侧子序列中所有对象的关键字都小于或等于 枢轴 对象的关键字
右侧子序列中所有对象的关键字都大于 枢轴 对象的关键字
枢轴对象则排在这两个子序列中间 (这也是该对象最终应安放的位置 )。
然后分别对这两个子序列重复施行上述方法，
直到所有的对象都排在相应位置上为止。
算法描述
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
2516
2516
08
49
pivot
08
25*4921i = 2
i = 3
08 16 25*2521
pivotpivot
pivot
快速排序的算法
void QSort(SqList &L,int low,int high){
if (low < high)
{
int pivotloc = Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L){
QSort(L,1,L.length);
}
int Partition(SqList &L,int low,int high)
{ L.r[0] = L.r[low];
int pivotkey = L.r[low].key;
while (low < high)
{ while (low<high && L.r[high].key >= pivotkey) --high;
L.r[low] = L.r[high];
while (low<high && L.r[low].key <= pivotkey) ++low;
L.r[high] = L.r[low];
}
L.r[low]=L.r[0];
return low;
}
算法 quicksort是一个递归的算法，其递归树如图所示。
算法 partition利用序列第一个对象作为枢轴，
将整个序列划分为左右两个子序列。算法中执行了一个循环，只要是关键字小于枢轴对象关键字的对象都移到序列左侧，最后枢轴对象安放到位，函数返回其位置。
21
25*
25
49
08
16
算法分析
从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。
如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。
可以证明，函数 quicksort的平均计算时间也是
o(nlog2n)。实验结果表明,就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个 。
快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数 。
在最坏的情况,即待排序对象序列已经按其关键字从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列 。 这样,必须经过 n-1 趟才能把所有对象定位,而且第 i 趟需要经过
n-i 次关键字比较才能找到第 i 个对象的安放位置,总的关键字比较次数将达到
212
1 21
1
nnninn
i
)()(
选择排序的基本思想是：每一趟 (例如第 i 趟，
i = 1,…,n-1) 在后面的 n-i+1 个待排序对象中选出关键字最小的对象,作为有序对象序列的第 i 个对象。待到第 n-1 趟作完，待排序对象只剩下 1个
，就不用再选了。
选择排序 (Selection Sort)
基本步骤为,i从 1开始，直到 n-1，进行 n-1趟排序，第 i 趟的排序过程为,在一组对象 r[i]～ r[n]
(i=1,2,…,n -1)中选择具有最小关键字的对象；
并和第 i 个对象进行交换；
简单选 择排序 (Simple Selection Sort)
简单选择排序的算法
void SelectSort(SqList &L)
{ for (int i=1; i<L.length;++i)
{ int k=i;
for (int j=i+1;j<=L.length;++j)
if (L.r[k].key > L.r[j].key) k=j;
if (i!=k){ ElemType temp=L.r[i];
L.r[i]=L.r[k];
L.r[k]=temp;
}
}
}
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25 16
25 16
08
49
08
25*49 21i = 2
i = 3
08 16
25* 25 21
初始最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
4925*
0 1 2 3 4 5
25*i = 5
251608
49
25* 4921结果
i = 4
08 16 2521
最小者 25*
无交换最小者 25
无交换252116
08
各趟排序后的结果
0 1 2 3 4 5
49
1608 25*49 21
08 25*
25
21
i =2时选择排序的过程
i k j
4925
08 25* 16 21
i k j
49? 25
25*? 25
1625
i k j 16 < 25
4925
08 25* 16 21
0 1 2 3 4 5
i k j 21? 16
k 指示当前序列中最小者算法分析
直接选择排序的关键字比较次数 KCN与对象的初始排列无关。第 i 趟选择具有最小关键字对象所需的比较次数总是 n-i-1 次，此处假定整个待排序对象序列有 n 个对象。因此，总的关键字比较次数为
对象的移动次数与对象序列的初始排列有关。
当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数 RMN = 0，
达到最少。
最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN = 3(n-1)。
直接选择排序是一种 不稳定 的排序方法。
2
0 2
11n
i
nninKC N )()(
锦标赛排序 (Tournament Tree Sort)
树形选择排序 (Tree Selection Sort)
它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，
得到?n/2?个比较的优胜者 (关键字小者 )，
作为第一步比较的结果保留下来。然后对这?n/2?个对象再进行关键字的两两比较,…,如此重复，直到选出一个关键字最小的对象为止。
在图例中，最下面是对象排列的初始状态，
相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。
如果 n 不是 2的 k 次幂,则让叶结点数补足到满足 2k-1 < n? 2k 的 2k个 。 叶结点上面一层的非叶结点是叶结点关键字两两比较的结果 。
最顶层是树的根 。
08
Winner
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
胜者树的概念
每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点,称这种比赛树为胜者树 。
位于最底层的叶结点叫做胜者树的外结点,
非叶结点称为胜者树的内结点 。 每个结点除了存放对象的关键字 key 外,还存放了此对象是否要参选的标志 Active 和此对象在满二叉树中的序号 index。
胜者树最顶层是树的根，表示最后选择出来的具有最小关键字的对象。
08
Winner (胜者 )
21 08
08 6325*21
21 25 49 25* 16 08 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
形成初始胜者树（最小关键字上升到根）
a[0]
关键字比较次数,6
16
Winner (胜者 )
21 16
16 6325*21
21 25 49 25* 16 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出冠军并调整胜者树后树的状态
a[1]
关键字比较次数,2
21
Winner (胜者 )
21 63
6325*21
21 25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出亚军并调整胜者树后树的状态
a[2]
关键字比较次数,2
25
Winner (胜者 )
25 63
6325*25
25 49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第三名并调整胜者树后树的状态
a[3]
关键字比较次数,2
25*
Winner (胜者 )
25* 63
6325*
49 25* 63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
输出第四名并调整胜者树后树的状态
a[4]
关键字比较次数,2
63
Winner (胜者 )
63
63
63
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]
全部比赛结果输出时树的状态
a[6]
关键字比较次数,2
归并排序 (Merge Sort)
归并，是将两个或两个以上的有序表合并成一个新的有序表。
对象序列 initList 中有两个有序表 V[l] … V[m]
和 V[m+1] … V[n]。它们可归并成一个有序表，
存于另一对象序列 mergedList 的 V[l] … V[n]中。
这种归并方法称为 2-路归并 (2-way merging)。
其基本思想是：设两个有序表 A和 B的对象个数 (表长 )分别为 al 和 bl，变量 i 和 j 分别是表
A和表 B的当前检测指针。设表 C是归并后的新有序表，变量 k 是它的当前存放指针。
08 21 25 25* 49 62 72 93 16 37 54
l m m+1 n
initList
i j
08 16 21 25 25* 37 49 54 62 72 93
l n
k
mergeList
当 i 和 j 都在两个表的表长内变化时，根据
A[i]与 B[j]的关键字的大小，依次把关键字小的对象排放到新表 C[k]中；
当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表 C[k]中。
归并排序算法
迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：
假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项 )，先做两两归并，得到?n / 2?个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为
1)；再做两两归并,…,如此重复，最后得到一个长度为 n 的有序序列。
此算法的关键字比较次数和对象移动次数均为
(m - l + 1) + (n - m) = n - l + 1。
两路归并算法
void Merge(ElemType SR[],ElemType TR[],int i,
int m,int n)
//将有序表的 SR[i..m]和 SR[m+1..n]归并为有序的 TR[I..n]
{
for (int j=m+1,k=i;i<=m && j<=n; ++k)
{
if (LQ(SR[i].key,SR[j].key))
TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i<=m)
for (int n1=k,n2=i;n1<=n && n2<=m;n1++,n2++)
TR[n1]=SR[n2];
if (j<=n)
for (int n1=k,n2=j;n1<=n && n2<=n;n1++,n2++)
TR[n1]=SR[n2];
}
归并排序算法
21 25
25*
25* 93 62 72 08 37 16 5449
21 25 49 62 93 08 72 16 37 54
21 25 25* 49 08 62 72 93 16 37 54
08
08
21
16
25
21
25*
25
49
25*
62
37
72
49
93
54
16 37 54
62 72 93
len=1
len=2
len=4
len=8
len=16
算法分析
归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组 。 这是这个算法的缺点 。
归并排序是一个稳定的排序方法 。
基数排序 (Radix Sort)
基数排序是采用,分配,与,收集,的办法，
用对多关键字进行排序的思想实现对单关键字进行排序的方法。 多关键字排序
以扑克牌排序为例 。 每张扑克牌有两个,关键字,,花色和面值 。 其有序关系为：
花色,
面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J <
Q < K < A
如果我们把所有扑克牌排成以下次序：
2,…,?A,?2,…,?A,?2,…,?A,?
2,…,?A
这就是 多关键字排序 。排序后形成的有序序列叫做词典有序序列。
对于上例两关键字的排序，可以先按花色排序，
之后再按面值排序；也可以先按面值排序，再按花色排序。
一般情况下，假定有一个 n 个对象的序列 {V0,
V1,…,Vn-1 }，且每个对象 Vi 中含有 d 个关键字
如果对于序列中任意两个对象 Vi 和 Vj ( 0? i< j
n-1 ) 都满足：
diii KKK,,,?21
djjjdiii KKKKKK,,,,,, 2121?
则称序列对关键字 (K1,K2,…,Kd) 有序。其中，
K1 称为最高位关键字,Kd 称为最低位关键字。
如果关键字是由多个数据项组成的数据项组，
则依据它进行排序时就需要利用多关键字排序。
实现多关键字排序有两种常用的方法
最高位优先 MSD (Most Significant Digit first)
最低位优先 LSD (Least Significant Digit first)
最高位优先法 通常是一个递归的过程：
先根据 最高位关键字 K1排序,得到若干对象组，
对象组中每个对象都有相同 关键字 K1。
再分别对每组中对象根据 关键字 K2进行排序,
按 K2值的不同,再分成若干个更小的子组,
每个子组中的对象具有相同的 K1和 K2值 。
依此重复,直到对 关键字 Kd完成排序为止 。
最后,把所有子组中的对象依次连接起来,
就得到一个有序的对象序列 。
最低位优先法 首先依据 最低位关键字 Kd对所有对象进行一趟排序,再依据 次低位关键字 Kd-1对上一趟排序的结果再排序,依次重复,直到依据 关键字 K1最后一趟排序完成,就可以得到一个有序的序列 。 使用这种排序方法对每一个关键字进行排序时,不需要再分组,而是整个对象组都参加排序 。
基数排序是典型的 LSD排序方法,利用,分配,
和,收集,两种运算对单关键字进行排序 。 在这种方法中,把 单关键字 Ki 看成是一个 d元组,
其中的每一个分量 ( 1? j? d ) 也可看成是一个关键字 。
diii KKK,,,?21
LSD和 MSD方法也可应用于对一个关键字进行的排序。此时可将 单关键字 Ki 看作是一个子关键字组：
diii KKK,,,?21
链式基数排序
jiK
jiK
分量 (1? j? d ) 有 radix种取值,则称 radix为基数 。 例如,关键字 984可以看成是一个 3元组
(9,8,4),每一位有 0,1,…,9等 10种取值,基数
radix = 10。 关键字 ‘ data’可以看成是一个 4元组 (d,a,t,a),每一位有 ‘ a’,‘b’,…,‘z’等 26种取值,radix = 26。
针对 d元组中的每一位分量,把对象序列中的所有对象,按 的取值,先,分配,到 rd个队列中去 。 然后再按各队列的顺序,依次把对象从队列中,收集,起来,这样所有对象按取值排序完成 。
jiK
jiK
jiK
如果对于所有对象的关键字 K0,K1,…,Kn-1，依次对各位的分量，让 j = d,d-1,…,1,分别用这种,分配,、“收集”的运算逐趟进行排序，
在最后一趟“分配”、,收集,完成后，所有对象就按其关键字的值从小到大排好序了。
各队列采用链式队列结构，分配到同一队列的关键字用链接指针链接起来。每一队列设置两个队列指针,int front [radix]指示队头,int
rear [radix] 指向队尾。
为了有效地存储和重排 n 个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。
基数排序的“分配”与“收集”过程 第一趟614 921 485 637738 101 215 530 790 306
第一趟分配（按最低位 i = 3 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738921 485 637
101 215
530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第一趟收集
530 790 921 101 614 485 215 306 637 738
基数排序的“分配”与“收集”过程 第二趟 614921 485 637 738101 215530 790 306
第二趟分配（按次低位 i = 2 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614
738
921 485
637
101
215
530 790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第二趟收集
530 790921101 614 485215306 637 738
基数排序的“分配”与“收集”过程 第三趟 614 921 485637 738101 215 530 790306
第三趟分配（按最高位 i = 1 ）
re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9]
614 738 921485
637
101 215 530
790
306
fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9]
第三趟收集
530 790 921101 614485215 306 637 738
小结 需要复习的知识点
排序的基本概念
排序的基本概念
关键字、初始关键字排列
关键字比较次数、数据移动次数
稳定性
附加存储
插入排序
直接插入排序、折半插入排序的过程
直接插入排序和折半插入排序的算法
排序的性能分析
当待排序的关键字序列已经基本有序时，
用直接插入排序最快
选择排序
直接选择排序、锦标赛排序、堆排序的过程
直接选择排序和堆排序的算法
三种选择排序的性能分析
用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。
交换排序
起泡排序和快速排序的过程
起泡排序的算法
快速排序的 递归算法 和用栈实现的 非递归算法
快速排序是一个递归的排序法
当待排序关键字序列已经基本有序时，
快速排序显著变慢。
二路归并排序
二路归并排序的过程
二路归并排序的非递归算法
该算法的性能分析
归并排序可以递归执行
归并排序需要较多的附加存储。
归并排序对待排序关键字的初始排列不敏感，故排序速度较稳定。
思考题：
1,已知一组记录为 (46,74,53,14,26,38,86,65,27,34),给出采用下列排序时每一趟的排序结果：
1） 直接插入排序
2） 快速排序法
3） 归并排序法
2,试以单链表为存储结构实现简单选择排序的算法 。
作业
1；直接插入法：
第一趟,46 74 53 14 26 38 86 65 27 34
第二趟,46 53 74 14 26 38 86 65 27 34
第三趟,14 46 53 74 26 38 86 65 27 34
第四趟,14 26 46 53 74 38 86 65 27 34
第五趟,14 26 38 46 53 74 86 65 27 34
第六趟,14 26 38 46 53 74 86 65 27 34
第七趟,14 26 38 46 53 65 74 86 27 34
第八趟,14 26 27 38 46 53 65 74 86 34
第九趟,14 26 27 34 38 46 53 65 74 86
2；归并排序法：
第一趟 (46 74),(14 53) (26 38),(65 86) (27 34)
第二趟（ 14 46 53 74），（ 26 38 65 86） （ 27 34）
第三趟（ 14 26 38 46 53 65 74 86），（ 27 34）
第四趟,14 26 27 34 38 46 53 65 74 86
