数据结构：内排序.pdf

文档介绍：该【数据结构：内排序 】是由【窝窝爱蛋蛋】上传分享，文档一共【62】页，该文档可以免费在线阅读，需要了解更多关于【数据结构：内排序 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
数据结构:内排序
DataStructure
2016年3月15日星期二1:.
内排序
排序术语及记号
2
三种代价为O(n)的排序方法
shell排序
快速排序
归并排序
堆排序
分配排序和基数排序
对各种排序算法的实验比较
排序问题的下限
2016年3月15日星期二2:.
排序术语及记号
术语
记录——结点文件——线性表
关键码:能够唯一确定结点的一个或若干域。
排序码:作为排序运算依据的一个或若干域。
组合排序码,(主关键码,次关键码)
例,(总分数,数据结构分数,计算引论分数)
排序:排序就是将一组杂乱无章的数据按一定的
规律排列起来
2016年3月15日星期二3:.
术语
排序问题:给定一组记录r,r,...r,其排序码分别为
12n
k,k,…,k,将这些记录排成顺序为r,r,…,r的一
12ns1s2sn
个序列S,满足条件k≤k≤k。
s1s2sn
排序算法的稳定性:如果在对象序列中有两个对象r[i]和
r[j],它们的关键码k[i]==k[j],且在排序之前,对象
r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象
r[j]的前面,则称这个排序方法是稳定的,否则称这个排
序方法是不稳定的。
排序——在内存中进行的排序
外排序——排序过程还要访问外存(因为待排记录的数量太
大,内存容纳不下)
2016年3月15日星期二4:.
插入排序
2016年3月15日星期二5:.
一趟直接插入排序的基本思想
有序序列A[1..i-1]无序序列A[i..n]
A[i]
有序序列A[1..i]无序序列A[i+1..n]
2016年3月15日星期二6:.
实现“一趟插入排序”分三步进行
[1..i-1]中查找A[i]的插入位置,
A[1..j].keyA[i].key<A[j+1..i-1].key;
[j+1..i-1]中的所有记录均后移
一个位置;
[i]插入(复制)到A[j+1]的位置上。
2016年3月15日星期二7:.
插入排序算法描述
template<typenameE,typenameComp>
voidinssort(EA[],intn){
for(inti=1;i<n;i++)
for(intj=i;(j>0)&&(Comp::prior(A[j],A[j-1]));j--)
swap(A,j,j-1);
}
2016年3月15日星期二8:.
加入监视哨的插入排序算法
template<typenameE,typenameComp>
voidinssort(EA[],intn){
for(inti=2;i<=n;i++)
{A[0]=A[i];j=i-1;
while(Comp::prior(x,A[j]))
{A[j+1]=A[j];j--;}
A[j+1]=A[0];
}
}
2016年3月15日星期二9:.
直接插入排序时间分析
最好的情况(关键字在记录序列中顺序有序):
“比较”的次数:“移动”的次数:
n
1n12(n-1)

