第十章 群体数据的组织
清华大学计算机与信息管理中心
郑 莉
C++语言程序设计
前一页 休息 2
本章主要内容
? 插入排序
? 选择排序
? 交换排序
? 顺序查找
? 折半查找
前一页 休息 3
排序（ sorting）
? 排序 是计算机程序设计中的一种重要操作，它
的功能是将一个 数据元素 的任意序列，重新排
列成一个按 关键字 有序的序列。
– 数据元素,数据的基本单位。在计算机中通常作为
一个整体进行考虑。一个数据元素可由若干数据项
组成。
– 关键字,数据元素中某个数据项的值，用它可以标
识（识别）一个数据元素。
? 在排序过程中需要完成两种基本操作：
– 比较两个数的大小
– 调整元素在数组中的位置
前一页 休息 4
内部排序与外部排序
? 内部排序,待排序的数据元素存放在计算
机内存中进行的排序过程。
? 外部排序,待排序的数据元素数量很大，
以致内存存中一次不能容纳全部数据，在
排序过程中尚需对外存进行访问的排序过
程。
前一页 休息 5
内部排序方法
? 插入排序
? 选择排序
? 交换排序
前一页 休息 6
插入排序的基本思想
? 每一步将一个待排序元素按其关键字值的大小插入到已排
序序列的适当位置上，直到待排序元素插入完为止。
初始状态,[5] 4 10 20 12 3
插入操作,1 [4] [4 5] 10 20 12 3
2 [10] [4 5 10] 20 12 3
3 [20] [4 5 10 20] 12 3
4 [12] [4 5 10 12 20] 3
5 [3] [3 4 5 10 12 20]
前一页 休息 7
直接插入排序
? 在插入排序过程中，由于寻找插入位置的
方法不同又可以分为不同的插入排序法，
这里我们只介绍最简单的直接插入排序法。
? 例 10.1 直接插入排序函数模板（ 10-1.h）
template <class T>
void InsertionSort(T A[],int n)
{ int i,j;
T temp;
for (i = 1; i < n; i++)
{ j = i;
temp = A[i];
while (j > 0 && temp < A[j-1])
{ A[j] = A[j-1];
j--;
}
A[j] = temp;
}
}
前一页 休息 9
选择排序的基本思想
每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），顺序排在已排序序列的
最后，直至全部排完。
[5 4 10 20 12 3]初始状态：
3 [4 10 20 12 5]
3 4 [10 20 12 5]
第 i 次选择后，将选出的那个记录与第 i 个记录做 交换 。
3 4 5 [20 12 10]
...,..
前一页 休息 10
直接选择排序
? 在选择类排序方法中，从待排序序列中选
择元素的方法不同，又分为不同的选择排
序方法，其中最简单的是通过顺序比较找
出待排序序列中的最小元素，称为直接选
择排序。
? 例 10.2 直接选择排序函数模板（ 10-2.h）
template <class T>
void Swap (T &x,T &y)
{ T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void SelectionSort(T A[],int n)
{ int smallIndex;
int i,j;
for (i = 0; i < n-1; i++)
{ smallIndex = i;
for (j = i+1; j < n; j++)
if (A[j] < A[smallIndex])
smallIndex = j;
Swap(A[i],A[smallIndex]);
}
}
前一页 休息 13
交换排序的基本思想
两两比较待排序序列中的元素，并交
换不满足顺序要求的各对元素，直到全部
满足顺序要求为止。
前一页 休息 14
最简单的交换排序方法
—— 起泡排序
对具有 n个元素的序列按升序进行起泡排序的步骤：
– 首先将第一个元素与第二个元素进行比较，若为逆序，
则将两元素交换。然后比较第二、第三个元素，依次
类推，直到第 n-1和第 n个元素进行了比较和交换。此
过程称为第一趟起泡排序。经过第一趟，最大的元素
便被交换到第 n个位置。
– 对前 n-1个元素进行第二趟起泡排序，将其中最大元
素交换到第 n-1个位置。
– 如此继续，直到某一趟排序未发生任何交换时，排序
完毕。对 n个元素的序列，起泡排序最多需要进行 n-1
趟。
前一页 休息 15
起泡排序举例
对整数序列 8 5 2 4 3 按升序排序
8
5
2
4
3
5
2
4
3
8
2
4
3
5
8
2
3
4
5
8
2
3
4
5
8
初
始
状态
第
一
趟
结果
第
二
趟
结果
第
三
趟
结果
第
四
趟
结果
小
的
逐
渐
上
升
每
趟
沉
下
一
个
最
大
的
前一页 休息 16
例 10-3 起泡排序函数模板
template <class T>
void Swap (T &x,T &y)
{
T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void BubbleSort(T A[],int n)
{ int i,j;
int lastExchangeIndex;
i = n-1;
while (i > 0)
{ lastExchangeIndex = 0;
for (j = 0; j < i; j++)
if (A[j+1] < A[j])
{
Swap(A[j],A[j+1]);
lastExchangeIndex = j; }
i = lastExchangeIndex;
}
}
前一页 休息 18
顺序查找
? 其基本思想
– 从数组的首元素开始, 逐个元素与待查找的
关键字进行比较, 直到找到相等的 。 若整个
数组中没有与待查找关键字相等的元素, 就
是查找不成功 。
? 顺序查找函数模板
– 例 10.4
template <class T>
int SeqSearch(T list[],int n,T key)
{
for(int i=0;i < n;i++)
if (list[i] == key)
return i;
return -1;
}
前一页 休息 20
折半查找的基本思想
对于已按关键字排序的序列，经过一次
比较，可将序列分割成两部分，然后只在有
可能包含待查元素的一部分中继续查找，并
根据试探结果继续分割，逐步缩小查找范围，
直至找到或找不到为止。
前一页 休息 21
折半查找举例
用折半查找法，在下列序列中查找值为 21的元素：
L=1
5 13 19 21 37 56 64 75 80 88 92
H=11M =INT((L+H)/2)=6
5 13 19 21 37
L=1 H=M-1=5 M=INT((L+H)/2)=3M
21 37
H
L=M+1=4
L
M=INT((L+H)/2)=4
M
前一页 休息 22
例 10-5 折半查找函数模板
template <class T>
int BinSearch(T list[],int n,T key)
{ int mid,low,high;
T midvalue;
low=0;
high=n-1;
while (low <= high)
{ mid = (low+high)/2;
midvalue = list[mid];
if (key == midvalue) return mid;
else if (key < midvalue) high = mid-1;
else low = mid+1;
}
return -1;
}
前一页 休息 24
作业
? 复习第十章，预习第十一章
? 实验十
清华大学计算机与信息管理中心
郑 莉
C++语言程序设计
前一页 休息 2
本章主要内容
? 插入排序
? 选择排序
? 交换排序
? 顺序查找
? 折半查找
前一页 休息 3
排序（ sorting）
? 排序 是计算机程序设计中的一种重要操作，它
的功能是将一个 数据元素 的任意序列，重新排
列成一个按 关键字 有序的序列。
– 数据元素,数据的基本单位。在计算机中通常作为
一个整体进行考虑。一个数据元素可由若干数据项
组成。
– 关键字,数据元素中某个数据项的值，用它可以标
识（识别）一个数据元素。
? 在排序过程中需要完成两种基本操作：
– 比较两个数的大小
– 调整元素在数组中的位置
前一页 休息 4
内部排序与外部排序
? 内部排序,待排序的数据元素存放在计算
机内存中进行的排序过程。
? 外部排序,待排序的数据元素数量很大，
以致内存存中一次不能容纳全部数据，在
排序过程中尚需对外存进行访问的排序过
程。
前一页 休息 5
内部排序方法
? 插入排序
? 选择排序
? 交换排序
前一页 休息 6
插入排序的基本思想
? 每一步将一个待排序元素按其关键字值的大小插入到已排
序序列的适当位置上，直到待排序元素插入完为止。
初始状态,[5] 4 10 20 12 3
插入操作,1 [4] [4 5] 10 20 12 3
2 [10] [4 5 10] 20 12 3
3 [20] [4 5 10 20] 12 3
4 [12] [4 5 10 12 20] 3
5 [3] [3 4 5 10 12 20]
前一页 休息 7
直接插入排序
? 在插入排序过程中，由于寻找插入位置的
方法不同又可以分为不同的插入排序法，
这里我们只介绍最简单的直接插入排序法。
? 例 10.1 直接插入排序函数模板（ 10-1.h）
template <class T>
void InsertionSort(T A[],int n)
{ int i,j;
T temp;
for (i = 1; i < n; i++)
{ j = i;
temp = A[i];
while (j > 0 && temp < A[j-1])
{ A[j] = A[j-1];
j--;
}
A[j] = temp;
}
}
前一页 休息 9
选择排序的基本思想
每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），顺序排在已排序序列的
最后，直至全部排完。
[5 4 10 20 12 3]初始状态：
3 [4 10 20 12 5]
3 4 [10 20 12 5]
第 i 次选择后，将选出的那个记录与第 i 个记录做 交换 。
3 4 5 [20 12 10]
...,..
前一页 休息 10
直接选择排序
? 在选择类排序方法中，从待排序序列中选
择元素的方法不同，又分为不同的选择排
序方法，其中最简单的是通过顺序比较找
出待排序序列中的最小元素，称为直接选
择排序。
? 例 10.2 直接选择排序函数模板（ 10-2.h）
template <class T>
void Swap (T &x,T &y)
{ T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void SelectionSort(T A[],int n)
{ int smallIndex;
int i,j;
for (i = 0; i < n-1; i++)
{ smallIndex = i;
for (j = i+1; j < n; j++)
if (A[j] < A[smallIndex])
smallIndex = j;
Swap(A[i],A[smallIndex]);
}
}
前一页 休息 13
交换排序的基本思想
两两比较待排序序列中的元素，并交
换不满足顺序要求的各对元素，直到全部
满足顺序要求为止。
前一页 休息 14
最简单的交换排序方法
—— 起泡排序
对具有 n个元素的序列按升序进行起泡排序的步骤：
– 首先将第一个元素与第二个元素进行比较，若为逆序，
则将两元素交换。然后比较第二、第三个元素，依次
类推，直到第 n-1和第 n个元素进行了比较和交换。此
过程称为第一趟起泡排序。经过第一趟，最大的元素
便被交换到第 n个位置。
– 对前 n-1个元素进行第二趟起泡排序，将其中最大元
素交换到第 n-1个位置。
– 如此继续，直到某一趟排序未发生任何交换时，排序
完毕。对 n个元素的序列，起泡排序最多需要进行 n-1
趟。
前一页 休息 15
起泡排序举例
对整数序列 8 5 2 4 3 按升序排序
8
5
2
4
3
5
2
4
3
8
2
4
3
5
8
2
3
4
5
8
2
3
4
5
8
初
始
状态
第
一
趟
结果
第
二
趟
结果
第
三
趟
结果
第
四
趟
结果
小
的
逐
渐
上
升
每
趟
沉
下
一
个
最
大
的
前一页 休息 16
例 10-3 起泡排序函数模板
template <class T>
void Swap (T &x,T &y)
{
T temp;
temp = x;
x = y;
y = temp;
}
template <class T>
void BubbleSort(T A[],int n)
{ int i,j;
int lastExchangeIndex;
i = n-1;
while (i > 0)
{ lastExchangeIndex = 0;
for (j = 0; j < i; j++)
if (A[j+1] < A[j])
{
Swap(A[j],A[j+1]);
lastExchangeIndex = j; }
i = lastExchangeIndex;
}
}
前一页 休息 18
顺序查找
? 其基本思想
– 从数组的首元素开始, 逐个元素与待查找的
关键字进行比较, 直到找到相等的 。 若整个
数组中没有与待查找关键字相等的元素, 就
是查找不成功 。
? 顺序查找函数模板
– 例 10.4
template <class T>
int SeqSearch(T list[],int n,T key)
{
for(int i=0;i < n;i++)
if (list[i] == key)
return i;
return -1;
}
前一页 休息 20
折半查找的基本思想
对于已按关键字排序的序列，经过一次
比较，可将序列分割成两部分，然后只在有
可能包含待查元素的一部分中继续查找，并
根据试探结果继续分割，逐步缩小查找范围，
直至找到或找不到为止。
前一页 休息 21
折半查找举例
用折半查找法，在下列序列中查找值为 21的元素：
L=1
5 13 19 21 37 56 64 75 80 88 92
H=11M =INT((L+H)/2)=6
5 13 19 21 37
L=1 H=M-1=5 M=INT((L+H)/2)=3M
21 37
H
L=M+1=4
L
M=INT((L+H)/2)=4
M
前一页 休息 22
例 10-5 折半查找函数模板
template <class T>
int BinSearch(T list[],int n,T key)
{ int mid,low,high;
T midvalue;
low=0;
high=n-1;
while (low <= high)
{ mid = (low+high)/2;
midvalue = list[mid];
if (key == midvalue) return mid;
else if (key < midvalue) high = mid-1;
else low = mid+1;
}
return -1;
}
前一页 休息 24
作业
? 复习第十章，预习第十一章
? 实验十
