数据结构思维导图-排序.pdf
需积分: 25 65 浏览量
2022-08-23
22:58:27
上传
评论
收藏 268KB PDF 举报
排序
基本概念
稳定性
算法的稳定性指：如果序列中存在的相同关键字
在排序算法后顺序不变，则算法稳定，有变则不
稳定，
比较次数
对任意序列进行比较，求最少的比较次数即考虑
最坏情况，对任意n个关键字至少比较次数为向
上取整的[log2(n!)]
内外部排序
内部排序：排序期间，元素都在内存；外部排
序：排序期间，元素在内外存之间不断移动。
衡量标准 时空复杂度
内部排序(内存中)
插入排序
基本思想
将待排序的序列中的关键字插入已排序的序列中
去，直到每个元素都在已排序序列中。
直接插入
一、适用链式和顺序存储的线性表。
二、稳定性：先比较后移动，稳定。
三、时间复杂度O(n^2)。空间复杂度常数级O(
1)。在待排序序列正序时。时间复杂度为O(n)。
四、逻辑：起始，第二个元素开始与前一个元素
比较，前一个元素相当于排序好的子序列的尾部
元素，如果小于前一个元素，则应该插入子序列
中，与子序列元素依次比较，大于该元素的后
移，该元素赋值给相应的位置；第n轮重复插
入。哨兵只是为了存放元素值和处理排序时判断
一次元素值用到，可以处理下排序循环的条件，
可以用单独的变量来存放关键字。
void InsertSort(ElemType A[],int n){//数组A,处
理的元素n个
int i,j;
//循环比较每个元素，A[1]-A[n]存放需要处理的
序列值
for(i=2;i<=n;i++){
if(A[i]<A[i-1]){//关键字小于前驱，需要排序
A[0]=A[i];//暂时存放需要处理的值，
//给需要插入的元素排序调整排好序的子序列
for(j=i-1;A[0]<A[j];--j){
A[j+1]=A[j];//元素值后移
}
A[j+1]=A[0];//关键字插入到相应位置
}
}
}
折半插入
一、适用顺序存储的线性表。
二、稳定性：稳定，比较后移动。
三、时间复杂度：O(n^2)。
四、逻辑：与直接插入一样，对于已有序的子序
列采用折半查找的方式查找位置进行插入，移动
元素的次数未改变。
void InsertSort(ElemType A[],int n){
//序列数组0号位存哨兵，n个关键字。
int i,j,low,high,mid;
for(i=2;i<=n;i++){
A[0]=A[i];
low=1;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid]>A[0]){
high=mid-1;//左边查找
}else{
low=mid+1;//右边查找
}
}
//与直接插入一样循环中后移元素
for(j=i-1;j>=high+1;--j){
A[j+1]=A[j];
}
A[high+1]=A[0];//插入操作
}
}
希尔排序
一、稳定性：非稳定。当相同元素分到不同的子
表时，可能交换次序后相对位置发生了变化。
二、时间复杂度：O(n^2)。空间复杂度为O(1)。
三、适用性：表为顺序存储的线性表。
四、改进原因：①插入排序在对几乎已经排好序
的数据操作时，效率高，即可以达到线性排序的
效率；②插入排序一般来说是低效的，因为插入
排序每次只能将数据移动一位。
五、逻辑：将待排序序列按照一定的间隔分为若
干子序列分别进行直接插入排序，直到待排序序
列基本有序，再对整体进行直接插入排序。
void ShellSort(ElemType A[],int n){
for(dk=n/2;dk>=1;dk=dk/2){//确定增量为多少
for(i=dk+1;i<=n;++i){//按照增量分为n-dk个子
序列。
//对其中一个被间隔开的子序列进行插入排
序。
if(A[i]<A[i-dk]){
A[0]=A[i];
for(j=i-dk;j>0&&A[0]<A[j];j-=dk){
A[j+dk]=A[j];
}
A[j+dk]=A[0];
}
}
}
}
交换排序
基本思想 序列中两个关键字对比，逆序则交换位置。
冒泡排序
一、稳定性：稳定。A[i]=A[j]，不交换。
二、时间复杂度：O(n^2);空间复杂度：O(1)。
三、逻辑：从后往前或从前往后两两比较相邻关
键字的大小，第一趟比较完成，将最小的元素交
换到了序列最前，相当于一个元素已经站定他的
位置，下一趟不再参与排序。
void BubbleSort(ElemType A[],int n){
for(i=0;i<n-1;i++){//第i+1躺排序
flag=flase;
for(j=n-1;j>1;j--){//从后往前排
if(A[j-1]>A[j]){//从小到大排
swap(A[j-1],A[j]);//交换两个元素
flag=true;
}
}
//flag=false本躺没有交换，已排好退出排序
if(flag==false){
return;
}
}
}
快排
一、时间复杂度：最坏情况O(n^2)，最好的情况
每次平均划分找到最中间的位置元素，最好为O(
nlog2(n))；空间复杂度：O(log2(n)),需要递归
栈，最好情况和平均情况下栈深度为O(log2(
n))，最坏为O(n)。
二、是所有内部排序中平均性能最优的算法。
三、稳定性：不稳定，当相同元素小于基准被交
换时，相对位置可能发生变化。
逻辑：第一遍，取一个元素作为基准，从序列两
端找小于基准的元素交换到前面位置，大于基准
的元素交换到后面位置，直到找到中间位置就是
应该存放基准的位置。第二遍对基准左右两个乱
序的子序列继续快速排序。
void QuickSort(ElemType A[],int n){
if(low<high){
//一趟划分得到基准应在的中间位置。
int pivotpos=Partition(A,low,high);
//左子序列
QuickSort(A,low,pivotpos-1);
//右子序列
QuickSort(A,pivotpos+1,high);
}
}
int Partition(ElemType A[],int low,int high){
ElemType pivot=A[low];
while(low<high){
//都大于基准只调整high指针往前移动
while(low<high&&A[high]>=pivot){
--high;
}
//直到A[high]小于基准则交换位置。
A[low]=A[high];
//都小于基准只调整low指针往后移动
while(low<high&&A[low]<=pivot){
++low;
}
//直到A[low]大于基准则交换位置。
A[high]=A[low];
}
//n轮交换完毕，两个端点指针重合了。此位置
为基准所在位置
A[low]=pivot;
return low;
}
选择排序
基本思想
第i躺后有n-i+1个待排序的元素，选出最小的放在
第i个位置上，直到走完n-1躺，只剩下一个元
素。
简单选择排序
一、不稳定，待排序与第i个位置的相同元素之一
一交换，相对位置可能发生变化。
二、时间复杂度O(n^2);空间复杂度O(1)。
三、逻辑：基于选择排序的基本思想，每次选择
出待排序中最小的放到固定位置。
void SelectSort(ElemType A[],int n){
for(i=0;i<n-1;i++){//第i+1躺
//min为待排序序列中最小元素对应的位置。
min=i;
//从i到n-1号元素中找到最小的元素位置给min
赋值
for(j=i+1;j<n;j++){
if(A[j]<A[min]){
min=j;
}
}
if(min!=i){
//将第i号位与最小位置元素进行交换。
swap(A[i],A[min]);
}
}
}
堆排序
一、稳定性，不稳定。
二、时间复杂度O(nlog2(n))，建堆O(n),调整堆
O(h),h=log2(n)；空间复杂度为O(1)，空间不随
问题规模n的增大而增大是个常量。
逻辑：看代码吧，，首先构造大根堆数组，构造
完成之后，将堆顶元素和最小元素交换，排到数
组末尾，数组长度-1，继续调整除了排好的最大
元素外的数组，再次调整大根堆又选出第二个堆
顶元素，即最大值，排到数组末尾。
调整大根堆逻辑：看代码注释把
数组从1开始存储元素，0号位为暂存元素位置。
索引为i的结点，父结点索引为i/2，左孩子为(
2i)，右孩子为(2i+1);最后一个结点下标为元素总
量n。
堆：完全二叉树且父节点>左右孩子结点值
//建立大根堆
void BuildMaxHeap(ElemType A[],int len){
//i是最后一个叶结点的父结点,调整最底层的子
树
//调整树从n/2开始直到1；
for(int i=len/2;i>0;i--){
HeadAdjust(A,i,len);
}
}
//把数组调整成大根堆
void HeadAdjust(ElemType A[],int k,int len){
A[0]=A[k];//暂存根结点的值，又是空0号位从1
开始存储
//调整根结点和左右结点的最大值，
//如果有交换调整，向下继续调整刚换过根结点
的子树。
for(i=2*k;i<=len;i*=2){
//左右结点挑选大的值位置为i；
if(i<len&&A[i]<A[i+1]){
i++;
}
if(A[0]>A[i]){//根结点最大
break;
}else{
A[k]=A[i];//将父节点调整为最大值。
k=i;//被交换的左孩子或者右孩子作为下一个根
节点
}
}
//最开始的暂存的值也要交换回去，避免频繁交
换了。
A[k]=A[0];
}
//堆排序入口
void HeapSort(ElemType A[],int len){
BuildMaxHeap(A,len);
//n-1趟，大顶堆堆顶元素交换到数组末尾。
for(i=len;i>1;i--){
Swap(A[i],A[1]);
HeadAdjust(A,1,i-1);
}
}
归并排序
基本思想
与交换选择思想不同，归并指将两个多个有序表
合并成一个有序表。
ElemType *B=(ElemType *)malloc((n+1)*
sizeof(ElemType));
void Merge(ElemType A[],int low,int mid ,int
high){
//low-mid有序和mid+1-high有序
//整体无序的A复制到B。
for(int k=low;k<=high;k++){
B[k]=A[k];
}
//k++后移。第二趟循环即下次比较该放到第二
个位置上了。
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
//比较两个有序子序列的最小值,放到A的第一个
位置上。
//最小值指针后移。
if(B[i]<=B[j]){
A[k]=B[i++];
}else{
A[k]=B[j++];
}
}
//例第一个子序列小居多，所以第一个序列放置
到A中位置放完了，
//第二个子序列剩下的都是大的了。
//所以将第二个子序列的值，依次排放到A中k后
移一位的位置。
//最后一次循环内执行了i++或j++没执行k++,需
要先k后移，再赋值。
while(i<=mid){
A[k++]=B[i++];
}
while(j<=high){
A[k++]=B[j++];
}
}
//递归，先分割到元素为1，每次先处理一半
void MergeSort(ElemType A[],int low,int mid,
int high){
if(low<high){
int mid=(low+hight)/2;
MergSort(A,low,mid);
MergSort(A,mid+1,high);
Merge(A,low,mid,high);
}
}
一、时间复杂度：O(nlog2(n))，每一趟时间复杂
度为n，需要处理log2(n)躺，即二叉树树高，多
路归即k叉树树高，[logk(n)]向上取整，每趟时间
复杂度还是n；空间复杂度O(n)。
二、稳定性：稳定。相同元素在不同子序列中，
位置不会改变，在相同子序列中也不会改变。
基数排序
基数为r，需要借助r个辅助链队列，
一、时间复杂度：O(d(n+r))需要排序d趟按个十
百就是三趟，每趟分到链队列上复杂度为n，从r
个队列上依次拿到链表上复杂度为r。空间复杂
度：O(r)。
二、稳定性，稳定，只比较大小，相同元素在前
面的先进先出，最后还是排在前面。
多关键字：①最高位优先：将序列按照第一位大
小分成若干个第一位递增的子序列，对每个子序
列进行第二位大小的分配。直到每一位都分完，
此时每个子序列都排好序了，将他们连接起来即
可。②最低位优先：r个队列，将序列只看低位放
入相同队列，将队列中元素收集到链表里，这一
趟按照最低位大小递增把所有元素排了序。第二
躺再按照次低位排序。
内部排序算法的比较和应用
附表
-------------------------------------------------------------------------------------------------------
算法种类--|---------------------时间复杂度----------------------------|空间复杂度--------|稳定性
-------------------------------------------------------------------------------------------------------
-----------|最好----------------|平均----------------|最坏-------------|平均--------------|--------
-------------------------------------------------------------------------------------------------------
直接插入--|O(n)----------------|O(n^2)-------------|O(n^2)-------------|O(1)----------------|Y
冒泡------|O(n)----------------|O(n^2)-------------|O(n^2)-------------|O(1)----------------|Y
简单选择--|O(n^2)-------------|O(n^2)-------------|O(n^2)-------------|O(1)----------------|F
希尔------|------------------ -|--------------------|--------------------|O(1)----------------|F
快排------|O(nlog2(n))--------|O(nlog2(n))---------|O(n^2)-------------|O(log2(n))----------|F
堆--------|O(nlog2(n))--------|O(nlog2(n))---------|O(nlog2(n))--------|O(1)-----------------|F
2路归并---|O(nlog2(n))--------|O(nlog2(n))--------|O(nlog2(n))--------|O(n)-----------------|Y
基数------|O(d(n+r))-------- --|O(d(n+r))-----------|O(d(n+r))----------|O(r)-----------------|Y
比较
时间复杂度
直接插入、简单选择、冒泡平均都是n^2,简单排
序根序列初始初始有序状态无关。希尔适用大规
模数据量的排序，没有时间复杂度。。堆排建堆
在线性时间，排序在n*log2(n)内完成，综合起来
n*log2(n);快排基于分治的思想即使用递归，平
均性能n*log2(n),实际应用中常优于其他算法。
归并基于分钟思想，与初始序列是否乱序的厉害
没有关系，性能始终为O(log2(n))
空间复杂度
简单选择，直接插入、冒泡、希尔都是常数辅助
空间，快排需要递归栈，最坏n，平均log2(n)。
2路归并需要借助多个辅助空间用于序列的分裂
O(n)。。
稳定性
插入、冒泡、归并、基数稳定，，
简单选择、希尔、快排、堆不稳定
过程特征
考题经常给出初始序列，和部分排序的序列，问
采用的何种排序。冒泡和堆都会产生最大值最小
值，快排一趟能确定一个元素的最终位置。
应用
选择考虑因素
待排序元素的规模n
元素本身信息量大小(大需要移动次数小)
关键字的构造及其分布情况
稳定性要求
语言工具条件，存储结构以及辅助空间的大小。
小结
n较小，直接插入，简单选择，记录信息量大用
简单选择，比较次数小。
初始状态基本有序，用直接插入和冒泡
n大。快排，堆排，归并。
基于比较的排序算法中，每次比较过后，出现两
种可能的转移，可用二叉树来描述判定的过程，
则，当n随机分布时，任何基于比较的算法，都
至少需要O(n*log2(n))的时间，因为树高最矮为
log2(n)
n很大，关键字位数较少且可以分解，采用基数
排序
记录本身信息量大，避免大量移动，可以用链表
存储元素。
外部排序(内外存交互)
相关概念
外存数据一部分一部分的读入内存，在内存中排
序，数据写入外存。外存->输入缓冲区->输出缓
冲区->外存。
文件按块存储在磁盘上，操作系统也是在磁盘上
读写，读写操作远超过内存运算的时间，所以时
间效率主要考虑访问磁盘I/O的次数。
归并排序法
①构建数据的初始状态。根据内存缓冲区的大
小，将外存的文件分为若干长度的子文件。依次
读入内存用内部排序的方法对每个子文件进行排
序，将有序子文件(归并段或顺串)写回外存。②
对这些归并段进行逐趟归并，使归并段逐渐由小
变大，直到整个文件有序为止。
例子
例2000记录的文件，每个磁盘块容量为125个记
录，输入缓冲区有两个，即可生成250记录容量
的有序段。依次250 250的逐步读入内存并排好
每个250段。得到8个初始的归并段。后续将每个
归并段合二为一。k路归并就合k为一。
算一下磁盘IO次数。
2000个记录首次内部排序读入8次有两个输出缓
冲区，写出共16次有一个输出缓冲区，即16*2=
32次读写操作；归并操作每一次合二为一完成全
部输出到外存后，读了16个小块，因为输入缓冲
区就这么大，写出的输出缓冲区也是125，所以
还是16*2=32次读或写操作。一共归并
多少次？归并相当于反着的完全二叉树，树高-1
即为归并的次数，8个有序段合为一个，8/2/2/
2=1，三次/2操作即归并。IO次数 16*2*3+32（
初始内部排序）=128次读写。若改为4路归并排
序。8/4/2=1两轮归并可得到一个有序文件。总
IO次数为16*2*2+32=96。
结论
对r个初始归并段，做k路平衡归并，第一趟为[r/
k]（向上取整）个归并段。第二趟归并后将得到[[
r/k]/k](向上取整)个归并段。直到形成一个。即
树高h-1 =[logk(r)]向上取整=归并次数。
提高外部排序速度，减少归并段数r，增大归并路
数k，都会减少IO次数。
多路平衡归并与败者树
多路归并排序
增加归并路数，会减少io次数，但内部归并排序
会增加比较次数，受到路数的影响，时间复杂度
会增加。
每趟归并排序从k路取归并段首位元素，选出最小
值，要比较k-1次。最小值所在归并段往前递第二
个元素，再次参与选最小值。一共需要选n-1次，
每次都要与其他路元素比较，最坏情况是k-1次。
将k路合为一路需要比较(n-1)(k-1)次，形成有序
文件一共有logk(r)次归并操作。总比较次数为
logk(r)*(n-1)(k-1)。
败者树(挑选出最小值)
为了不使内部归并随着k的增长而而增长，不能使
用普通的内部归并排序。引入了败者树结构。
创建过程：取k个归并段的首位元素添加父结点，
父结点存储元素k路编号，形成k个树，选中两个
树，比较元素大小，元素大的父结点作为两个子
树合并后的根结点，关键字小的作为合并两个子
树后根结点的根结点；逐步把k个树合并成一个
树，根结点可以输出最小元素。之前最小元素所
在的归并段需要提供下一个元素顶替最小元素的k
编号。重新调整败者树，继续输出最小元素。
置换选择排序
起因
为了减少归并的趟数，可以减少初始归并段个数
r。除了最后一个归并段，每个归并段长度都相
同，长度依赖于内部排序时使用的可用内存工作
区的大小(例两个输入缓冲区)。需要产生更长的
初始归并段，这就是置换选择算法的目的。
过程
令FI代表初始待排的文件，FO代表初始归并段输
出文件，内存工作区为WA，大小为w。FO和WA
为空。
步骤：1.FI中输入w个记录到WA中。充满内存。
2.从WA中选出最小记录，输出到FO中，记为
MINIMAX标记。
3.FI继续输出下一个记录到WA。填满内存。
4.从WA中所有比MINIMAX大的记录中选出最小
的记录，作为新的MINIMAX，并输出到FO中。
5.重读3-4，直到WA中选不出新的MINIMAX为
止 ，由此一个初始归并段已经得到，输出一个结
束标志到FO中。
6.重复2-5。得到全部初始归并段。
在WA中选择MINIMAX记录需要利用败者树来实
现。
最佳归并树
起因
置换选择之后得到长度不等的初始归并段，将初
始归并段再次归并时，IO次数随着归并策略的不
同而不同。
例：2 3 6 9 12一共五个初始归并段，值代表归
并段长度，进行3路归并，6，9，12形成27的归
并段，2，3，27形成32的归并段，归并结束。
比较次数为（2*1+3*1+6*2+9*2+12*2）*2=108
每个初始归并段长度*自身参与归并的趟数加和，
由于读写操作，再乘2。发现越短的初始归并段
最后参与归并即参与归并趟数少一些时，总io次
数就会越少。
过程
根据每个初始归并段的长度做一个哈夫曼树。
即，最小值对应路径最长，最大值结点对应路径
最短。
算法实现设计(不考)
评论0