文档介绍：数据结构(shù jù jié ɡòu)第7章
第一页，共80页。
2
排序(pái xù)术语及记号
术语
记录——结点 文件——线性表
关键码：能够唯一确定结点的一个或若干域。
排序码：作为排序运算依据的一个或若干域。
组合排序码，(主关键码，次关键码)
例，(总分数，数据结构分数，计算引论分数)
排序：将一组杂乱无章的数据按一定的规律(guīlǜ)排列起来将序列中的记录。
第1页/共80页
第二页，共80页。
3
术语(shùyǔ)
排序问题
给定一组记录序列R={r1,r2,...rn},其排序码分别为K={ k1,k2, …，kn}
将这些记录排成顺序为R’={ rs1,rs2,…，rsn }的一个序列S，其排序码序列K’={ ks1，ks2，……ksn }是一个满足某种关系的有序序列。关系是任意(rènyì)的，如通常经常使用的小于、大于等关系或任意(rènyì)的关系。
第2页/共80页
第三页，共80页。
4
术语(shùyǔ)
内排序——全部记录都可以同时调入内存进行的排序。
外排序——排序过程(guòchéng)还要访问外存(因为待排记录的数量太大，内存容纳不下)
排序算法的稳定 & 不稳定
如果在对象序列中有两个对象r[i]和r[j]，它们的关键码 k[i] == k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。
第3页/共80页
第四页，共80页。
5
基本操作
按排序依据原则
插入排序：直接插入排序、折半插入排序、希尔（shell）排序
交换排序：冒泡排序、快速(kuài sù)排序
选择排序：简单选择排序、堆排序
归并排序：2-路归并排序
基数排序
第4页/共80页
第五页，共80页。
6
三种代价(dàijià)为O(n2)的排序方法
插入排序
冒泡排序
选择(xuǎnzé)排序
第5页/共80页
第六页，共80页。
7
插入排序
算法思想：逐个处理待排序的记录，每个记录都要与前面(qián mian)那些已排好序的记录进行比较，然后插入到适当的位置。
第6页/共80页
第七页，共80页。
8
教材(jiàocái)上插入排序算法
template <class Elem, class Comp>
void inssort(Elem A[], int n) {
for (int i=1; i<n; i++)
for (int j=i; (j>0) &&
(Comp::lt(A[j], A[j-1])); j--)
swap(A, j, j-1);
}
算法分析：
稳定
空间代价(dàijià)：Θ(1)
时间代价(dàijià)：
最佳情况：n-1次比较，0次交换，Θ(n)
最差情况：比较次数为∑i=n(n-1)/2=Θ(n2)
交换次数为 3∑i=3n(n-1)/2=Θ(n2)（一次swap需要交换3次）
平均情况：Θ(n2)
i=1
n-1
i=1
n-1
第7页/共80页
第八页，共80页。
9
改进(gǎijìn)的插入排序算法
template <class Elem, class Comp>
void inssort(Elem A[], int n) {
for (int i=1; i<n; i++)
{Elem temp=A[i];
j=i-1;
while (j>=0 &&(Comp::lt(temp, A[j])))
{A[j+1]=A[j];j--;} //将>=A[i]的记录后移
A[j+1]=temp; // A[j+1]是记录A[i]的正确(zhèngquè)位置
}
}
第8页/共80页
第九页，共80页。
10
改进插入排序算法(suàn fǎ)分析
算法分析：
稳定
空间代价：Θ(1)
时间代价：
最佳情况：n-1次比较，n次交换(jiāohuàn)，Θ(n)
最差情况：比较次数为Θ(n2)（同前）
交换(jiāohuàn)次数为 ∑i=n(n-1)/2=Θ(n2)
平均情况：Θ(n2)
i=1
n-1
第9页/共80页
第十页，共80页。