第 1 页第 2 页
学习的意义：
早期的计算机约有一半的时间花在排序操作上，虽然随着计算机速度的提高，排序操作不再像早期那样占用计算机过多的时间，但它仍然是信息处理中最常用，也是最重要的运算之一。
实际上，在计算机科学中，排序仍然是组织数据最基本的运算，许多程序和软件均以它作为一个中间步骤。因此，人们设计了大量的排序算法以满足不同的需求。
计算机图灵奖获得者，著名计算机科学家 D.E.Knuth在他的巨著,Art of Computer Programming,中列举分析了 25中经典排序方法，并且指出，这只是现有方法中的“一小部分”。
第 3 页
3.1 排序的基本概念
3.2 简单的排序方法
3.2.1 插入排序
3.2.2 起泡排序
3.3 先进的排序方法
3.3.1 快速排序
3.3.2 归并排序
3.3.3 堆排序
3.4 基数排序
3.4 各种排序方法的综合比较
主要内容：
第 4 页在很多情况下，相对于无序表而言，使用有序表可以提高算法效率，因为有序表可以充分利用其有序性采用一些效率较高的算法，例如，在进行数据元素的查找时，采用有序表比无序表效率要高很多。
如何得到有序表？我们可以在构造顺序表的时候依顺序表的有序性进行数据元素的插入，从而求得有序表。
更多的时候，我们需要对一个无序的顺序表进行“排序”
，将它转化为“有序”的顺序表。
3,1 排序的基本概念第 5 页排序 是按关键字的非递减或非递增顺序对一组记录重新进行整队 (或 )排列的操作,
姓名 电话号码蔡颖 63214444
陈红 63217777
刘建平 63216666
王小林 63218888
张力 63215555
...
3,1 排序的基本概念例 1,高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能；
例 2、数学中的数列（ 11,13,15,17,19,21）
例 3、英文字母表（ A,B,C,D,E? Z ）。
例 4、某单位的电话号码簿。
排序的定义第 6 页排序的形式化描述假设含有 n个记录的序列为：
{r1,r2,r3,…,rn}
它们的关键字相应为：
{k1,k2,k3,…,k n}
对记录序列进行排序就是确定序号 1,2,3,…,n的一种排列：
p1,p2,p3,…,p n
使其相应的关键字满足 非递减或非递增的关系
kp1≤ kp2 ≤ kp3。。。 ≤ kpn
也就是使记录序列重新排列成为一个按关键字有序的序列
1 2 3{,,,}p p p p nr r r r
第 7 页排序分类什么叫内部排序？什么叫外部排序？
若整个排序过程 不需要访问外存 便能完成，则称此类排序问题 为内部排序 ；称为内部排序；
反之，若参加排序的记录数量很大，整个序列的排序过程 不可能在内存中完成,则称此类排序问题为外部排序。
注,外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。
第 8 页内部排序的算法有哪些？
—— 按排序的规则不同，可分为 5类：
插入排序
交换排序（重点是快速排序）
选择排序
归并排序
基数排序
d＝ 关键字的位数 (长度 )
—— 按排序算法的时间复杂度不同，可分为 3类：
简单的排序算法：时间效率低,O(n2)
先进的排序算法,时间效率高,O( nlog2n )
基数排序算算法：时间效率高,O( d× n)
第 9 页按稳定性分类：
在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。
例 设 49,38,65,97,76,13,27,49 是待排序列排序后,13,27,38,49,49,65,76,97 —— 稳定排序后,13,27,38,49,49,65,76,97—— 不稳定稳性排序的应用：
例 股票交易系统 考虑一种股票交易 (清华紫光 )）
1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾 ；
2） 股票 交易系统按如下原则交易：
A） 申购价高者先成交
B） 申购价相同者按申购时间先后顺序成交第 10 页如何实现股票交易系统？
申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足原则交易
B）,要求排序方法是稳定的申购队列 （ 09,10),(06,10.5),(033,9.8),(051,10))
排序后,((06,10.5),(09,10),(051,10),(033,9.8))
第 11 页待排序记录在内存中怎样存储和处理？
① 顺序 排序 —— 排序时直接移动记录；
② 链表 排序 —— 排序时只移动指针；
③ 地址 排序 —— 排序时先移动地址，最后再移动记录。
注,地址排序 中可以增设一维数组来专门存放记录的地址。
第 12 页内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
经过一趟排序有序序列区 无 序 序 列 区有序序列区 无 序 序 列 区第 13 页选择排序从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。【 算法 3.1 】 一趟选择排序的算法如下：
void SelectPass( SqList &L,int i )
{
// 已知 L.r[1..i-1]中记录按关键字非递减有序，本算法实现第 i趟选择排序，
// 即在 L.r[i..n]的记录中选出关键字最小的记录 L.r[j]和 L.r[i]交换
RcdType W；
j = i； // j 指示关键字最小记录的位置，初值设为 i
for ( k=i+1; k<=L.length; k++ )
if ( L.r[k].key < L.r[j].key ) j = k ； // 暂不进行记录交换，只记录位置
if ( i != j )
{ W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； } // 最后互换记录 R[j] 和 R[i]
} // SelectPass
第 14 页
【 算法 3.2 】
void SelectSort (SqList &L)
{
// 对顺序表 L作简单选择排序。
RcdType W；
for (i=1; i<L.length; ++i) // 选择第 i小的记录，并交换到位
{
j = i；
for ( k=i+1; k<=L.length; k++ ) // 在 L.r[i..L.length]中选择 key最小的记录
if ( L.r[k].key < L.r[j].key ) j =k ；
if ( i!=j ) { W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； } // 与第 i个记录交换
}
} // SelectSort
整个选择排序的过程是一趟选择排序过程的多次重复，
融合 SelectPass。
第 15 页初试关键字：
491 38 65 492 76 13 27 52
i=1 （ 13） 38 65 492 76 491 27 52
i=2 （ 13 27） 65 492 76 491 38 52
i=3 （ 13 27 38） 492 76 491 65 52
i=4 （ 13 27 38 492） 76 491 65 52
i=5 （ 13 27 38 492 491） 76 65 52
i=6 （ 13 27 38 492 491 52） 65 76
i=7 （ 13 27 38 492 491 52 65 ） 76
【 例 3-1 】 对下面一组关键字：
491 38 65 492 76 13 27 52
进行选择排序，每趟排序之后的状况如下：
第 16 页选择排序时间性能分析对 n 个记录进行简单选择排序，所需进行的关键字间的比较次数 总计为,
移动记录的次数，最小值为 0,最大值为 3(n-1)
2
)1()(1
1
nninn
i
第 17 页简单排序算法，除前面讨论的选择排序外，常用的还有插入排序和起泡排序。
3.2 简单排序方法插入排序的基本思想：
每步将一个待排序的对象，按其关键码大小，
插入到前面 已经排好序的一组对象 的 适当位臵 上，
直到对象全部插入为止。
简而言之，边插入边排序,保证子序列中随时都是排好序的。
第 18 页利用,顺序查找,实现“在 R[1..i-1]中查找 R[i]的插入位臵”
直接插入排序算法实现：
当插入第 i (i? 1) 个对象时,前面的 r[0],r[1],…,
r[i-1]已经排好序。这时,用 r[i]的排序码与 r[i-1],r[i-
2],… 的排序码顺序进行比较,找到插入位置即将 r[i]插入,原来位置上的对象向后顺移。
第 19 页有序序列 R[1..i-1]
R[i]
无序序列 R[i..n]
有序序列 R[1..i] 无序序列 R[i+1..n]
一趟直接插入排序的基本思想：
第 20 页
【 算法 3.3 】
void InsertPass( SqList &L,int i )
{
// 已知 L.r[1..i-1]中的记录已按关键字非递减的顺序有序排列，本算法实现
// 将 L.r[i]插入其中，并保持 L.r[1..i]中记录按关键字非递减顺序有序
L.r[0] = L.r[i]; // 复制为哨兵
for ( j=i-1; L.r[0].key < L.r[j].key; --j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0]; // 插入到正确位置
} // InsertPass
注意：“哨兵”的作用一趟插入排序第 21 页从 R[i-1]起向前进行顺序查找,监视哨设臵在 R[0]；
R[0] = R[i]; // 设臵“哨兵”
循环结束表明 R[i]的插入位臵为 j +1
R[0]
j
R[i]
for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找插入位臵第 22 页对于在查找过程中找到的那些关键字不小于 R[i].key的记录，
并在查找的同时实现记录向后移动；
for (j=i-1; R[0].key<R[j].key; --j);
R[j+1] = R[j]
R[0]
j
R[i]
j= i-1
上述循环结束后可以直接进行“插入”
插入位臵第 23 页例 2,关键字序列 T= （ 21,25,49,25*,16,08），
请写出直接插入排序的具体实现过程。 *表示后一个 25
i=1
21 25 49 25* 16 08
0 1 2 3 4 5 6
暂存
i=2 i=3 i=5i=4 i=6
254925* 4916 25*08 49
解,假设该序列已存入一维数组 V[7]中，将 V[0]作为缓冲或暂存单元（ Temp）。则程序执行过程为：
21 25 49初态,16 25*25211608
完成 !
时间效率,O(n2)—— 因为在最坏情况下，所有元素的比较次数总和为
（ 0＋ 1＋ … ＋ n-1)→O(n 2)。其他情况下还要加上移动元素的次数。
空间效率,O(1)—— 因为仅占用 1个缓冲单元算法的稳定性：稳定 —— 因为 25*排序后仍然在 25的后面。
第 24 页
【 算法 3.4 】
void InsertSort ( SqList &L)
{
for ( i=2; i<=L.length; ++i ) // 对顺序表 L作插入排序
if ( L.r[i].key < L.r[i-1].key )
{ // "<"时，才需将 L.r[i]插入有序子表
L.r[0] = L.r[i]; // 复制为哨兵
for ( j=i-1; L.r[0].key < L.r[j].key; --j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0]; // 插入到正确位置
} // if
} // InsertSort
整个插入排序需要进行 n-1趟“插入”。
因为只含有一个关键字的序列必定是有序序列，因此，插入应该从 i=1开始进行，此外，若第 i个记录的关键字不小于第 i-1个关键字，插入也就不需要进行了。
第 25 页
49 38 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
初始时，有序子表中只有一个元素待排序记录集合：
38 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
i=2
i=3
i=4
65 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
97 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
第 26 页
38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
L.r[0].key < L.r[4].key，
L.r[4]记录后移看一下外层 For循环 i=5 时算法的执行的情况
L.r[5]复制为哨兵
76 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
76 38 49 65 97 97 13 27 49
0 1 2 3 4 5 6 7 8 9
76 38 49 65 97 97 13 27 49
0 1 2 3 4 5 6 7 8 9
L.r[0].key?L.r[3].key
找到插入位置
76 38 49 65 97 97 13 27 49
0 1 2 3 4 5 6 7 8 9
L.r[5]为待插入元素插入！ 76
第 27 页时间复杂度：
待排序列正向有序时,0 （ n）
待排序列逆向有序时,0（ n2）
一般待排序列,0（ n2）
插入排序特点：
1) 算法简单
2) 时间复杂度为 O（ n2 ）
3） 初始序列基本（正向）有序时，时间复杂度为 O（ n）
4） 稳定排序该方法适用于记录基本（正向）有序或 n较少的情况第 28 页性能分析：
基本操作,比较元素：比较、移动元素次数均取决于插入位置移动元素
①处理第 i个记录时待排序列递增（正向）有序时，比较元素次数最少,1次待排序列递减（逆向）有序时，比较元素次数最多,i 次一般待排序列，平均比较元素次数,(i+1)/2
② 对 n个记录待排序列,直接插入排序待排序列正向有序时，比较元素次数最少,n-1次待排序列逆向有序时，比较元素次数最多,(n+2)(n-1)/2次一般待排序列，平均比较元素次数大约为,n2/4
类似可分析移动元素次数第 29 页
3.2.2 起泡排序基本思想：
是通过对无序序列区中的记录进行相邻记录关键字的
“比较”和记录位置的“交换”实现较小的记录向“一头”漂移，
而关键字较大的记录向“另一头”下沉，从而达到记录按关键字非递减有序排列的目标。
第 30 页假设在排序过程中，记录序列 R[1..n]的状态为：
第 i 趟起泡排序无序序列 R[1..n-i+1] 有序序列 R[n-i+2..n]
n-i+1
无序序列 R[1..n-i] 有序序列 R[n-i+1..n]
比较相邻记录，将 关键字最大的记录 交换 到 n-i+1 的位臵上第 31 页
1) 冒泡排序基本思路,每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。
优点,每趟结束时，不仅能挤出一个最大值到最后面位臵，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。
前提,顺序存储结构例,关键字序列 T=(21,25,49,25*,16,08），请写出冒泡排序的具体实现过程。
21,25,49,25*,16,08
21,25,25*,16,08,49
21,25,16,08,25*,49
21,16,08,25,25*,49
16,08,21,25,25*,49
08,16,21,25,25*,49
初态：
第 1趟第 2趟第 3趟第 4趟第 5趟第 32 页
【 具体算法 3.5 】
void BubbleSort( SqList &L )
{
// 对顺序表 L作起泡排序,
RcdType W；
i = L.length;
while (i >1) { // i>1 表明上一趟曾进行过记录的交换
lastExchangeIndex = 1;
for (j = 1; j < i; j++)
{
if (L.r[j+1].key < L.r[j].key) {
W=L.r[j]； L.r[j] =L.r[j+1]； L.r[j+1] = W； // 互换记录
lastExchangeIndex = j;
} //if
} //for
i = lastExchangeIndex; // 一趟排序中无序序列中最后一个记录的位置
} // while
} // BubbleSort
空间复杂度 O(1)
第 33 页注意,
2,一般情况下，每经过一趟“起泡”，,i 减一”，但并不是每趟都如此。
例如,
i=7
for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …
1,起泡排序的结束条件为，
最后一趟没有进行“交换记录”。
5 2 3 1 9 7 8
2 3 1 5 7 8 9
i=6i=2
1 3
第 34 页时间分析,
最好 的情况（关键字在记录序列中顺序有序）：
只需进行一趟起泡
“比较”的次数：
最坏 的情况（关键字在记录序列中逆序有序）：
需进行 n-1趟起泡
“比较”的次数：
0
“移动”的次数：
“移动”的次数：
n-1
2
)1()1(2
nni
ni 2
)1(3)1(3 2
nni
ni
第 35 页
3.3 先进的排序方法
3.3.1 快速排序 (quick sort)
快速排序是从起泡排序改进而得的一种“交换”排序方法，
它的基本思想是通过一趟排序将将记录分割成相邻的两个区域，
其中一个区域中记录的关键字均比另一区域中记录关键字小（区域内不一定有序），则可分别对这两个区域的记录进行再排序，
以达到整个序列有序。
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。
致使一趟排序之后，记录的无序序列 R[s..t]将分割成两部分,R[s..i-1]和 R[i+1..t],
且
R[j].key≤ R[i].key ≤ R[j].key
(s≤j≤i-1) 枢轴 (i+1≤j≤t)
第 36 页基本步骤：
为简洁起见，对待排记录仍只写出其关键字序列
1,(一趟快速排序）设被指定的关键字为待排序列的第一个关键字 k,i指向待排序列的的第一个关键字； j指向最后一个关键字；
若 i < j 循环：
1）从后向前将关键字与 k比较，直至遇到小于 k的 关键字 k’,k’ 前移；
2） 从前向后将关键字与 k比较，直至遇到大于 k的 关键字 k’’,k’’后移；
（一趟快速排序后,,小,记录被移至 k 前,,大,的记录被移至 k 后
2,继续对 k前后两部分关键字进行快速排序，直至排序范围为 1;
第 37 页
27 38 65 97 76 13 27 49
i i
27 38 65 97 76 13 65 49
j j
27 38 13 49 76 97 65 49
j ji
被指定的关键字 从后向前，将关键字与 49比较，
直至遇到小于 49
的关键字，前移从后向前，将关键字与 49比较，
直至遇到小于 49
的关键字，前移从前向后，将关键字与 49比较，
直至遇到大于 49
的关键字，后移从前向后，将关键字与 49比较，
直至遇到大于 49
的关键字，后移
27 38 13 97 76 13 65 49
i i
从后向前，将关键字与 49比较，
直至遇到 i=j,将
49放至 i处
49
一趟 快速 排序结束例 待排记录 49 38 65 97 76 13 27 49
jj
第 38 页
[27 38 13] 49 [76 97 65 49]
[13 27 38] 49 [49 65 76 97]
[13] 27 [38] 49 [49 65] 76 [97]
13 27 38 49 49 65 76 97
两趟 快速 排序结束三趟 快速 排序结束快速 排序结束第 39 页
【 算法 3.7 】
void QSort (RedType R[],int s,int t )
{
// 对记录序列 R[s..t]进行快速排序
if (s < t)
{ // 长度大于 1
pivotloc = Partition(R,s,t);// 对 R[s..t] 进行一次划分，并返回枢轴位置
QSort(R,s,pivotloc-1); // 对低子序列递归排序
QSort(R,pivotloc+1,t); // 对高子序列递归排序
} // if
} // Qsort
int Partition (RedType R[],int s,int t )
{
key = R[s];
while ( s < t)
{
while (s < t && R[t] >= key ) t--;
R[s]R[t];
while (s < t && R[s] <= key) s++;
R[s]R[t];
}
return s;
}
【 算法 3.8 】
void QuickSort( SqList & L) {
// 对顺序表 L 进行快速排序
QSort(L.r,1,L.length);
} // QuickSort
第 40 页快速排序的时间分析：
假设 一次划分所得枢轴位臵 i=k,则对 n 个记录进行快排所需时间其中 Tpass(n)为对 n 个记录进行一次划分所需时间，
若待排序列中记录的关键字是随机分布的，则 k 取 1
至 n 中任意一值的可能性相同。
T(n) = Tpass(n) + T(k-1) + T(n-k)
第 41 页
1
1( ) ( 1 ) ( )n
a v g a v g a v g
k
T n Cn T k T n k
n?
设 Tavg(1)≤ b
则可得结果,
( ) ( 2 ) ( 1 ) l n ( 1 )2a v g bT n c n n
结论,快速排序的时间复杂度为 O(nlogn),快速排序是目前被认为同数量级中最快的内部排序算法。
由此可得快速排序所需时间的平均值为：
第 42 页若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序,其时间复杂度为 O(n2)。
为避免出现这种情况，需在进行一次划分之前，进行
“予处理”，即：
先对 R(s).key,R(t).key 和 R[?(s+t)/2?.key,进行相互比较，然后取关键字为,三者之中,的记录为枢轴记录。
第 43 页归并排序的基本思想是,将两个（或以上）的有序表组成新的有序表。
更实际的意义,可以把一个长度为 n 的无序序列看成是 n 个长度为 1 的有序子序列,首先做两两归并，得到?n / 2? 个长度为 2
的子序列 ；再做两两归并,…,如此重复，直到最后得到一个长度为 n 的有序序列。
例,关键字序列 T= （ 21,25,49,25*,93,62,72，
08,37,16,54），请给出归并排序的具体实现过程。
3.3.2 归并排序第 44 页
21 25 25* 93 62 72 08 37 16 5449
21 25 25* 49 62 93 08 72 16 37 54
16 37 54
21 25 25* 49 08 62 72 93
08 21 25 25* 49 62 72 93
08 16 21 25 25* 37 49 54 62 72 93
len=1
len=2
len=4
len=8
len=16
16 37 54
整个归并排序仅需?log2n?趟第 45 页
Void Merge (RcdType SR[ ],RcdType TR[ ],int i,int m,int n)
{
// 将有序的 SR[i…m] 和 SR[m+1…n] 归并为有序的 TR[i…n]
for(k=i,j=m+1; i<=m && j<=n; ++k )
{
if ( SR[i].key <= SR[j].key ) TR[k] = SR[i++];
else TR[k] = SR[j++]; // 将 SR中记录由小到大地并入 TR
}
if (i <= m) TR[k++] = SR[i++]; // 将剩余的 SR[i…m] 复制到 TR
if (j <= n) TR[k++] = SR[j++]; // 将剩余的 SR[j…n] 复制到 TR
} // Merge
一趟归并排序算法,(两路有序并为一路 ) 参见教材 P53
第 46 页
【 算法 3.11 】
void MergeSort (SqList &L) {
// 对顺序表 L作归并排序
MSort(L.r,L.r,1,L.length);
} // MergeSort
【 算法 3.10 】
void Msort ( RcdType SR[],RcdType TR1[],int s,int t ) {
// 对 SR[s..t]进行归并排序，排序后的记录存入 TR1[s..t]。
RcdType TR2[t-s+1]; //开设用于存放归并排序中间结果的辅助空间
if (s==t) TR1[s] = SR[s];
else {
m = (s+t)/2; // 将 SR[s..t]平分为 SR[s..m]和 SR[m+1..t]
Msort (SR,TR2,s,m); // 递归地将 SR[s..m]归并为有序的 TR2[s..m]
Msort (SR,TR2,m+1,t); // 递归地将 SR[m+1..t]归并为有序的 TR2[m+1..t]
Merge (TR2,TR1,s,m,t); // 将 TR2[s..m]和 TR2[m+1..t]归并到 TR1[s..t]
} // else
} // MSort
第 47 页归并排序算法分析：
时间效率,O(nlog2n)
因为在递归的归并排序算法中,函数 Merge( )做一趟两路归并排序,
需要调用 merge ( )函数?n/(2*len) O(n/len) 次,函数 Merge( )调用 Merge( )正好?log2n? 次,而每次 merge( )要执行比较 O(len)次,
所以算法总的时间复杂度为 O(nlog2n)。
空间效率,O(n)
因为需要一个与原始序列同样大小的辅助序列 （ TR） 。 这正是此算法的缺点 。
稳定性,稳定第 48 页
3.3.3 堆排序（ Heap Sort)）
堆的定义,
堆是满足下列性质的数列 {r1,r2,…,rn}：
2
21
ii
ii
rr
rr?
2
21
ii
ii
rr
rr?
(小顶堆 ) (大顶堆 )
堆排序 是利用堆的特性对记录序列进行排序的一种排序方法，是对 选择排序 的一种改进。
第 49 页
{12,36,27,65,40,34,98,81,73,55,49}
例如,
{12,36,27,65,40,14,98,81,73,55,49}
解释,如果让满足以上条件的元素序列 （ k1,k2,…,kn）
顺次排成一棵 完全二叉树,则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。
第 50 页
08
25
46
49
58 67
2 3
4 5 6
1
（大顶堆）
91
85
66
76
58 67
2 3
4 5 6
1
55
7
√ （小顶堆） √
（小根堆）
（最小堆）
（大根堆）
（最大堆）
例,有序列 T1=（ 08,25,49,46,58,67） 和序列 T2=（ 91,85,76,66,
58,67,55）,判断它们是否,堆”？
第 51 页
0 1 2 3 4 5 6
40 55 73 12 40 27
初始数据
H.r[1..6]
0 1 2 3 4 5 6
27 55 73 12 40 98
互换 H.r[1]和
H.r[6]
0 1 2 3 4 5 6
98 55 73 12 40 27
初建大顶堆第 52 页
0 1 2 3 4 5 6
73 55 27 12 40 98
重新将 H.r[1..5]
调整为大顶堆
0 1 2 3 4 5 6
40 55 27 12 73 98
互换 H.r[1]和
H.r[5]
0 1 2 3 4 5 6
12 40 27 55 73 98
重新将 H.r[1..4]
调整为大顶堆第 53 页
0 1 2 3 4 5 6
12 40 27 55 73 98
互换 H.r[1]和
H.r[4]
0 1 2 3 4 5 6
40 12 27 55 73 98
重新将 H.r[1..3]
调整为大顶堆
0 1 2 3 4 5 6
27 12 40 55 73 98
互换 H.r[1]和
H.r[3]
第 54 页
0 1 2 3 4 5 6
27 12 40 55 73 98
重新将 H.r[1..2]
调整为大顶堆
0 1 2 3 4 5 6
12 27 40 55 73 98
互换 H.r[1]和
H.r[2]
至此，堆排序结束,H.r[1..6]为有序序列。
第 55 页
3.4 基数排序基数排序（ Radix Sort）,
是一种借助,多关键字排序”的思想 来实现,单关键字排序,
的内部排序算法（ 即：用关键字 不同的位值 进行排序。 ）。
要讨论的问题：
1,什么是,多关键字,排序？ 实现方法？
2,单逻辑关键字怎样,按位值,排序？
多关键字排序的实现方法通常有两种：
1）最高位优先法 MSD (Most Significant Digit first)
2）最低位优先法 LSD (Least Significant Digit first)
第 56 页
以扑克牌排序为例 。 每张扑克牌有两个,排序码,,花色和面值 。 其有序关系为：
花色,
面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
如果我们把所有扑克牌排成以下次序：
2,…,? A,? 2,…,? A,? 2,…,? A,
2,…,? A
这就是多关键字排序。
第 57 页例,对一副扑克牌该如何排序？
答,若规定 花色为第一 关键字（高位）,面值为第二 关键字（低位），则使用 MSD和 LSD方法都可以达到排序目的。
MSD方法的思路,先设立 4个花色“箱”，将全部牌按花色分别归入 4个箱内（每个箱中有 13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。
LSD方法的思路,先按面值分成 13堆（每堆 4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。
想一想：用哪种方法更快些？
第 58 页
2,单逻辑 关键字怎样,按位值,排序？
思路,设 n 个记录的序列为,{V0,V1,…,Vn-1 },可以把每个记录 Vi 的 单关键码 Ki 看成是一个 d元组（ Ki1,Ki2,…,Kid）,则其中的每一个分量 Kij ( 1?
j? d ) 也可看成是一个关键字。
注 1,Ki1＝ 最高位关键字,Kid＝ 最低位关键字； Ki共有 d位,可看成 d元组；
注 2,每个分量 Kij (1? j? d ) 有 radix种取值,则称 radix为 基数 。
(9,8,4) (0,1,…,9)
（ a,b,…,z ）(d,i,a,n)
例 1,关键码 984可以看成是 3 元组；基数 radix 为 10 。
例 2,关键码 dian可以看成是 4 元组；基数 radix 为 26 。
第 59 页
0 1 2 3 4 5 6 7 8 9 10 11
78 09 63 30 74 89 94 25 05 69 18 83
初始状态
0 1 2 3 4 5 6 7 8 9
30 63
83
74
94
25
05
78
18
09
89
69
0 1 2 3 4 5 6 7 8 9 10 11
30 63 83 74 94 25 05 78 18 09 89 69
第一趟,分配,之后的结果第一趟,收集,之后的结果采用,分配,与,收集,的方法实现基数排序。
第 60 页
0 1 2 3 4 5 6 7 8 9
05
09
18 25 30 63
69
74
78
83
89
94
0 1 2 3 4 5 6 7 8 9 10 11
05 09 18 25 30 63 69 74 78 83 89 94
第二趟,分配,之后的结果第二趟,收集,之后的结果第 61 页对由顺序表表示法存储的记录进行基数排序可利用“计数”和
“复制”的操作实现。
0 1 2 3 4 5 6 7 8 9 10 11
78 09 63 30 74 89 94 25 05 69 18 83
记录数组 A
0 1 2 3 4 5 6 7 8 9
1 0 0 2 2 2 0 0 2 3
记数数组 count
(个位情况 )
0 1 2 3 4 5 6 7 8 9
1 1 1 3 5 7 7 7 9 12
累加结果
count
（ a） 初始状态和对“个位数”计数的结果第 62 页
0 1 2 3 4 5 6 7 8 9
1 1 1 3 5 7 7 7 9 12
累加结果
count
0 1 2 3 4 5 6 7 8 9 10 11
30 63 83 74 94 25 05 78 18 09 89 69
记录数组 B
0 1 2 3 4 5 6 7 8 9
2 1 1 1 0 0 2 2 2 1
记数数组 count
(十位情况 )
（ b） 计数器的累加结果和记录“复制”后的状态第 63 页
0 1 2 3 4 5 6 7 8 9
2 1 1 1 0 0 2 2 2 1
记数数组 count
(十位情况 )
0 1 2 3 4 5 6 7 8 9
2 3 4 5 5 5 7 9 11 12
累加结果
count
0 1 2 3 4 5 6 7 8 9 10 11
05 09 18 25 30 63 69 74 78 83 89 94
记录数组 A
（ c） 对“十位数”计数和“复制”和记录“复制”
后的状态第 64 页
【 算法 3.12 】
void RadixSort( SqList &L )
{
// 对顺序表 L 进行基数排序
RcdType C[L.length]; //开设同等大小的辅助空间用于复制数据
i= bitsnum-1;
while ( i >= 0 ) {
RadixPass( L.r,C,L.length,i ); // 对 L.r进行一趟基数排序，排序结果存入 C
i--;
if (i >=0 ) {
RadixPass( C,L.r,L.length,i ); // 对 C进行一趟基数排序，排序结果存入 L.r
i--;
}
else
for ( j=0; j<l.length; ++j ) L.r[j] = C[j]; // 排序后的结果在 C中，复制至 L.r中
}// while
}// RadixSort
第 65 页
【 算法 3.13 】
void RadixPass( RcdType A[],RcdType B[],int n,int i ) {
// 对数组 A中记录关键字的 "第 i位 "计数，并按计数数组 count的值
// 将数组 A中记录复制到数组 B中
for ( j=0; j<RADIX; ++j ) count[j] = 0; // 计数数组初始化为 0
for ( k=0; k<n; ++k ) count[ A[k].keys[i] ] ++; // 对关键字的对第 i位 "计数 "
for ( j=1; j<RADIX; ++j ) count[j] = count[j-1] + count[j]; // 累加操作
for ( k=n-1; k>=0; --k ) // 从右端开始复制记录
{
j = A[k].keys[i];
B[ count[j]-1 ] = A[k];
count[j]--;
}// for
}// RadixPass
时间复杂度,O(d× n)(d趟基数排序，每趟对 n个记录进行“计数”和“复制” )
空间复杂度,O(n)
第 66 页因为有分组，故此算法需递归实现。
思考：是借用 MSD方式来排序呢，还是借用 LSD方式？
方法 1（ MSD）,原始序列,32,13,27,32*,19,33
先按高位 Ki1 排序,（ 13,19）,27,（ 32,32*,33）
再按低位 Ki2 排序,13,19,27,32,32*,33
方法 2（ LSD）,原始序列,32,13,27,32*,19,33
先按低位 Ki2排序,32,32*,13,33,27,19
再按高位 Ki1排序,13,19,27,32,32*,33
无需分组，易编程实现！
例：初始关键字序列 T=（ 32,13,27,32*,19,33）,请分别用 MSD和 LSD
进行排序，并讨论其优缺点。
第 67 页
3.5 各种排序方法的比较第 68 页一、时间性能
1,平均的时间性能时间复杂度为 O(nlogn),快速排序、堆排序和归并排序时间复杂度为 O(n2),直接插入排序、起泡排序和简单选择排序时间复杂度为 O(n),基数排序2,当待排记录序列按关键字顺序有序时直接插入排序和起泡排序能达到 O(n)的时间复杂度 ;
快速排序的时间性能蜕化为 O(n2)
3,简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
第 69 页二、空间性能空间性能指的是排序过程中所需的辅助空间大小
1,所有的简单排序方法 (包括：直接插入、起泡和简单选择 ) 和堆排序的空间复杂度为 O(1)；
2,快速排序为 O(logn),为递归程序执行过程中，栈所需的辅助空间 ;
3,归并排序和基数排序所需辅助空间最多，其空间复杂度为 O(n);
第 70 页三、排序方法的稳定性能
1,稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位臵，在排序之前和经过排序之后，没有改变。
2,除快速排序、堆排序和希尔排序是不稳定的排序方法之外，本章讨论的其它排序方法都是稳定的排序方法。
3,对于不稳定的排序方法，只要能举出一个实例说明即可。
例如,对 { 4,3,4,2 } 进行快速排序，得到 { 2,3,4,4 }
第 71 页四、关于“排序方法的时间复杂度的下限”
本章讨论的各种排序方法，除基数排序外，其它方法都是基于
“比较关键字”进行排序的排序方法。可以证明,这类排序法可能达到的最快的时间复杂度为 O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制 )
第 72 页作业：
3.3 3.6 3.9 3.11
学习的意义：
早期的计算机约有一半的时间花在排序操作上，虽然随着计算机速度的提高，排序操作不再像早期那样占用计算机过多的时间，但它仍然是信息处理中最常用，也是最重要的运算之一。
实际上，在计算机科学中，排序仍然是组织数据最基本的运算，许多程序和软件均以它作为一个中间步骤。因此，人们设计了大量的排序算法以满足不同的需求。
计算机图灵奖获得者，著名计算机科学家 D.E.Knuth在他的巨著,Art of Computer Programming,中列举分析了 25中经典排序方法，并且指出，这只是现有方法中的“一小部分”。
第 3 页
3.1 排序的基本概念
3.2 简单的排序方法
3.2.1 插入排序
3.2.2 起泡排序
3.3 先进的排序方法
3.3.1 快速排序
3.3.2 归并排序
3.3.3 堆排序
3.4 基数排序
3.4 各种排序方法的综合比较
主要内容：
第 4 页在很多情况下，相对于无序表而言，使用有序表可以提高算法效率，因为有序表可以充分利用其有序性采用一些效率较高的算法，例如，在进行数据元素的查找时，采用有序表比无序表效率要高很多。
如何得到有序表？我们可以在构造顺序表的时候依顺序表的有序性进行数据元素的插入，从而求得有序表。
更多的时候，我们需要对一个无序的顺序表进行“排序”
，将它转化为“有序”的顺序表。
3,1 排序的基本概念第 5 页排序 是按关键字的非递减或非递增顺序对一组记录重新进行整队 (或 )排列的操作,
姓名 电话号码蔡颖 63214444
陈红 63217777
刘建平 63216666
王小林 63218888
张力 63215555
...
3,1 排序的基本概念例 1,高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能；
例 2、数学中的数列（ 11,13,15,17,19,21）
例 3、英文字母表（ A,B,C,D,E? Z ）。
例 4、某单位的电话号码簿。
排序的定义第 6 页排序的形式化描述假设含有 n个记录的序列为：
{r1,r2,r3,…,rn}
它们的关键字相应为：
{k1,k2,k3,…,k n}
对记录序列进行排序就是确定序号 1,2,3,…,n的一种排列：
p1,p2,p3,…,p n
使其相应的关键字满足 非递减或非递增的关系
kp1≤ kp2 ≤ kp3。。。 ≤ kpn
也就是使记录序列重新排列成为一个按关键字有序的序列
1 2 3{,,,}p p p p nr r r r
第 7 页排序分类什么叫内部排序？什么叫外部排序？
若整个排序过程 不需要访问外存 便能完成，则称此类排序问题 为内部排序 ；称为内部排序；
反之，若参加排序的记录数量很大，整个序列的排序过程 不可能在内存中完成,则称此类排序问题为外部排序。
注,外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。
第 8 页内部排序的算法有哪些？
—— 按排序的规则不同，可分为 5类：
插入排序
交换排序（重点是快速排序）
选择排序
归并排序
基数排序
d＝ 关键字的位数 (长度 )
—— 按排序算法的时间复杂度不同，可分为 3类：
简单的排序算法：时间效率低,O(n2)
先进的排序算法,时间效率高,O( nlog2n )
基数排序算算法：时间效率高,O( d× n)
第 9 页按稳定性分类：
在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。
例 设 49,38,65,97,76,13,27,49 是待排序列排序后,13,27,38,49,49,65,76,97 —— 稳定排序后,13,27,38,49,49,65,76,97—— 不稳定稳性排序的应用：
例 股票交易系统 考虑一种股票交易 (清华紫光 )）
1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾 ；
2） 股票 交易系统按如下原则交易：
A） 申购价高者先成交
B） 申购价相同者按申购时间先后顺序成交第 10 页如何实现股票交易系统？
申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足原则交易
B）,要求排序方法是稳定的申购队列 （ 09,10),(06,10.5),(033,9.8),(051,10))
排序后,((06,10.5),(09,10),(051,10),(033,9.8))
第 11 页待排序记录在内存中怎样存储和处理？
① 顺序 排序 —— 排序时直接移动记录；
② 链表 排序 —— 排序时只移动指针；
③ 地址 排序 —— 排序时先移动地址，最后再移动记录。
注,地址排序 中可以增设一维数组来专门存放记录的地址。
第 12 页内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
经过一趟排序有序序列区 无 序 序 列 区有序序列区 无 序 序 列 区第 13 页选择排序从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。【 算法 3.1 】 一趟选择排序的算法如下：
void SelectPass( SqList &L,int i )
{
// 已知 L.r[1..i-1]中记录按关键字非递减有序，本算法实现第 i趟选择排序，
// 即在 L.r[i..n]的记录中选出关键字最小的记录 L.r[j]和 L.r[i]交换
RcdType W；
j = i； // j 指示关键字最小记录的位置，初值设为 i
for ( k=i+1; k<=L.length; k++ )
if ( L.r[k].key < L.r[j].key ) j = k ； // 暂不进行记录交换，只记录位置
if ( i != j )
{ W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； } // 最后互换记录 R[j] 和 R[i]
} // SelectPass
第 14 页
【 算法 3.2 】
void SelectSort (SqList &L)
{
// 对顺序表 L作简单选择排序。
RcdType W；
for (i=1; i<L.length; ++i) // 选择第 i小的记录，并交换到位
{
j = i；
for ( k=i+1; k<=L.length; k++ ) // 在 L.r[i..L.length]中选择 key最小的记录
if ( L.r[k].key < L.r[j].key ) j =k ；
if ( i!=j ) { W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； } // 与第 i个记录交换
}
} // SelectSort
整个选择排序的过程是一趟选择排序过程的多次重复，
融合 SelectPass。
第 15 页初试关键字：
491 38 65 492 76 13 27 52
i=1 （ 13） 38 65 492 76 491 27 52
i=2 （ 13 27） 65 492 76 491 38 52
i=3 （ 13 27 38） 492 76 491 65 52
i=4 （ 13 27 38 492） 76 491 65 52
i=5 （ 13 27 38 492 491） 76 65 52
i=6 （ 13 27 38 492 491 52） 65 76
i=7 （ 13 27 38 492 491 52 65 ） 76
【 例 3-1 】 对下面一组关键字：
491 38 65 492 76 13 27 52
进行选择排序，每趟排序之后的状况如下：
第 16 页选择排序时间性能分析对 n 个记录进行简单选择排序，所需进行的关键字间的比较次数 总计为,
移动记录的次数，最小值为 0,最大值为 3(n-1)
2
)1()(1
1
nninn
i
第 17 页简单排序算法，除前面讨论的选择排序外，常用的还有插入排序和起泡排序。
3.2 简单排序方法插入排序的基本思想：
每步将一个待排序的对象，按其关键码大小，
插入到前面 已经排好序的一组对象 的 适当位臵 上，
直到对象全部插入为止。
简而言之，边插入边排序,保证子序列中随时都是排好序的。
第 18 页利用,顺序查找,实现“在 R[1..i-1]中查找 R[i]的插入位臵”
直接插入排序算法实现：
当插入第 i (i? 1) 个对象时,前面的 r[0],r[1],…,
r[i-1]已经排好序。这时,用 r[i]的排序码与 r[i-1],r[i-
2],… 的排序码顺序进行比较,找到插入位置即将 r[i]插入,原来位置上的对象向后顺移。
第 19 页有序序列 R[1..i-1]
R[i]
无序序列 R[i..n]
有序序列 R[1..i] 无序序列 R[i+1..n]
一趟直接插入排序的基本思想：
第 20 页
【 算法 3.3 】
void InsertPass( SqList &L,int i )
{
// 已知 L.r[1..i-1]中的记录已按关键字非递减的顺序有序排列，本算法实现
// 将 L.r[i]插入其中，并保持 L.r[1..i]中记录按关键字非递减顺序有序
L.r[0] = L.r[i]; // 复制为哨兵
for ( j=i-1; L.r[0].key < L.r[j].key; --j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0]; // 插入到正确位置
} // InsertPass
注意：“哨兵”的作用一趟插入排序第 21 页从 R[i-1]起向前进行顺序查找,监视哨设臵在 R[0]；
R[0] = R[i]; // 设臵“哨兵”
循环结束表明 R[i]的插入位臵为 j +1
R[0]
j
R[i]
for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找插入位臵第 22 页对于在查找过程中找到的那些关键字不小于 R[i].key的记录，
并在查找的同时实现记录向后移动；
for (j=i-1; R[0].key<R[j].key; --j);
R[j+1] = R[j]
R[0]
j
R[i]
j= i-1
上述循环结束后可以直接进行“插入”
插入位臵第 23 页例 2,关键字序列 T= （ 21,25,49,25*,16,08），
请写出直接插入排序的具体实现过程。 *表示后一个 25
i=1
21 25 49 25* 16 08
0 1 2 3 4 5 6
暂存
i=2 i=3 i=5i=4 i=6
254925* 4916 25*08 49
解,假设该序列已存入一维数组 V[7]中，将 V[0]作为缓冲或暂存单元（ Temp）。则程序执行过程为：
21 25 49初态,16 25*25211608
完成 !
时间效率,O(n2)—— 因为在最坏情况下，所有元素的比较次数总和为
（ 0＋ 1＋ … ＋ n-1)→O(n 2)。其他情况下还要加上移动元素的次数。
空间效率,O(1)—— 因为仅占用 1个缓冲单元算法的稳定性：稳定 —— 因为 25*排序后仍然在 25的后面。
第 24 页
【 算法 3.4 】
void InsertSort ( SqList &L)
{
for ( i=2; i<=L.length; ++i ) // 对顺序表 L作插入排序
if ( L.r[i].key < L.r[i-1].key )
{ // "<"时，才需将 L.r[i]插入有序子表
L.r[0] = L.r[i]; // 复制为哨兵
for ( j=i-1; L.r[0].key < L.r[j].key; --j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0]; // 插入到正确位置
} // if
} // InsertSort
整个插入排序需要进行 n-1趟“插入”。
因为只含有一个关键字的序列必定是有序序列，因此，插入应该从 i=1开始进行，此外，若第 i个记录的关键字不小于第 i-1个关键字，插入也就不需要进行了。
第 25 页
49 38 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
初始时，有序子表中只有一个元素待排序记录集合：
38 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
i=2
i=3
i=4
65 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
97 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
第 26 页
38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
L.r[0].key < L.r[4].key，
L.r[4]记录后移看一下外层 For循环 i=5 时算法的执行的情况
L.r[5]复制为哨兵
76 38 49 65 97 76 13 27 49
0 1 2 3 4 5 6 7 8 9
76 38 49 65 97 97 13 27 49
0 1 2 3 4 5 6 7 8 9
76 38 49 65 97 97 13 27 49
0 1 2 3 4 5 6 7 8 9
L.r[0].key?L.r[3].key
找到插入位置
76 38 49 65 97 97 13 27 49
0 1 2 3 4 5 6 7 8 9
L.r[5]为待插入元素插入！ 76
第 27 页时间复杂度：
待排序列正向有序时,0 （ n）
待排序列逆向有序时,0（ n2）
一般待排序列,0（ n2）
插入排序特点：
1) 算法简单
2) 时间复杂度为 O（ n2 ）
3） 初始序列基本（正向）有序时，时间复杂度为 O（ n）
4） 稳定排序该方法适用于记录基本（正向）有序或 n较少的情况第 28 页性能分析：
基本操作,比较元素：比较、移动元素次数均取决于插入位置移动元素
①处理第 i个记录时待排序列递增（正向）有序时，比较元素次数最少,1次待排序列递减（逆向）有序时，比较元素次数最多,i 次一般待排序列，平均比较元素次数,(i+1)/2
② 对 n个记录待排序列,直接插入排序待排序列正向有序时，比较元素次数最少,n-1次待排序列逆向有序时，比较元素次数最多,(n+2)(n-1)/2次一般待排序列，平均比较元素次数大约为,n2/4
类似可分析移动元素次数第 29 页
3.2.2 起泡排序基本思想：
是通过对无序序列区中的记录进行相邻记录关键字的
“比较”和记录位置的“交换”实现较小的记录向“一头”漂移，
而关键字较大的记录向“另一头”下沉，从而达到记录按关键字非递减有序排列的目标。
第 30 页假设在排序过程中，记录序列 R[1..n]的状态为：
第 i 趟起泡排序无序序列 R[1..n-i+1] 有序序列 R[n-i+2..n]
n-i+1
无序序列 R[1..n-i] 有序序列 R[n-i+1..n]
比较相邻记录，将 关键字最大的记录 交换 到 n-i+1 的位臵上第 31 页
1) 冒泡排序基本思路,每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。
优点,每趟结束时，不仅能挤出一个最大值到最后面位臵，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。
前提,顺序存储结构例,关键字序列 T=(21,25,49,25*,16,08），请写出冒泡排序的具体实现过程。
21,25,49,25*,16,08
21,25,25*,16,08,49
21,25,16,08,25*,49
21,16,08,25,25*,49
16,08,21,25,25*,49
08,16,21,25,25*,49
初态：
第 1趟第 2趟第 3趟第 4趟第 5趟第 32 页
【 具体算法 3.5 】
void BubbleSort( SqList &L )
{
// 对顺序表 L作起泡排序,
RcdType W；
i = L.length;
while (i >1) { // i>1 表明上一趟曾进行过记录的交换
lastExchangeIndex = 1;
for (j = 1; j < i; j++)
{
if (L.r[j+1].key < L.r[j].key) {
W=L.r[j]； L.r[j] =L.r[j+1]； L.r[j+1] = W； // 互换记录
lastExchangeIndex = j;
} //if
} //for
i = lastExchangeIndex; // 一趟排序中无序序列中最后一个记录的位置
} // while
} // BubbleSort
空间复杂度 O(1)
第 33 页注意,
2,一般情况下，每经过一趟“起泡”，,i 减一”，但并不是每趟都如此。
例如,
i=7
for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …
1,起泡排序的结束条件为，
最后一趟没有进行“交换记录”。
5 2 3 1 9 7 8
2 3 1 5 7 8 9
i=6i=2
1 3
第 34 页时间分析,
最好 的情况（关键字在记录序列中顺序有序）：
只需进行一趟起泡
“比较”的次数：
最坏 的情况（关键字在记录序列中逆序有序）：
需进行 n-1趟起泡
“比较”的次数：
0
“移动”的次数：
“移动”的次数：
n-1
2
)1()1(2
nni
ni 2
)1(3)1(3 2
nni
ni
第 35 页
3.3 先进的排序方法
3.3.1 快速排序 (quick sort)
快速排序是从起泡排序改进而得的一种“交换”排序方法，
它的基本思想是通过一趟排序将将记录分割成相邻的两个区域，
其中一个区域中记录的关键字均比另一区域中记录关键字小（区域内不一定有序），则可分别对这两个区域的记录进行再排序，
以达到整个序列有序。
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。
致使一趟排序之后，记录的无序序列 R[s..t]将分割成两部分,R[s..i-1]和 R[i+1..t],
且
R[j].key≤ R[i].key ≤ R[j].key
(s≤j≤i-1) 枢轴 (i+1≤j≤t)
第 36 页基本步骤：
为简洁起见，对待排记录仍只写出其关键字序列
1,(一趟快速排序）设被指定的关键字为待排序列的第一个关键字 k,i指向待排序列的的第一个关键字； j指向最后一个关键字；
若 i < j 循环：
1）从后向前将关键字与 k比较，直至遇到小于 k的 关键字 k’,k’ 前移；
2） 从前向后将关键字与 k比较，直至遇到大于 k的 关键字 k’’,k’’后移；
（一趟快速排序后,,小,记录被移至 k 前,,大,的记录被移至 k 后
2,继续对 k前后两部分关键字进行快速排序，直至排序范围为 1;
第 37 页
27 38 65 97 76 13 27 49
i i
27 38 65 97 76 13 65 49
j j
27 38 13 49 76 97 65 49
j ji
被指定的关键字 从后向前，将关键字与 49比较，
直至遇到小于 49
的关键字，前移从后向前，将关键字与 49比较，
直至遇到小于 49
的关键字，前移从前向后，将关键字与 49比较，
直至遇到大于 49
的关键字，后移从前向后，将关键字与 49比较，
直至遇到大于 49
的关键字，后移
27 38 13 97 76 13 65 49
i i
从后向前，将关键字与 49比较，
直至遇到 i=j,将
49放至 i处
49
一趟 快速 排序结束例 待排记录 49 38 65 97 76 13 27 49
jj
第 38 页
[27 38 13] 49 [76 97 65 49]
[13 27 38] 49 [49 65 76 97]
[13] 27 [38] 49 [49 65] 76 [97]
13 27 38 49 49 65 76 97
两趟 快速 排序结束三趟 快速 排序结束快速 排序结束第 39 页
【 算法 3.7 】
void QSort (RedType R[],int s,int t )
{
// 对记录序列 R[s..t]进行快速排序
if (s < t)
{ // 长度大于 1
pivotloc = Partition(R,s,t);// 对 R[s..t] 进行一次划分，并返回枢轴位置
QSort(R,s,pivotloc-1); // 对低子序列递归排序
QSort(R,pivotloc+1,t); // 对高子序列递归排序
} // if
} // Qsort
int Partition (RedType R[],int s,int t )
{
key = R[s];
while ( s < t)
{
while (s < t && R[t] >= key ) t--;
R[s]R[t];
while (s < t && R[s] <= key) s++;
R[s]R[t];
}
return s;
}
【 算法 3.8 】
void QuickSort( SqList & L) {
// 对顺序表 L 进行快速排序
QSort(L.r,1,L.length);
} // QuickSort
第 40 页快速排序的时间分析：
假设 一次划分所得枢轴位臵 i=k,则对 n 个记录进行快排所需时间其中 Tpass(n)为对 n 个记录进行一次划分所需时间，
若待排序列中记录的关键字是随机分布的，则 k 取 1
至 n 中任意一值的可能性相同。
T(n) = Tpass(n) + T(k-1) + T(n-k)
第 41 页
1
1( ) ( 1 ) ( )n
a v g a v g a v g
k
T n Cn T k T n k
n?
设 Tavg(1)≤ b
则可得结果,
( ) ( 2 ) ( 1 ) l n ( 1 )2a v g bT n c n n
结论,快速排序的时间复杂度为 O(nlogn),快速排序是目前被认为同数量级中最快的内部排序算法。
由此可得快速排序所需时间的平均值为：
第 42 页若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序,其时间复杂度为 O(n2)。
为避免出现这种情况，需在进行一次划分之前，进行
“予处理”，即：
先对 R(s).key,R(t).key 和 R[?(s+t)/2?.key,进行相互比较，然后取关键字为,三者之中,的记录为枢轴记录。
第 43 页归并排序的基本思想是,将两个（或以上）的有序表组成新的有序表。
更实际的意义,可以把一个长度为 n 的无序序列看成是 n 个长度为 1 的有序子序列,首先做两两归并，得到?n / 2? 个长度为 2
的子序列 ；再做两两归并,…,如此重复，直到最后得到一个长度为 n 的有序序列。
例,关键字序列 T= （ 21,25,49,25*,93,62,72，
08,37,16,54），请给出归并排序的具体实现过程。
3.3.2 归并排序第 44 页
21 25 25* 93 62 72 08 37 16 5449
21 25 25* 49 62 93 08 72 16 37 54
16 37 54
21 25 25* 49 08 62 72 93
08 21 25 25* 49 62 72 93
08 16 21 25 25* 37 49 54 62 72 93
len=1
len=2
len=4
len=8
len=16
16 37 54
整个归并排序仅需?log2n?趟第 45 页
Void Merge (RcdType SR[ ],RcdType TR[ ],int i,int m,int n)
{
// 将有序的 SR[i…m] 和 SR[m+1…n] 归并为有序的 TR[i…n]
for(k=i,j=m+1; i<=m && j<=n; ++k )
{
if ( SR[i].key <= SR[j].key ) TR[k] = SR[i++];
else TR[k] = SR[j++]; // 将 SR中记录由小到大地并入 TR
}
if (i <= m) TR[k++] = SR[i++]; // 将剩余的 SR[i…m] 复制到 TR
if (j <= n) TR[k++] = SR[j++]; // 将剩余的 SR[j…n] 复制到 TR
} // Merge
一趟归并排序算法,(两路有序并为一路 ) 参见教材 P53
第 46 页
【 算法 3.11 】
void MergeSort (SqList &L) {
// 对顺序表 L作归并排序
MSort(L.r,L.r,1,L.length);
} // MergeSort
【 算法 3.10 】
void Msort ( RcdType SR[],RcdType TR1[],int s,int t ) {
// 对 SR[s..t]进行归并排序，排序后的记录存入 TR1[s..t]。
RcdType TR2[t-s+1]; //开设用于存放归并排序中间结果的辅助空间
if (s==t) TR1[s] = SR[s];
else {
m = (s+t)/2; // 将 SR[s..t]平分为 SR[s..m]和 SR[m+1..t]
Msort (SR,TR2,s,m); // 递归地将 SR[s..m]归并为有序的 TR2[s..m]
Msort (SR,TR2,m+1,t); // 递归地将 SR[m+1..t]归并为有序的 TR2[m+1..t]
Merge (TR2,TR1,s,m,t); // 将 TR2[s..m]和 TR2[m+1..t]归并到 TR1[s..t]
} // else
} // MSort
第 47 页归并排序算法分析：
时间效率,O(nlog2n)
因为在递归的归并排序算法中,函数 Merge( )做一趟两路归并排序,
需要调用 merge ( )函数?n/(2*len) O(n/len) 次,函数 Merge( )调用 Merge( )正好?log2n? 次,而每次 merge( )要执行比较 O(len)次,
所以算法总的时间复杂度为 O(nlog2n)。
空间效率,O(n)
因为需要一个与原始序列同样大小的辅助序列 （ TR） 。 这正是此算法的缺点 。
稳定性,稳定第 48 页
3.3.3 堆排序（ Heap Sort)）
堆的定义,
堆是满足下列性质的数列 {r1,r2,…,rn}：
2
21
ii
ii
rr
rr?
2
21
ii
ii
rr
rr?
(小顶堆 ) (大顶堆 )
堆排序 是利用堆的特性对记录序列进行排序的一种排序方法，是对 选择排序 的一种改进。
第 49 页
{12,36,27,65,40,34,98,81,73,55,49}
例如,
{12,36,27,65,40,14,98,81,73,55,49}
解释,如果让满足以上条件的元素序列 （ k1,k2,…,kn）
顺次排成一棵 完全二叉树,则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。
第 50 页
08
25
46
49
58 67
2 3
4 5 6
1
（大顶堆）
91
85
66
76
58 67
2 3
4 5 6
1
55
7
√ （小顶堆） √
（小根堆）
（最小堆）
（大根堆）
（最大堆）
例,有序列 T1=（ 08,25,49,46,58,67） 和序列 T2=（ 91,85,76,66,
58,67,55）,判断它们是否,堆”？
第 51 页
0 1 2 3 4 5 6
40 55 73 12 40 27
初始数据
H.r[1..6]
0 1 2 3 4 5 6
27 55 73 12 40 98
互换 H.r[1]和
H.r[6]
0 1 2 3 4 5 6
98 55 73 12 40 27
初建大顶堆第 52 页
0 1 2 3 4 5 6
73 55 27 12 40 98
重新将 H.r[1..5]
调整为大顶堆
0 1 2 3 4 5 6
40 55 27 12 73 98
互换 H.r[1]和
H.r[5]
0 1 2 3 4 5 6
12 40 27 55 73 98
重新将 H.r[1..4]
调整为大顶堆第 53 页
0 1 2 3 4 5 6
12 40 27 55 73 98
互换 H.r[1]和
H.r[4]
0 1 2 3 4 5 6
40 12 27 55 73 98
重新将 H.r[1..3]
调整为大顶堆
0 1 2 3 4 5 6
27 12 40 55 73 98
互换 H.r[1]和
H.r[3]
第 54 页
0 1 2 3 4 5 6
27 12 40 55 73 98
重新将 H.r[1..2]
调整为大顶堆
0 1 2 3 4 5 6
12 27 40 55 73 98
互换 H.r[1]和
H.r[2]
至此，堆排序结束,H.r[1..6]为有序序列。
第 55 页
3.4 基数排序基数排序（ Radix Sort）,
是一种借助,多关键字排序”的思想 来实现,单关键字排序,
的内部排序算法（ 即：用关键字 不同的位值 进行排序。 ）。
要讨论的问题：
1,什么是,多关键字,排序？ 实现方法？
2,单逻辑关键字怎样,按位值,排序？
多关键字排序的实现方法通常有两种：
1）最高位优先法 MSD (Most Significant Digit first)
2）最低位优先法 LSD (Least Significant Digit first)
第 56 页
以扑克牌排序为例 。 每张扑克牌有两个,排序码,,花色和面值 。 其有序关系为：
花色,
面值,2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
如果我们把所有扑克牌排成以下次序：
2,…,? A,? 2,…,? A,? 2,…,? A,
2,…,? A
这就是多关键字排序。
第 57 页例,对一副扑克牌该如何排序？
答,若规定 花色为第一 关键字（高位）,面值为第二 关键字（低位），则使用 MSD和 LSD方法都可以达到排序目的。
MSD方法的思路,先设立 4个花色“箱”，将全部牌按花色分别归入 4个箱内（每个箱中有 13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。
LSD方法的思路,先按面值分成 13堆（每堆 4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。
想一想：用哪种方法更快些？
第 58 页
2,单逻辑 关键字怎样,按位值,排序？
思路,设 n 个记录的序列为,{V0,V1,…,Vn-1 },可以把每个记录 Vi 的 单关键码 Ki 看成是一个 d元组（ Ki1,Ki2,…,Kid）,则其中的每一个分量 Kij ( 1?
j? d ) 也可看成是一个关键字。
注 1,Ki1＝ 最高位关键字,Kid＝ 最低位关键字； Ki共有 d位,可看成 d元组；
注 2,每个分量 Kij (1? j? d ) 有 radix种取值,则称 radix为 基数 。
(9,8,4) (0,1,…,9)
（ a,b,…,z ）(d,i,a,n)
例 1,关键码 984可以看成是 3 元组；基数 radix 为 10 。
例 2,关键码 dian可以看成是 4 元组；基数 radix 为 26 。
第 59 页
0 1 2 3 4 5 6 7 8 9 10 11
78 09 63 30 74 89 94 25 05 69 18 83
初始状态
0 1 2 3 4 5 6 7 8 9
30 63
83
74
94
25
05
78
18
09
89
69
0 1 2 3 4 5 6 7 8 9 10 11
30 63 83 74 94 25 05 78 18 09 89 69
第一趟,分配,之后的结果第一趟,收集,之后的结果采用,分配,与,收集,的方法实现基数排序。
第 60 页
0 1 2 3 4 5 6 7 8 9
05
09
18 25 30 63
69
74
78
83
89
94
0 1 2 3 4 5 6 7 8 9 10 11
05 09 18 25 30 63 69 74 78 83 89 94
第二趟,分配,之后的结果第二趟,收集,之后的结果第 61 页对由顺序表表示法存储的记录进行基数排序可利用“计数”和
“复制”的操作实现。
0 1 2 3 4 5 6 7 8 9 10 11
78 09 63 30 74 89 94 25 05 69 18 83
记录数组 A
0 1 2 3 4 5 6 7 8 9
1 0 0 2 2 2 0 0 2 3
记数数组 count
(个位情况 )
0 1 2 3 4 5 6 7 8 9
1 1 1 3 5 7 7 7 9 12
累加结果
count
（ a） 初始状态和对“个位数”计数的结果第 62 页
0 1 2 3 4 5 6 7 8 9
1 1 1 3 5 7 7 7 9 12
累加结果
count
0 1 2 3 4 5 6 7 8 9 10 11
30 63 83 74 94 25 05 78 18 09 89 69
记录数组 B
0 1 2 3 4 5 6 7 8 9
2 1 1 1 0 0 2 2 2 1
记数数组 count
(十位情况 )
（ b） 计数器的累加结果和记录“复制”后的状态第 63 页
0 1 2 3 4 5 6 7 8 9
2 1 1 1 0 0 2 2 2 1
记数数组 count
(十位情况 )
0 1 2 3 4 5 6 7 8 9
2 3 4 5 5 5 7 9 11 12
累加结果
count
0 1 2 3 4 5 6 7 8 9 10 11
05 09 18 25 30 63 69 74 78 83 89 94
记录数组 A
（ c） 对“十位数”计数和“复制”和记录“复制”
后的状态第 64 页
【 算法 3.12 】
void RadixSort( SqList &L )
{
// 对顺序表 L 进行基数排序
RcdType C[L.length]; //开设同等大小的辅助空间用于复制数据
i= bitsnum-1;
while ( i >= 0 ) {
RadixPass( L.r,C,L.length,i ); // 对 L.r进行一趟基数排序，排序结果存入 C
i--;
if (i >=0 ) {
RadixPass( C,L.r,L.length,i ); // 对 C进行一趟基数排序，排序结果存入 L.r
i--;
}
else
for ( j=0; j<l.length; ++j ) L.r[j] = C[j]; // 排序后的结果在 C中，复制至 L.r中
}// while
}// RadixSort
第 65 页
【 算法 3.13 】
void RadixPass( RcdType A[],RcdType B[],int n,int i ) {
// 对数组 A中记录关键字的 "第 i位 "计数，并按计数数组 count的值
// 将数组 A中记录复制到数组 B中
for ( j=0; j<RADIX; ++j ) count[j] = 0; // 计数数组初始化为 0
for ( k=0; k<n; ++k ) count[ A[k].keys[i] ] ++; // 对关键字的对第 i位 "计数 "
for ( j=1; j<RADIX; ++j ) count[j] = count[j-1] + count[j]; // 累加操作
for ( k=n-1; k>=0; --k ) // 从右端开始复制记录
{
j = A[k].keys[i];
B[ count[j]-1 ] = A[k];
count[j]--;
}// for
}// RadixPass
时间复杂度,O(d× n)(d趟基数排序，每趟对 n个记录进行“计数”和“复制” )
空间复杂度,O(n)
第 66 页因为有分组，故此算法需递归实现。
思考：是借用 MSD方式来排序呢，还是借用 LSD方式？
方法 1（ MSD）,原始序列,32,13,27,32*,19,33
先按高位 Ki1 排序,（ 13,19）,27,（ 32,32*,33）
再按低位 Ki2 排序,13,19,27,32,32*,33
方法 2（ LSD）,原始序列,32,13,27,32*,19,33
先按低位 Ki2排序,32,32*,13,33,27,19
再按高位 Ki1排序,13,19,27,32,32*,33
无需分组，易编程实现！
例：初始关键字序列 T=（ 32,13,27,32*,19,33）,请分别用 MSD和 LSD
进行排序，并讨论其优缺点。
第 67 页
3.5 各种排序方法的比较第 68 页一、时间性能
1,平均的时间性能时间复杂度为 O(nlogn),快速排序、堆排序和归并排序时间复杂度为 O(n2),直接插入排序、起泡排序和简单选择排序时间复杂度为 O(n),基数排序2,当待排记录序列按关键字顺序有序时直接插入排序和起泡排序能达到 O(n)的时间复杂度 ;
快速排序的时间性能蜕化为 O(n2)
3,简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
第 69 页二、空间性能空间性能指的是排序过程中所需的辅助空间大小
1,所有的简单排序方法 (包括：直接插入、起泡和简单选择 ) 和堆排序的空间复杂度为 O(1)；
2,快速排序为 O(logn),为递归程序执行过程中，栈所需的辅助空间 ;
3,归并排序和基数排序所需辅助空间最多，其空间复杂度为 O(n);
第 70 页三、排序方法的稳定性能
1,稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位臵，在排序之前和经过排序之后，没有改变。
2,除快速排序、堆排序和希尔排序是不稳定的排序方法之外，本章讨论的其它排序方法都是稳定的排序方法。
3,对于不稳定的排序方法，只要能举出一个实例说明即可。
例如,对 { 4,3,4,2 } 进行快速排序，得到 { 2,3,4,4 }
第 71 页四、关于“排序方法的时间复杂度的下限”
本章讨论的各种排序方法，除基数排序外，其它方法都是基于
“比较关键字”进行排序的排序方法。可以证明,这类排序法可能达到的最快的时间复杂度为 O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制 )
第 72 页作业：
3.3 3.6 3.9 3.11