i2
最坏的情况(关键字在记录序列中逆序有序):
“比较”的次数:“移动”的次数:
nn
nn(1)(n4)(n1)
(1)i(i1)
i22i22
2016年3月15日星期二10:.
冒泡排序
2016年3月15日星期二11:.
冒泡排序算法
template<typenameE,typenameComp>
voidbubsort(EA[],intn){
for(inti=0;i<n-1;i++)
for(intj=n-1;j>i;j--)
if(Comp::prior(A[j],A[j-1]))
swap(A,j,j-1);
}
2016年3月15日星期二12:.
改进的冒泡排序算法
template<typenameE,typenameComp>
voidbubsort(EA[],intn){
intflag;
for(inti=0;i<n-1;i++)
{flag=FALSE:
for(intj=n-1;j>i;j--)
if(Comp::prior(A[j],A[j-1]))
{swap(A,j,j-1);flag=TRUE;}
if(flag==FALSE)return;
}}
2016年3月15日星期二13:.
冒泡排序时间分析
最好的情况(关键字在记录序列中顺序有序):
只需进行一趟起泡
“比较”的次数:“移动”的次数:
n-10
最坏的情况(关键字在记录序列中逆序有序):
需进行n-1趟起泡
“比较”的次数:“移动”的次数:
22
n(n1)3n(n1)
(i1)3(i1)
in2in2
2016年3月15日星期二14:.
直接选择排序
2016年3月15日星期二15:.
直接选择排序算法
template<typenameE,typenameComp>
voidselsort(EA[],intn){
for(inti=0;i<n-1;i++){
intlowindex=i;//Rememberitsindex
for(intj=n-1;j>i;j--)//Findleast
if(Comp::prior(A[j],A[lowindex]))
lowindex=j;//Putitinplace
swap(A,i,lowindex);
}
}
2016年3月15日星期二16:.
直接选择排序时间性能分析
对n个记录进行简单选择排序,所需进
行的关键字间的比较次数总计为:
n1
n(n1)
(ni)
i12
移动记录的次数,最小值为0,最大值
为3(n-1)。
2016年3月15日星期二17:.
时间代价
InsertionBubbleSelection
Comparisons:
22
BestCase(n)(n)(n)
222
AverageCase(n)(n)(n)
222
WorstCase(n)(n)(n)
Swaps
BestCase00(n)
22
AverageCase(n)(n)(n)
22
WorstCase(n)(n)(n)
2016年3月15日星期二18:.
Shell排序

