1
概述
插入排序
交换排序
选择排序
归并排序
外排序
2
概述
排序,将一组杂乱无章的数据按一定的规律顺次排列起来 。
数据表 (datalist),它是待排序数据对象的有限集合 。
排序码 (key),通常数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据 。 该域即为 排序码 。 每个数据表用哪个属性域作为排序码,
要视具体的应用需要而定 。
3
排序算法的稳定性,如果在对象序列中有两个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],且在排序之前,对象 r[i]排在 r[j]前面。如果在排序之后,对象 r[i]仍在对象 r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。
内排序与外排序,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
4
排序的时间开销,排序的时间开销是衡量算法好坏的最重要的标志。 排序的时间开销可用算法执行中的 数据比较次数 与 数据移动次数 来衡量 。
算法运行时间代价的大略估算一般都 按平均情况 进行估算。对于那些 受对象排序码序列初始排列及对象个数影响较大的,需要 按最好情况 和 最坏情况 进行估算 。
算法执行时所需的附加存储,评价算法好坏的另一标准。
5
插入排序 (Insert Sorting)
基本思想是,当插入第 i (i? 1) 个对象时,前面的 V[0],V[1],…,V[i-1]已经排好序。这时,
用 V[i]的排序码与 V[i-1],V[i-2],… 的排序码顺序进行比较,找到插入位置即将 V[i]插入,
原来位置上的对象向后顺移。
基本方法是,每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止 。
直接插入排序 (Insert Sort)
6
各趟排序结果
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
7
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
8
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
9
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
10
直接插入排序的算法
typedef int SortData;
void InsertSort ( SortData V[ ],int n ) {
//按非递减顺序对表进行排序
SortData temp; int i,j;
for ( i = 1; i < n; i++ ) {
temp = V[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < V[j-1] ) V[j] = V[j-1];
else break;
V[j] = temp;
}
}
11
算法分析
设待排序对象个数为 n,则该算法的主程序执行 n-1趟。
排序码比较次数和对象移动次数与对象排序码的初始排列有关。
最好情况下,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较 1次,移动 2次对象,总的排序 码比较次数为 n-1,对象移动次数为 2(n-1)。
12
最坏情况下,第 i 趟时第 i 个对象必须与前面 i 个对象都做排序码比较,并且每做 1次比较就要做 1次数据移动 。 则总 排序码比较次数 KCN和 对象移动次数 RMN分别为
在平均情况下的 排序码比较次数 和 对象移动次数 约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。
直接插入排序是一种 稳定 的排序方法。
1
1
1
1
22142
221
n
i
n
i
nnniR M N
nnniKCN
//))(()(
,//)(
2
2
13
希尔排序 (Shell Sort)
希尔排序方法又称为缩小增量排序。该方法的基本思想是,设待排序对象序列有 n 个对象,首先取一个整数 gap < n 作为间隔,将全部对象分为 gap 个子序列,所有 距离为 gap
的对象放在 同一个子序列 中,在每一个子序列中分别施行直接插入排序。然后缩小间隔
gap,例如取 gap =?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1,
将所有对象放在同一个序列中排序为止。
14
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
15
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
16
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
Gap = 1
2516 4925*
开始时 gap 的值较大,子序列中的对象较少,
排序速度较快 ; 随着排序进展,gap 值逐渐变小,子序列中对象个数逐渐变多,由于前面工作的基础,大多数对象已基本有序,所以排序速度仍然很快。
17
希尔排序的算法
typedef int SortData;
void ShellSort ( SortData V[ ],int n ) {
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( int j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
18
V[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
Gap的取法有多种。最初 shell 提出取 gap =
n/2?,gap =?gap/2?,直到 gap = 1。 knuth
提出取 gap =?gap/3?+1。
对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数 。
19
想要弄清排序码比较次数和对象移动次数与增量选择之间的依赖关系,并给出完整的数学分析,还没有人能够做到 。
Knuth利用大量实验统计资料得出,当 n
很大时,排序码平均比较次数和对象平均移动次数大约在 n1.25到 1.6n1.25的范围内 。
这是在利用直接插入排序作为子序列排序方法的情况下得到的 。
20
交换排序 ( Exchange Sort )
基本方法：设待排序对象序列中的对象个数为 n。最多作 n-1 趟,i = 1,2,?,n-1。
在第 i 趟中 从后向前,j = n-1,n-2,?,i，
顺次两两 比较 V[j-1]和 V[j]。 如果发生逆序，
则交换 V[j-1]和 V[j]。
基本思想是 两两比较待排序对象的排序码,
如发生逆序 (即排列顺序与排序后的次序正好相反 )，则交换之 。直到所有对象都排好序为止。
冒泡排序 (Bubble Sort)
21
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
2516
25 16
08
49
Exchang=108
25*4921
Exchang=1
i = 2
i = 3
08 16 Exchang=125*2521
22
25*
0 1 2 3 4 5
i = 4 4916
Exchang=008
2521
冒泡排序的算法
typedef int SortData;
void BubbleSort ( SortData V[ ],int n ) {
int i = 1; int exchange = 1;
while ( i < n && exchange ){
exchange = 0; //标志置为 0,假定未交换
for ( int j = n-1; j >= i; j-- )
if ( V[j-1] > V[j] ) { //逆序
23
Swap ( V[j-1],V[j] );,//交换
exchange = 1; //标志置为 1,有交换
}
i++;
}
}
第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-1]
进行排序,结果 将该序列中排序码最小的对象交换到序列的第一个位置 (i-1),其它对象也都向排序的最终位置移动 。 在个别情形,
对象可能在排序中途向相反的方向移动 。
24
最多做 n-1趟冒泡 就能把所有对象排好序 。
在对象的 初始排列已经按排序码从小到大排好序 时,此算法 只执行一趟冒泡,做 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
nninK C N
)()(
)()(
25
快速排序 (Quick Sort)
基本思想是任取 待排序对象序列中的某个对象
(例如取第一个对象 ) 作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列,
冒泡排序需要一个附加对象以实现对象值的对换。
冒泡排序是一个 稳定 的排序方法。
26
左侧子序列中所有对象的排序码都小于或等于基准对象的排序码
右侧子序列中所有对象的排序码都大于基准对象的排序码
基准对象则排在这两个子序列中间 (这也是该对象最终应安放的位置 )。
然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。
27
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
算法描述
28
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25*16
2516
08
49
pivot
08
25 4921i = 2
i = 3
08 16 2525*21
pivotpivot
pivot
29
21 25 49 25* 16 08
0 1 2 3 4 5
25*
i = 1
划分
2516
2516
08
49
pivotpos
08
25* 49
08 16 25* 2521
pivotpos
21
比较 4次交换 25,16
i
i
pivotpos
21
比较 1次交换 49,08
49
low pivotpos
交换 21,08
30
最大递归调用层次数与递归树的高度一致,
理想情况为?log2(n+1)? 。 因此,要求存储开销为 O(log2n)。
在最坏的情况,即 待排序对象序列已经按其排序码从小到大排好序 的情况下,其 递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列 。 总的排序码比较次数将达
快速排序是一种 不稳定 的排序方法 。
212
1 21
1
nnninn
i
)()(
31
用第一个对象作为基准对象快速排序退化的例子
08 16 21 25 25* 49 08
0 1 2 3 4 5 pivot
初始
16 21 25 25* 4908 16
21 25 25* 49 2108 16
2525 25* 4908 16 21
25* 49 25*08 16 21 25
4908 16 21 25 25*
i = 1
i = 2
i = 3
i = 4
i = 5
32用居中排序码对象作为基准对象
08 16 21 25 25* 49
0 1 2 3 4 5 pivot
21初始
08 16 21 25 25* 49 08 25*
08 16 21 25 25* 49
i = 1
i = 2
其 排序速度退化到简单排序的水平,比直接插入排序还慢 。占用附加存储 (栈 )将达到 O(n)。
改进办法,取每个待排序对象序列的 第一个对象,最后一个对象 和 位置接近正中的 3 个对象，取其排序码居中者作为基准对象。
33
基本思想是,每一趟 (例如第 i 趟,i = 0,1,…,
n-2) 在后面 n-i 个待排序对象中选出排序码最小的对象,作为有序对象序列的第 i 个对象。
待到第 n-2 趟作完,待排序对象只剩下 1个,就不用再选了。
选择排序
34
② 若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码的对象 。 在剩下的对象 V[i+1]～ V[n-1]中重复执行第 ①,② 步,直到剩余对象只有一个为止 。
直接选择排序是一种简单的排序方法,它的基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最小排序码的对象；
直接选择排序 (Select Sort)
35
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 0
49
25 16
25 16
08
49
08
25*49 21i = 1
i = 2
08 16
25* 25 21
初始最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
36
4925*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3
08 16 2521
最小者 25*
无交换最小者 25
无交换252116
08
各趟排序后的结果
37
直接选择排序的算法
typedef int SortData;
void SelectSort ( SortData V[ ],int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( V[i],V[k] );
}
}
38
0 1 2 3 4 5
49
1608 25*49 21
08 25*
25
21
i =1时选择排序的过程
i k j
4925
08 25* 16 21
i k j
49? 25
25*? 25
1625
i k j 16 < 25
39
4925
08 25* 16 21
0 1 2 3 4 5
i k j 21? 16
k 指示当前序列中最小者
直接选择排序的 排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象,则第 i 趟选择具有最小排序码对象所需的比较次数 总是 n-i-1次 。总的排序码比较次数为
2
0 2
11n
i
nninKCN )()(
40
对象的移动次数与对象序列的初始排列有关 。当这组对象的初始状态是按其排序码从小到大有序的时候,对象的移动次数
RMN = 0，达到最少。
最坏情况是每一趟都要进行交换,总的对象移动次数 为 RMN = 3(n-1)。
直接选择排序是一种 不稳定 的排序方法。
41
利用堆及其运算,可以很容易地实现选择排序的思路。
堆排序分为两个步骤
根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
通过一系列的对象交换和重新调整堆进行排序。
堆排序 (Heap Sort)
42
建立初始的最大堆
21
25
25*
49
16 08
0
1 2
3 4 5
i 21
25
25* 16
49
08
0
2
543
1
i
21 25 49 25* 16 08
初始排序码集合
21 25 49 25* 16 08
i = 2 时的局部调整
43
21
25
25*
49
16 08
0
1 2
3 4 5
i
49
25
25* 16
21
08
0
2
543
1
21 25 49 25* 16 08 49 25 21 25* 16 08
i = 0 时的局部调整形成最大堆
i = 1 时的局部调整
44
基于初始堆进行堆排序
最大堆堆顶 V[0]具有最大的排序码,将 V[0]与
V[n-1]对调,把具有最大排序码的对象交换到最后,再对前面的 n-1个对象,使用堆的调整算法 FilterDown(0,n-2),重新建立最大堆,
具有次最大排序码的对象又上浮到 V[0]位置。
再 对调 V[0]和 V[n-2],调用 FilterDown(0,n-3),
对前 n-2个对象重新调整,… 。
如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，其细节在下面的程序中给出。
45
49
25
25*
21
16 08
0
1 2
3 4 5
08
25
25* 16
21
49
0
2
543
1
49 25 21 25* 16 08 08 25 21 25* 16 49
交换 0 号与 5 号对象,
5 号对象就位初始最大堆
46
25
25*
08
21
16 49
0
1 2
3 4 5
16
25*
08 25
21
49
0
2
543
1
25 25* 21 08 16 49 16 25* 21 08 25 49
交换 0 号与 4 号对象,
4 号对象就位从 0 号到 4 号 重新调整为最大堆
47
25*
16
08
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
25* 16 21 08 25 49 08 16 21 25* 25 49
交换 0 号与 3 号对象,
3 号对象就位从 0 号到 3 号 重新调整为最大堆
48
21
16
25*
08
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
21 16 08 25* 25 49 08 16 21 25* 25 49
交换 0 号与 2 号对象,
2 号对象就位从 0 号到 2 号 重新调整为最大堆
49
16
08
25*
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
16 08 21 25* 25 49 08 16 21 25* 25 49
交换 0 号与 1 号对象,
1 号对象就位从 0 号到 1 号 重新调整为最大堆
50
堆排序的时间复杂性为 O(nlog2n)。
空间复杂性为 O(1)。
堆排序是一个 不稳定 的排序方法 。
51
归并排序 (Merge Sort)
归并，是将两个或两个以上的有序表合并成一个新的有序表。
原始序列 initList[ ]中两个有序表
initList[l] … initList[ m]和 initList[m+1] …
initList[n]。它们可归并成一个有序表,存于另一对象序列 mergedList的 l … n 中。
这种归并方法称为 两路归并 (2-way merging)。
设变量 i 和 j 是表 initList[l … m]和 initList
[m+1… n]的当前检测指针。 k是存放指针。
52
08 21 25 25* 49 62 72 93 16 37 54
left mid mid+1 right
initList
i j
08 16 21 25 25* 37 49 54 62 72 93
left right
k
mergeList
当 i 和 j 都在两个表的表长内变化时,根据对应项的排序码的大小,依次把排序码小的对象排放到新表 k 所指位置 中；
当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。
53
迭代的归并排序算法
迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：
假设初始对象序列有 n 个对象,首先把它看成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到?n / 2? 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为 1)；再做两两归并,…,如此重复,最后得到一个长度为 n 的有序序列 。
54
两路归并算法
typedef int SortData;
void merge ( SortData InitList[ ],
SortData mergedList[ ],
int left,int mid,int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = InitList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++; }
55
while ( i <= mid )
{ mergedList[k] = InitList[i]; i++; k++; }
while ( j <= right )
{ mergedList[k] = InitList[j]; j++; k++; }
}
56
迭代的归并排序算法
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
57
(两路 )归并排序的主算法
void MergeSort ( SortData initList[ ],int n ) {
//按对象排序码非递减的顺序对表中对象排序
SortData tempList[n];
int len = 1;
while ( len < n ) {
MergePass ( initList,tempList,len );
len *= 2;
MergePass ( tempList,initList,len );
len *= 2;
}
}
58
时间复杂度为 O(nlog2n)。
归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组 。 这是这个算法的缺点 。
归并排序是一个 稳定 的排序方法 。
59
基数排序（ Radix Sort）
一、基数排序：按组成关键字的各数位的值进行排序。
60
二,将关键字 Ki看成一个 d元组，即
Ki,Ki,…,K i，其中 0≤Ki≤r，
i=1~n,j=1~d,r为基数,d为关键字的位数 （为最长关键字的长度，不足 d位长的关键字前补零） 。
Ki----最高有效位 MSD
Ki----最低有效位 LSD
排序开始的位置
1 2 d
1
d
j
61
三、基本思想：
设立 r个队列，首先按 Ki 的值，把 n个关键字分配到 r个队列中，然后从小到大将各个队列中的关键字依次收集起来；依此类推，重复进行分配和收集，直至最高有效位。
d
62
四、例：
986 321 432
987765
123
654 018
500
210 ^
head
63
500 210
321
432
123
654
765
986
987
018
NULL
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
r[0]
r[1]
r[2]
r[3]
r[4]
r[5]
r[6]
r[7]
r[8]
r[9]
第一趟分配
64
500 210 123
654 765 986
321
018 ^987
432head
第一趟收集
65
500
210
321
432
654
765
986
NULL
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
r[0]
r[1]
r[2]
r[3]
r[4]
r[5]
r[6]
r[7]
r[8]
r[9]
第二趟分配
018
123
NULL
NULL
987
66
500 210 123
432 654 765
018
987 ^986
321head
第二趟收集
67
018
123
210
321
432
500
654
765
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
r[0]
r[1]
r[2]
r[3]
r[4]
r[5]
r[6]
r[7]
r[8]
r[9]
第三趟分配
NULL
986 987
68
018 123 432
500 654 765
210
987 ^986
321head
第三趟收集
69
五、性能分析：
基数排序执行一次分配和收集的时间为
O(n+r)，若关键字位数为 d，则总时间为
O(d(n+r))；
辅助空间为 2r；
基数排序是稳定的。
70
各种内部排序方法的比较排序方法 平均时间 辅助空间 稳定性直接插入 O(n2) O(1) 稳定冒 泡 O(n2) O(1) 稳定直接选择 O(n2) O(1) 不稳定希 尔 O(n1.25) O(1) 不稳定快 速 O(nlog2n) O(log2n) 不稳定堆 O(nlog2n) O(1) 不稳定归 并 O(nlog2n) O(n) 稳定基 数 O(d(n+r)) 稳定
71
一、选择合适的排序方法应综合考虑：
待排序的记录数目 n；
记录的大小（规模）；
关键字的结构及其初始状态；
对稳定性的要求；
语言工具的选择；
存储结构；
时间和辅助空间复杂度等；
72
二、目前较为一致的结论：
若 n较小，可采用直接插入或直接选择排序；
若文件初始状态基本有序（正序），则应选择直接插入，冒泡排序；
当 n较大，应选择快速排序、归并排序、堆排序、希尔排序；
从存储容量来讲，归并排序，基数排序，快速排序（从大到小）。
概述
插入排序
交换排序
选择排序
归并排序
外排序
2
概述
排序,将一组杂乱无章的数据按一定的规律顺次排列起来 。
数据表 (datalist),它是待排序数据对象的有限集合 。
排序码 (key),通常数据对象有多个属性域,
即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据 。 该域即为 排序码 。 每个数据表用哪个属性域作为排序码,
要视具体的应用需要而定 。
3
排序算法的稳定性,如果在对象序列中有两个对象 r[i]和 r[j],它们的排序码 k[i] == k[j],且在排序之前,对象 r[i]排在 r[j]前面。如果在排序之后,对象 r[i]仍在对象 r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。
内排序与外排序,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
4
排序的时间开销,排序的时间开销是衡量算法好坏的最重要的标志。 排序的时间开销可用算法执行中的 数据比较次数 与 数据移动次数 来衡量 。
算法运行时间代价的大略估算一般都 按平均情况 进行估算。对于那些 受对象排序码序列初始排列及对象个数影响较大的,需要 按最好情况 和 最坏情况 进行估算 。
算法执行时所需的附加存储,评价算法好坏的另一标准。
5
插入排序 (Insert Sorting)
基本思想是,当插入第 i (i? 1) 个对象时,前面的 V[0],V[1],…,V[i-1]已经排好序。这时,
用 V[i]的排序码与 V[i-1],V[i-2],… 的排序码顺序进行比较,找到插入位置即将 V[i]插入,
原来位置上的对象向后顺移。
基本方法是,每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止 。
直接插入排序 (Insert Sort)
6
各趟排序结果
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
7
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
8
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
9
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
10
直接插入排序的算法
typedef int SortData;
void InsertSort ( SortData V[ ],int n ) {
//按非递减顺序对表进行排序
SortData temp; int i,j;
for ( i = 1; i < n; i++ ) {
temp = V[i];
for ( j = i; j > 0; j-- ) //从后向前顺序比较
if ( temp < V[j-1] ) V[j] = V[j-1];
else break;
V[j] = temp;
}
}
11
算法分析
设待排序对象个数为 n,则该算法的主程序执行 n-1趟。
排序码比较次数和对象移动次数与对象排序码的初始排列有关。
最好情况下,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较 1次,移动 2次对象,总的排序 码比较次数为 n-1,对象移动次数为 2(n-1)。
12
最坏情况下,第 i 趟时第 i 个对象必须与前面 i 个对象都做排序码比较,并且每做 1次比较就要做 1次数据移动 。 则总 排序码比较次数 KCN和 对象移动次数 RMN分别为
在平均情况下的 排序码比较次数 和 对象移动次数 约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。
直接插入排序是一种 稳定 的排序方法。
1
1
1
1
22142
221
n
i
n
i
nnniR M N
nnniKCN
//))(()(
,//)(
2
2
13
希尔排序 (Shell Sort)
希尔排序方法又称为缩小增量排序。该方法的基本思想是,设待排序对象序列有 n 个对象,首先取一个整数 gap < n 作为间隔,将全部对象分为 gap 个子序列,所有 距离为 gap
的对象放在 同一个子序列 中,在每一个子序列中分别施行直接插入排序。然后缩小间隔
gap,例如取 gap =?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1,
将所有对象放在同一个序列中排序为止。
14
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
15
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
16
21 25 4925*1608
0 1 2 3 4 5
21
i = 3
08
Gap = 1
2516 4925*
开始时 gap 的值较大,子序列中的对象较少,
排序速度较快 ; 随着排序进展,gap 值逐渐变小,子序列中对象个数逐渐变多,由于前面工作的基础,大多数对象已基本有序,所以排序速度仍然很快。
17
希尔排序的算法
typedef int SortData;
void ShellSort ( SortData V[ ],int n ) {
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到 gap为零
for ( int i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( int j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
18
V[j] = temp;
}
gap = ( int ) ( gap / 2 );
}
}
Gap的取法有多种。最初 shell 提出取 gap =
n/2?,gap =?gap/2?,直到 gap = 1。 knuth
提出取 gap =?gap/3?+1。
对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数 。
19
想要弄清排序码比较次数和对象移动次数与增量选择之间的依赖关系,并给出完整的数学分析,还没有人能够做到 。
Knuth利用大量实验统计资料得出,当 n
很大时,排序码平均比较次数和对象平均移动次数大约在 n1.25到 1.6n1.25的范围内 。
这是在利用直接插入排序作为子序列排序方法的情况下得到的 。
20
交换排序 ( Exchange Sort )
基本方法：设待排序对象序列中的对象个数为 n。最多作 n-1 趟,i = 1,2,?,n-1。
在第 i 趟中 从后向前,j = n-1,n-2,?,i，
顺次两两 比较 V[j-1]和 V[j]。 如果发生逆序，
则交换 V[j-1]和 V[j]。
基本思想是 两两比较待排序对象的排序码,
如发生逆序 (即排列顺序与排序后的次序正好相反 )，则交换之 。直到所有对象都排好序为止。
冒泡排序 (Bubble Sort)
21
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
2516
25 16
08
49
Exchang=108
25*4921
Exchang=1
i = 2
i = 3
08 16 Exchang=125*2521
22
25*
0 1 2 3 4 5
i = 4 4916
Exchang=008
2521
冒泡排序的算法
typedef int SortData;
void BubbleSort ( SortData V[ ],int n ) {
int i = 1; int exchange = 1;
while ( i < n && exchange ){
exchange = 0; //标志置为 0,假定未交换
for ( int j = n-1; j >= i; j-- )
if ( V[j-1] > V[j] ) { //逆序
23
Swap ( V[j-1],V[j] );,//交换
exchange = 1; //标志置为 1,有交换
}
i++;
}
}
第 i趟对待排序对象序列 V[i-1],V[i],?,V[n-1]
进行排序,结果 将该序列中排序码最小的对象交换到序列的第一个位置 (i-1),其它对象也都向排序的最终位置移动 。 在个别情形,
对象可能在排序中途向相反的方向移动 。
24
最多做 n-1趟冒泡 就能把所有对象排好序 。
在对象的 初始排列已经按排序码从小到大排好序 时,此算法 只执行一趟冒泡,做 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
nninK C N
)()(
)()(
25
快速排序 (Quick Sort)
基本思想是任取 待排序对象序列中的某个对象
(例如取第一个对象 ) 作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列,
冒泡排序需要一个附加对象以实现对象值的对换。
冒泡排序是一个 稳定 的排序方法。
26
左侧子序列中所有对象的排序码都小于或等于基准对象的排序码
右侧子序列中所有对象的排序码都大于基准对象的排序码
基准对象则排在这两个子序列中间 (这也是该对象最终应安放的位置 )。
然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。
27
QuickSort ( List ) {
if ( List的长度大于 1) {
将序列 List划分为两个子序列
LeftList 和 Right List;
QuickSort ( LeftList );
QuickSort ( RightList );
将两个子序列 LeftList 和 RightList
合并为一个序列 List;
}
}
算法描述
28
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 1
49
25*16
2516
08
49
pivot
08
25 4921i = 2
i = 3
08 16 2525*21
pivotpivot
pivot
29
21 25 49 25* 16 08
0 1 2 3 4 5
25*
i = 1
划分
2516
2516
08
49
pivotpos
08
25* 49
08 16 25* 2521
pivotpos
21
比较 4次交换 25,16
i
i
pivotpos
21
比较 1次交换 49,08
49
low pivotpos
交换 21,08
30
最大递归调用层次数与递归树的高度一致,
理想情况为?log2(n+1)? 。 因此,要求存储开销为 O(log2n)。
在最坏的情况,即 待排序对象序列已经按其排序码从小到大排好序 的情况下,其 递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列 。 总的排序码比较次数将达
快速排序是一种 不稳定 的排序方法 。
212
1 21
1
nnninn
i
)()(
31
用第一个对象作为基准对象快速排序退化的例子
08 16 21 25 25* 49 08
0 1 2 3 4 5 pivot
初始
16 21 25 25* 4908 16
21 25 25* 49 2108 16
2525 25* 4908 16 21
25* 49 25*08 16 21 25
4908 16 21 25 25*
i = 1
i = 2
i = 3
i = 4
i = 5
32用居中排序码对象作为基准对象
08 16 21 25 25* 49
0 1 2 3 4 5 pivot
21初始
08 16 21 25 25* 49 08 25*
08 16 21 25 25* 49
i = 1
i = 2
其 排序速度退化到简单排序的水平,比直接插入排序还慢 。占用附加存储 (栈 )将达到 O(n)。
改进办法,取每个待排序对象序列的 第一个对象,最后一个对象 和 位置接近正中的 3 个对象，取其排序码居中者作为基准对象。
33
基本思想是,每一趟 (例如第 i 趟,i = 0,1,…,
n-2) 在后面 n-i 个待排序对象中选出排序码最小的对象,作为有序对象序列的第 i 个对象。
待到第 n-2 趟作完,待排序对象只剩下 1个,就不用再选了。
选择排序
34
② 若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调 ;
③ 在这组对象中剔除这个具有最小排序码的对象 。 在剩下的对象 V[i+1]～ V[n-1]中重复执行第 ①,② 步,直到剩余对象只有一个为止 。
直接选择排序是一种简单的排序方法,它的基本步骤是：
① 在一组对象 V[i]～ V[n-1] 中选择具有最小排序码的对象；
直接选择排序 (Select Sort)
35
21 25 49 25* 16 08
0 1 2 3 4 5
21 25*i = 0
49
25 16
25 16
08
49
08
25*49 21i = 1
i = 2
08 16
25* 25 21
初始最小者 08
交换 21,08
最小者 16
交换 25,16
最小者 21
交换 49,21
36
4925*
0 1 2 3 4 5
25*i = 4
251608
49
25* 4921结果
i = 3
08 16 2521
最小者 25*
无交换最小者 25
无交换252116
08
各趟排序后的结果
37
直接选择排序的算法
typedef int SortData;
void SelectSort ( SortData V[ ],int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( V[i],V[k] );
}
}
38
0 1 2 3 4 5
49
1608 25*49 21
08 25*
25
21
i =1时选择排序的过程
i k j
4925
08 25* 16 21
i k j
49? 25
25*? 25
1625
i k j 16 < 25
39
4925
08 25* 16 21
0 1 2 3 4 5
i k j 21? 16
k 指示当前序列中最小者
直接选择排序的 排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象,则第 i 趟选择具有最小排序码对象所需的比较次数 总是 n-i-1次 。总的排序码比较次数为
2
0 2
11n
i
nninKCN )()(
40
对象的移动次数与对象序列的初始排列有关 。当这组对象的初始状态是按其排序码从小到大有序的时候,对象的移动次数
RMN = 0，达到最少。
最坏情况是每一趟都要进行交换,总的对象移动次数 为 RMN = 3(n-1)。
直接选择排序是一种 不稳定 的排序方法。
41
利用堆及其运算,可以很容易地实现选择排序的思路。
堆排序分为两个步骤
根据初始输入数据，利用堆的调整算法
FilterDown( ) 形成初始堆 ;
通过一系列的对象交换和重新调整堆进行排序。
堆排序 (Heap Sort)
42
建立初始的最大堆
21
25
25*
49
16 08
0
1 2
3 4 5
i 21
25
25* 16
49
08
0
2
543
1
i
21 25 49 25* 16 08
初始排序码集合
21 25 49 25* 16 08
i = 2 时的局部调整
43
21
25
25*
49
16 08
0
1 2
3 4 5
i
49
25
25* 16
21
08
0
2
543
1
21 25 49 25* 16 08 49 25 21 25* 16 08
i = 0 时的局部调整形成最大堆
i = 1 时的局部调整
44
基于初始堆进行堆排序
最大堆堆顶 V[0]具有最大的排序码,将 V[0]与
V[n-1]对调,把具有最大排序码的对象交换到最后,再对前面的 n-1个对象,使用堆的调整算法 FilterDown(0,n-2),重新建立最大堆,
具有次最大排序码的对象又上浮到 V[0]位置。
再 对调 V[0]和 V[n-2],调用 FilterDown(0,n-3),
对前 n-2个对象重新调整,… 。
如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，其细节在下面的程序中给出。
45
49
25
25*
21
16 08
0
1 2
3 4 5
08
25
25* 16
21
49
0
2
543
1
49 25 21 25* 16 08 08 25 21 25* 16 49
交换 0 号与 5 号对象,
5 号对象就位初始最大堆
46
25
25*
08
21
16 49
0
1 2
3 4 5
16
25*
08 25
21
49
0
2
543
1
25 25* 21 08 16 49 16 25* 21 08 25 49
交换 0 号与 4 号对象,
4 号对象就位从 0 号到 4 号 重新调整为最大堆
47
25*
16
08
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
25* 16 21 08 25 49 08 16 21 25* 25 49
交换 0 号与 3 号对象,
3 号对象就位从 0 号到 3 号 重新调整为最大堆
48
21
16
25*
08
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
21 16 08 25* 25 49 08 16 21 25* 25 49
交换 0 号与 2 号对象,
2 号对象就位从 0 号到 2 号 重新调整为最大堆
49
16
08
25*
21
25 49
0
1 2
3 4 5
08
16
25* 25
21
49
0
2
543
1
16 08 21 25* 25 49 08 16 21 25* 25 49
交换 0 号与 1 号对象,
1 号对象就位从 0 号到 1 号 重新调整为最大堆
50
堆排序的时间复杂性为 O(nlog2n)。
空间复杂性为 O(1)。
堆排序是一个 不稳定 的排序方法 。
51
归并排序 (Merge Sort)
归并，是将两个或两个以上的有序表合并成一个新的有序表。
原始序列 initList[ ]中两个有序表
initList[l] … initList[ m]和 initList[m+1] …
initList[n]。它们可归并成一个有序表,存于另一对象序列 mergedList的 l … n 中。
这种归并方法称为 两路归并 (2-way merging)。
设变量 i 和 j 是表 initList[l … m]和 initList
[m+1… n]的当前检测指针。 k是存放指针。
52
08 21 25 25* 49 62 72 93 16 37 54
left mid mid+1 right
initList
i j
08 16 21 25 25* 37 49 54 62 72 93
left right
k
mergeList
当 i 和 j 都在两个表的表长内变化时,根据对应项的排序码的大小,依次把排序码小的对象排放到新表 k 所指位置 中；
当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。
53
迭代的归并排序算法
迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：
假设初始对象序列有 n 个对象,首先把它看成是 n 个长度为 1 的有序子序列 (归并项 )，
先做两两归并，得到?n / 2? 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为 1)；再做两两归并,…,如此重复,最后得到一个长度为 n 的有序序列 。
54
两路归并算法
typedef int SortData;
void merge ( SortData InitList[ ],
SortData mergedList[ ],
int left,int mid,int right ) {
int i = left,j = mid+1,k = left;
while ( i <= mid && j <= right ) //两两比较
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = InitList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++; }
55
while ( i <= mid )
{ mergedList[k] = InitList[i]; i++; k++; }
while ( j <= right )
{ mergedList[k] = InitList[j]; j++; k++; }
}
56
迭代的归并排序算法
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
57
(两路 )归并排序的主算法
void MergeSort ( SortData initList[ ],int n ) {
//按对象排序码非递减的顺序对表中对象排序
SortData tempList[n];
int len = 1;
while ( len < n ) {
MergePass ( initList,tempList,len );
len *= 2;
MergePass ( tempList,initList,len );
len *= 2;
}
}
58
时间复杂度为 O(nlog2n)。
归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组 。 这是这个算法的缺点 。
归并排序是一个 稳定 的排序方法 。
59
基数排序（ Radix Sort）
一、基数排序：按组成关键字的各数位的值进行排序。
60
二,将关键字 Ki看成一个 d元组，即
Ki,Ki,…,K i，其中 0≤Ki≤r，
i=1~n,j=1~d,r为基数,d为关键字的位数 （为最长关键字的长度，不足 d位长的关键字前补零） 。
Ki----最高有效位 MSD
Ki----最低有效位 LSD
排序开始的位置
1 2 d
1
d
j
61
三、基本思想：
设立 r个队列，首先按 Ki 的值，把 n个关键字分配到 r个队列中，然后从小到大将各个队列中的关键字依次收集起来；依此类推，重复进行分配和收集，直至最高有效位。
d
62
四、例：
986 321 432
987765
123
654 018
500
210 ^
head
63
500 210
321
432
123
654
765
986
987
018
NULL
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
r[0]
r[1]
r[2]
r[3]
r[4]
r[5]
r[6]
r[7]
r[8]
r[9]
第一趟分配
64
500 210 123
654 765 986
321
018 ^987
432head
第一趟收集
65
500
210
321
432
654
765
986
NULL
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
r[0]
r[1]
r[2]
r[3]
r[4]
r[5]
r[6]
r[7]
r[8]
r[9]
第二趟分配
018
123
NULL
NULL
987
66
500 210 123
432 654 765
018
987 ^986
321head
第二趟收集
67
018
123
210
321
432
500
654
765
f[0]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
r[0]
r[1]
r[2]
r[3]
r[4]
r[5]
r[6]
r[7]
r[8]
r[9]
第三趟分配
NULL
986 987
68
018 123 432
500 654 765
210
987 ^986
321head
第三趟收集
69
五、性能分析：
基数排序执行一次分配和收集的时间为
O(n+r)，若关键字位数为 d，则总时间为
O(d(n+r))；
辅助空间为 2r；
基数排序是稳定的。
70
各种内部排序方法的比较排序方法 平均时间 辅助空间 稳定性直接插入 O(n2) O(1) 稳定冒 泡 O(n2) O(1) 稳定直接选择 O(n2) O(1) 不稳定希 尔 O(n1.25) O(1) 不稳定快 速 O(nlog2n) O(log2n) 不稳定堆 O(nlog2n) O(1) 不稳定归 并 O(nlog2n) O(n) 稳定基 数 O(d(n+r)) 稳定
71
一、选择合适的排序方法应综合考虑：
待排序的记录数目 n；
记录的大小（规模）；
关键字的结构及其初始状态；
对稳定性的要求；
语言工具的选择；
存储结构；
时间和辅助空间复杂度等；
72
二、目前较为一致的结论：
若 n较小，可采用直接插入或直接选择排序；
若文件初始状态基本有序（正序），则应选择直接插入，冒泡排序；
当 n较大，应选择快速排序、归并排序、堆排序、希尔排序；
从存储容量来讲，归并排序，基数排序，快速排序（从大到小）。
