第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换，……关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上；
依次类推，则完成排序。
正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2)
适合于数据较少的情况。
2013-5-13 排序n个记录的文件最多需要n-1趟冒泡排序。 举例：图8-2-5
25
思想：小的 浮起，大的 沉底。
25 56 49 78 11 65 41 36
初 始 关 键 字
25 49 56 11 65 41 36 78
第 一 趟 排 序 后
25 49 11 56 41 36 65
25 11 49 41 36 56
11 25 41 36 49
11 25 36 41
11 25 36
简单选择排序、堆排序。
1、简单选择排序
思想：首先从1~n个元素中选 出关键字最小的记录交换到第 一个位置上。然后再从第2 个 到第n个元素中选出次小的记 录交换到第二个位置上，依次 类推。
时间复杂度为O(n2)， 适用于待排序元素较少的情况。
3 j 3 k 3 k 3
互换
9 9 j 9 9
1 1 1 j 1 k 8
插入算法如下：
9
方法:Ki与Ki-1,K i-2,…K1依次比较,直到找到应插入的位置。 void insertSort(RedType L[ ],int n)
{ int i ,j; for(i=2; i<=n; i++) if(L[i].key<L[i-1].key)
{
L[0]=L[i];
L[j+1]=L[j]; L[j+1]=L[0];
[ 15
27
36
53
69 ]
42
[ 15
27
36
low high mid ( 42<53 ) 53 69 ] 42 (high<low ，查找结束，插入位置为low 或high+1 )
high low
[ 15
27
36
42
53
69 ]
2013-5-13
void BinsertSort(RedType L[ ],int n)
19
E、筛选算法（调整建堆）
typedef Sqlist HeapType; //堆采用顺序表存储表示 void HeapAdjust( HeapType &H, int s, int m){ // 已知H.r[s..m]中记录的关键字除H.r[s] .key外均满足堆定义， //本函数调整H.r[s] .key，使H.r[s..m]成为一个堆，其中堆顶元素为最大值 rc=H.r[s]; for(j=2*s; j<=m; j*=2) { //沿关键字值较大的孩子结点向下筛选 if( j<m && H.r[j].key <H.r[j+1].key) + +j;// j 为 key较大的记录下标 if( rc.key >= H.r[j].key) break; H.r[s]=H.r[j]; s=j; // }// for s H.r[s]=rc; 10 10 76 24 33 15 } 1 2 3 4 5 j 76 24 rc.key = 10
2013-5-13
22
A:
56
25
49
F、堆排序算法
56
25 49 i=3
i=4
78
11
65
(1)
41
78
11
65
(2)
41
36 i=1 78 56
36 25
25 65 78 56
25 65 78 56 65
i=2
11
49 (5)
41
11
49 (4)
41
11
49 (3)
41
36
36
2013-5-13
6 6 6 6 j 6 第 二 趟 第 一 趟
14
3 i k
9 j 9
1 i k 1 i k 1
3
8 j 8 j
6
3
9
6
3
2013-5-13
9 i k
8 j
6
第 三 趟
简单选择排序的算法如下：
15
void SelectSort( RedType L[ ],int n)
{ int i,j,k,t; for (i=1,i<=n;++i） { k=i； for(j=i+1;j<=n;++j)
举例，图8-2-2
2013-5-13
2、折半插入排序
11
折半插入排序在寻找插入位置时，不是逐个比较而是利用折半 查找的原理寻找插入位置。待排序元素越多，改进效果越明显。
例：有6个记录，前5 个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42
low mid ( 42>36 ) high
6
插入排序
直接插入排序 折半插入排序
简单选择排序 堆排序 起泡排序
选择排序
排序方法
交换排序 归并排序
2013-5-13
快速排序
7
10.2 插入排序
直接插入、折半插入
1、直接插入排序: 基本思想：从数组的第2号元素开始，顺 序从数组中取出元素，并将该元素插入 到其左端已排好序的数组的适当位置上。
举例：图8-2-1
2013-5-13
假设待排序的记录存放在地址连续的 一组存储单元中，那么这种存储方式 下的数据类型可描述为：
5
#define MAX 20 typedef struct { int key; float otherinfo;
0 1 2 3 4
key info
MAX
}RedType;
… … …
2013-5-13
12
{ int i,low,high,mid;
for(i=2; i<=n; ++i){ L[0]=L[i]; /* r[0]作为监视哨*/
low=1; high=i-1;
While(low<=high) {mid=(low+high)/2; else low=mid+1; } for( j=i-1; j>=high+1; j ) L[j+1]=L[j]; L[high+1]=L[0]; } /* for*/ }/*折半插入排序*/
36
n=8, int(n/2)=4开始 25 41 11 65 49 36 11 56
25 41 65
78 (b): 78被筛选后的状态 11 25 36 78 56 65 41 49
56 36
49
78
78
2013-5-13 (d): 56被筛选后的状态
(c): 49被筛选后的状态
(e): 被筛选之后建成堆
76 33 24
s
10
24
s 15 76
j 76
33
15
10
33 24
15
10 15
10 10 24 33 j=2*j=4
j=2*j=8>m
第二次
2013-5-13
第一次
21
F、堆排序算法
void HeapSort( HeapType &H) { //堆顺序表H进行堆排序 for( i=H.length/2; i>0; i) HeapAdjust(H, i, H.length); // 把H.r[1..H.length]成为一个堆， For(i=H.length; i>1; i){ 把堆顶元素与最后一个记录相交换 // rc=H.r[1]; H.r[1]=H.r[i]; H.r[i]=rc; HeapAdjust(H, 1, i-1); //把H.r[1..i-1]重新调整为一个堆 } }
16
33
15
10
56
49
78
(a):堆顶元素取最大值 (2) 实现堆排序需解决两个问题：
(b):堆顶元素取最小值
（1） 如何由一个无序序列建成一个堆？
（2） 输出堆顶元素后，如何将剩余元素调整成一个新的堆？
举例：图8-2-4
2013-5-13
(3) 输出堆顶元素并调整建新堆的过程(筛选) 把自堆顶至叶子的调整过程称为“筛选‘。从一个无序序 65 11 (a) (b) 列建堆的过程就是一个反复”筛选“的过程。
2013-5-13
8
10.2 插入排序
直接插入、折半插入
1、直接插入排序: 基本思想：从数组的第2号元素开始，顺序从数组中取出元素， 并将该元素插入到其左端已排好序的数组的适当位置上 待排元素序列：[53] 27 36 15 69 42 第一次排序： 第二次排序： [27 53] 36 15 69 42 [27 36 53] 15 69 42
第 二 趟 排 序 后
2013-5-13
第 三 趟 排 序 后
第 四 趟 排 序 后
第 五 趟 排 序 后
第 六 趟 排 序 后
26
冒泡排序的C程序段：
Void bubsort(RedType L[ ],int n) { int i,x,j=1,k=1;
while (j<n)&&(k>0);
{ k=0; for (i=1;i<=n-j; i++) if (L[i+1].key<L[i].key) {k++;x=L[i];L[i]=L[i+1];L[i+1]=x;} j++; } /*while*/