缩小增量排序法法(不稳定算法,时间代价O(n)
原理:n很小时,或基本有序时排序速度较快
2016年3月15日星期二19:.
希尔排序
将记录序列分成若干子序列,分别对每个子序列进
行插入排序。
例如:将n个记录分成d个子序列:
{A[1],A[1+d],A[1+2d],…,A[1+kd]}
{A[2],A[2+d],A[2+2d],…,A[2+kd]}
…
{A[d],A[2d],A[3d],…,A[kd],A[(k+1)d]}
其中,d称为增量,它的值在排序过程中从大到小逐
渐缩小,直至最后一趟排序减为1。
2016年3月15日星期二20:.
例如:
1625123047**********
第一趟希尔排序,设增量d=5
112312918162536304731
第二趟希尔排序,设增量d=3
918121123162531304736
第三趟希尔排序,设增量d=1
911121618232530313647
2016年3月15日星期二21:.
shell排序算法
template<typenameE,typenameComp>
voidinssort2(EA[],intn,intincr){
for(inti=incr;i<n;i+=incr)
for(intj=i;
(j>=incr)&&
(Comp::prior(A[j],A[j-incr]));j-=incr)
swap(A,j,j-incr);
}
2016年3月15日星期二22:.
shell排序算法
template<typenameE,typenameComp>
voidshellsort(EA[],intn){//Shellsort
for(inti=n/2;i>2;i/=2)//Foreachincr
for(intj=0;j<i;j++)//Sortsublists
inssort2<E,Comp>(&A[j],n-j,i);
inssort2<E,Comp>(A,n,1);
}
2016年3月15日星期二23:.
快速排序
2016年3月15日星期二24:.
快速排序
2016年3月15日星期二25:.
一趟快速排序
目标:找一个记录,以它的关键字作为
“枢轴”,凡其关键字小于枢轴的记录均
移动至该记录之前,反之,凡关键字大于
枢轴的记录均移动至该记录之后。
致使一趟排序之后,记录的无序序列A[s..t]
将分割成两部分:A[s..i-1]和A[i+1..t],且
A[j].key≤A[i].key≤A[j].key
(s≤j≤i-1)枢轴(i+1≤j≤t)。
2016年3月15日星期二26:.
例如A[0]
s52t
23145280
52498036145861972375
lowlowlowlowlowhighhighhighhighhighhigh
设A[s]=52为枢轴
将A[high].key和枢轴的关键字进行比较,
要求A[high].key≥枢轴的关键字
将A[low].key和枢轴的关键字进行比较,
要求A[low].key≤枢轴的关键字
2016年3月15日星期二27:.
快速排序
首先对无序的记录序列进行“一次划分”,之
后分别对分割所得两个子序列“递归”进行快速
排序。
无序的记录序列
一次划分
枢轴无序子序列(2)
无序记录子序列(1)
分别进行快速排序
2016年3月15日星期二28:.
快速排序算法
template<typenameE,typenameComp>
voidqsort(EA[],inti,intj){
if(j<=i)return;//Listtoosmall
intpivotindex=findpivot(A,i,j);
swap(A,pivotindex,j);//Putpivotatend
//kwillbefirstpositiononrightside
intk=partition<E,Comp>(A,i-1,j,A[j]);
swap(A,k,j);//Putpivotinplace
qsort<E,Comp>(A,i,k-1);
qsort<E,Comp>(A,k+1,j);
}
2016年3月15日星期二29:.
快速排序算法
template<typenameE>
inlineintfindpivot(EA[],inti,intj)
{return(i+j)/2;}
template<typenameE,typenameComp>
inlineintpartition(EA[],intl,intr,E&pivot){
do{//Movetheboundsinuntiltheymeet
while(Comp::prior(A[++l],pivot));
while((l<r)&&Comp::prior(pivot,A[--r]));
swap(A,l,r);//Swapout-of-placevalues
}while(l<r);//Stopwhentheycross
swap(A,l,r);//Reverselastswap
returnl;//Returnfirstposonright
}
2016年3月15日星期二30
:.
快速排序的时间分析
假设一次划分所得枢轴位置i=k,则对n个记录进
行快排所需时间:
T(n)=T(n)+T(k-1)+T(n-k)
pass
其中T(n)为对n个记录进行一次划分所需时间。
pass
若待排序列中记录的关键字是随机分布的,则k取
1至n中任意一值的可能性相同。
2016年3月15日星期二31:.
由此可得快速排序所需时间的平均值为:
n
1
T(n)CnT(k1)T(nk)
avgavgavg
nk1
设T(1)≤b
avg
则可得结果:
b
Tavg(n)(2c)(n1)ln(n1)
2
结论:快速排序的时间复杂度为O(nlogn)
2016年3月15日星期二32:.
快速排序的时间分析
若待排记录的初始状态为按关键字有序
时,快速排序将蜕化为起泡排序,其时间
2
复杂度为O(n)。
2016年3月15日星期二33:.
归并排序
通常采用的是2-路归并排序。即:将两个
位置相邻的记录有序子序列
有序子序列R[l..m]有序子序列R[m+1..n]
归并为一个记录的有序序列。
有序序列R[l..n]
2016年3月15日星期二34:.
归并排序
Listmergesort(Listinlist){
if(()<=1)returninlist;
Listl1=halfoftheitemsfrominlist;
Listl2=otherhalfofitemsfrominlist;
returnmerge(mergesort(l1),mergesort(l2));
}
2016年3月15日星期二35:.
归并排序的算法
如果记录无序序列A[left..right]的两部分
A[left..(left+right)/2]和A[(left+right)/2+1..right]
分别按关键字有序,
则利用上述归并算法很容易将它们归
并成整个记录序列是一个有序序列。
由此,应该先分别对这两部分进行
2-路归并排序。
2016年3月15日星期二36:.
例如:
52,23,80,36,68,14(left=1,right=6)
[52,23,80][36,68,14]
[52,23][80][36,68][14]
[52][23][36][68]
[23,52][36,68]
[23,52,80][14,36,68]
[14,23,36,52,68,80]
2016年3月15日星期二37:.
归并排序算法
template<typenameE,typenameComp>
voidmergesort(EA[],Etemp[],intleft,intright){
if(left==right)return;
intmid=(left+right)/2;
mergesort<E,Comp>(A,temp,left,mid);
mergesort<E,Comp>(A,temp,mid+1,right);
for(inti=left;i<=right;i++)//Copy
temp[i]=A[i];
inti1=left;inti2=mid+1;
for(intcurr=left;curr<=right;curr++){
if(i1==mid+1)//Leftexhausted
A[curr]=temp[i2++];
elseif(i2>right)//Rightexhausted
A[curr]=temp[i1++];
elseif(Comp::prior(temp[i1],temp[i2]))
A[curr]=temp[i1++];
elseA[curr]=temp[i2++];
2016年}}3月15日星期二38
:.
优化归并排序算法
template<typenameE,typenameComp>
voidmergesort(EA[],Etemp[],intleft,intright){
if((right-left)<=THRESHOLD){
inssort<E,Comp>(&A[left],right-left+1);
return;
}
inti,j,k,mid=(left+right)/2;
if(left==right)return;
mergesort<E,Comp>(A,temp,left,mid);
mergesort<E,Comp>(A,temp,mid+1,right);
for(i=mid;i>=left;i--)temp[i]=A[i];
for(j=1;j<=right-mid;j++)
temp[right-j+1]=A[j+mid];
for(i=left,j=right,k=left;k<=right;k++)
if(temp[i]<temp[j])A[k]=temp[i++];
elseA[k]=temp[j--];
}
2016年3月15日星期二39
:.
归并排序算法效率
设需排序元素的数目为n,递归的深度为logn
(简单起见,设n是2的幂),第一层递归是对一
个长度为n的数组排序,下一层是对两个长度为
n/2的子数组排序,…,最后一层对n个长度为1
的子数组排序。
时间复杂度:T(n)=O(nlog2n)
空间复杂度:S(n)=O(n)
2016年3月15日星期二40:.
堆排序
堆排序:
将无序序列建成一个堆,得到关键字最小(或最
大)的记录;输出堆顶的最小(大)值后,使剩
余的n-1个元素重又建成一个堆,则可得到n个元
素的次小值;重复执行,得到一个有序序列,这
个过程叫堆排序。
堆排序需解决的两个问题:
如何由一个无序序列建成一个堆?
如何在输出堆顶元素之后,调整剩余元素,使之
成为一个新的堆?
2016年3月15日星期二41
:.
建堆是一个从下往上进行“筛选”的过程
例如:排序之前的关键字序列为
4098
5581499849
73817312363627984940
81735564361212
现在,左/右子树都已经调整为堆,最后只要调
整根结点,使整个二叉树是个“堆”即可。
2016年3月15日星期二42:.
堆排序算法
第二个问题解决方法——筛选
输出堆顶元素之后,以堆中最后一个元素替代之;然后将根
结点值与左、右子树的根结点值进行比较,并与其中小者进
行交换;重复上述操作,直至叶子结点,将得到新的堆,称
这个从堆顶至叶子的调整过程为“筛选”。
堆排序算法
template<typenameE,typenameComp>
voidheapsort(EA[],intn){//Heapsort
Emaxval;
maxheap<E,Comp>H(A,n,n);
for(inti=0;i<n;i++)//Nowsort
maxval=();//Putmaxatend
}
2016年3月15日星期二43
:.
HeapsortExample(1)
2016年3月15日星期二44:.
HeapsortExample(2)
2016年3月15日星期二45:.
堆排序的时间复杂度分析
,“筛选”所需进行的关键字
比较的次数至多为2(k-1);
,建成深度为h(=logn+1)的堆,
2
所需进行的关键字比较的次数至多4n;
“堆顶”n-1次,总共进行的关键
字比较的次数不超过
2(log(n-1)+log(n-2)+…+log2)<2n(logn)
2222
因此,堆排序的时间复杂度为O(nlogn)。
2016年3月15日星期二46:.
分配排序和基数排序
Asimple,efficientsort:
for(i=0;i<n;i++)
B[A[i]]=A[i];
Waystogeneralize:
Makeeachbintheheadofalist.
Allowmorekeysthanrecords.
2016年3月15日星期二47:.
分配排序
template<typenameE,classgetKey>
voidbinsort(EA[],intn){
List<E>B[MaxKeyValue];
Eitem;
for(i=0;i<n;i++)B[A[i]].append(getKey::key(A[i]));
for(i=0;i<MaxKeyValue;i++)
for(B[i].setStart();
B[i].getValue(item);B[i].next())
output(item);
}
2016年3月15日星期二48:.
基数排序
2016年3月15日星期二49:.
SupposethattherecordRhasrkeys.
i
j
K::=thej-thkeyofrecordR
ii
0
K::=themostsignificantkeyofrecordR
ii
r1
K::=theleastsignificantkeyofrecordR
ii
AlistofrecordsR,...,Rislexicallysortedwithrespect
0n1
01r1
totheke