• 第8章-排序

    目录

    插入排序

    直接插入排序

    折半插入排序

    希尔排序

    交换排序

    冒泡排序

    快速排序

    选择排序

    简单选择排序

    堆排序

    归并排序

    待补充

    基数排序

    内部排序算法比较

    内部排序算法应用

    外部排序方法

    多路平衡归并与败者树

    置换-选择排序（生成初始归并段）

    最佳归并树

    插入排序

    每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列。

    直接插入排序

    查找出L(i)在L[1,...,i-1]中的插入位置k

    将L[k,...,i-1]中所有元素依次后移一个位置

    将L(i)复制到L(k)中

    1. void InsertSort(ElemType A[],int n){
    2. 	int i,j;
    3. 	for(i=2;i<=n;i++)//依次将A[2]~A[n]插入到前面已排序序列 
    4. 		if(A[i]-1]){//若 A[i]关键码小于前驱，将A[i]插入有序表 
    5. 			A[0]=A[i];//复制为哨兵，A[0]不存放元素 
    6. 			for(j=i-1;A[0]//从后往前 查找待插入位置 
    7. 				A[j+1]=A[j];//向后挪位 
    8. 			A[j+1]=A[0];//复制到插入位置 
    9. 		}
    10. }

    空间O(1)

    时间  最好O(n)，最坏O(\sum_{i=2}^{n}(i+1))，平均O(\frac{n^{2}}{4}).

    折半插入排序

    1. void InsertSort(ElemType A[],int n){
    2. 	int i,j,low,high,mid;
    3. 	for(i=2;i<=n;i++){//依次将A[2]~A[n]插入到前面已排序序列 
    4. 		A[0]=A[i];//将A[i]暂存到A[0]
    5. 		low=1，high=i-1;//折半查找范围
    6. 		while(low<=high){//折半查找 默认递增有序 
    7. 			mid=(low+high)/2;
    8. 			if(A[mid]>A[0])high=mid-1;
    9. 			else low=mid+1;
    10. 		} 
    11. 		for(j=i-1;j>=high+1;--j)
    12. 			A[j+1]=A[j];//统一后移元素，空出插入位置 
    13. 		A[high+1]=A[0]; 
    14. 	}
    15. }

    减少了比较元素的次数，约为O(nlog_{2}n)，与待排序表的初始状态无关，仅与个数n有关。

    移动次数未改变，与待排序表的初始状态有关，所以折半插入排序O(n^{2})

    希尔排序

    缩小增量排序

    1. void shellSort(ElemType A[],int n){
    2. 	//A[0]只是暂存单元，不是哨兵，当j<=0,插入位置已到
    3. 	for(dk=n/2;dk>=1;dk=dk/2)//步长变化
    4. 		if(A[i]//需要将A[i]插入有序增量子表 
    5. 			A[0]=A[i];//暂存在A[0] 
    6. 			for(j=i-dk;j>0&&A[0]
    7. 				A[j+dk]=A[j];//记录后移，查找插入的位置 
    8. 			A[j+dk]=A[0];//插入 
    9. 		} 
    10. }

    空间O(1)

    时间约O(n^{1.3})，最坏O(n^{2})

    仅适用于线性表为顺序存储，且不稳定算法。 

    交换排序

    冒泡排序

    1. void BubbleSort(ElemType A[],int n){
    2. 	for(i=0;i-1;i++){
    3. 		flag=false;//表示本趟冒泡是否发生交换的标志
    4. 		for(j=n-1;j>i;j--)//一趟冒泡过程
    5. 			if(A[j-1]>A[j]){
    6. 				swap(A[j-1],A[j]);
    7. 				flag=true;
    8. 			} 
    9. 	if(flag==false)
    10. 		return ;//已经有序 
    11. 	}
    12. }

    空间O(1)

    时间最坏O(n^{2})

    快速排序

    是所有内部排序算法中平均性能最优的排序算法。

    数据结构课程PPT，非常全面
    rar 2星 超过35%的资源 14.53MB
    下载
    1. void QuickSort(ElemType A[],int low,int high){
    2. 	if(low//递归跳出条件 
    3. //Partition()就是划分操作，将表A[low...high]划分为满足上述条件的两个子表 
    4. 		int pivotpos=Partition(A,low,high);//划分
    5. 		QuickSort(A,low,pivotpos-1);//依次对两个子表进行递归
    6. 		QuickSort(A,pivotpos+1,high);	 
    7. 	}
    8. }
    9. int Partition(ElemType A[],int low,int high){//一趟划分 
    10. 	ElemType pivot=A[low];//将当前表中第一个元素设为枢轴，对表进行划分
    11. 	while(low
    12. 		while(low=pivot)--high;
    13. 		A[low] =A[high];//将比枢轴小的元素移动到左端
    14. 		while(low
    15. 		A[high] =A[low];//将比枢轴大的元素移动到右端
    16. 	} 
    17. 	A[low]=pivot;//将枢轴元素放到最终位置
    18. 	return low;//返回存放枢轴的最终位置 
    19. }

    空间 最好 O(log_{2}n)，最坏O(n)，平均O(log_{2}n)

    时间最坏 O(n^{2})，平均O(nlog_{2}n)

    选择排序

    简单选择排序

    第 i 趟排序即从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟可以确定一个元素的最终位置。

    1. void SelectSort(ElemType A[],int n){
    2. 	for(i=0;i-1;i++){//n-1趟 
    3. 		min=i;//记录最小元素位置 
    4. 		for(j=i+1;j
    5. 			if(A[j]//更新最小元素位置 
    6. 		if(min!=i)swap(A[i],A[min]);
    7. 	}
    8. }

    空间O(1)

    时间 O(n^{2})  

    堆排序

    建立大根堆 O(n)

    1. void BuildMaxHeap(ElemType A[],int len){
    2. 	for(int i=len/2;i>0;i--)//从i=[n/2]~1，反复调整堆 
    3. 		HeadAdjust(A,i,len);
    4. } 
    5. void HeadAdjust(ElenmType A[],int k,int len){
    6. 	//函数HeadAdjust将元素k为根的子树进行调整
    7. 	A[0]=A[k];//暂存子树的根结点
    8. 	for(i=2*k;i<=len;i*=2){//沿key较大的子结点向下筛选 
    9. 		if(i1])
    10. 			i++;//取key较大的子结点的下标
    11. 		if(A[0]>=A[i]) break;//筛选结束
    12. 		else {
    13. 			A[k]=A[i];//将A[i]调整到双亲结点上 
    14. 			k=i;//修改k值，以便继续向下筛选 
    15. 		} 
    16. 	} 
    17. }

    堆排序算法

    1. void HeapSort(ElemType A[],int len){
    2. 	BuildMaxHeap(A,len);//初始建堆
    3. 	for(i=len;i>1;i--){//n-1趟的交换和建堆过程
    4. 		Swap(A[i]),A[1]);//输出堆顶元素（和堆底元素交换）
    5. 		HeadAdjust(A,1,i-1);//调整，把剩余i-1个元素整理成堆 
    6. 	} 
    7. }

    空间O(1)

    时间O(nlog_{2}n) 

    归并排序

    Merge( )：将前后相邻的两个有序表归并为一个有序表。

    1. ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));//辅助数组B
    2. void Merge(ElemType A[],int low,int mid,int high){
    3. //表A的两段A[low..mid]和A[mid+1..high]各自有序，将他们合并成一个有序表
    4. 	for(int k=low;k<=high;k++)
    5. 		B[k]=A[k];//将A中所有元素复制到B中 
    6. 	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
    7. 		if(B[i]<=B[j])//比较B的左右两段中的元素 
    8. 			A[k]=B[i++];//将较小值复制到A中 
    9. 		else A[k]=B[j++]; 
    10. 	} 
    11. 	while(i<=mid)A[k++]=B[i++];//若第一个表未检测完，复制
    12. 	while(j<=high)A[k++]=B[j++]; 
    13. }

    合并：合并两个已排序的子表得到排序结果。

    1. void MergeSort(ElemType A[],int low,int high){
    2. 	if(low
    3. 		int mid=(low+high)/2;
    4. 		MergeSort(A,low,mid);//对左侧子序列进行递归排序 
    5. 		MergeSort(A,mid+1,high);
    6. 		Merge(A,low,mid,high);//归并 
    7. 	}
    8. }
    林碧英《数据结构》复习题及参考答案.zip
    zip 1星 超过10%的资源 2.74MB
    下载

    待补充

    基数排序

    内部排序算法比较

    内部排序算法应用

    1 )选取排序方法需要考虑的因素
    待排序的元素数目n。

    元素本身信息量的大小。

    关键字的结构及其分布情况。

    稳定性的要求。
    语言工具的条件,存储结构及辅助空间的大小等。

    2〉排序算法小结
            若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动
    次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
            若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
            若n较大，则应采用时间复杂度为O(nlog_{2}n)的排序方法:快速排序、堆排序或归并排
    序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为O(nlog_{2}n)，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。
            在基于比较的排序方法中,每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明:当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog_{2}n)的时间。
            若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。
            当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

    外部排序方法

    外部排序指待排序文件较大，内存一次放不下，需存放在外存的文件的排序。

    为减少平衡归并中外存读写次数所采取的方法:增大归并路数和减少归并段个数。
    利用败者树增大归并路数。
    利用置换-选择排序增大归并段长度来减少归并段个数。
    由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树。

    多路平衡归并与败者树

    置换-选择排序（生成初始归并段）

    最佳归并树

  • 相关阅读:
    Matlab图像处理基础(2)：区域处理，边沿检测
    营销经理提问常用的ChatGPT通用提示词模板
    基于Java+SpringBoot+Thymeleaf+Mysql疫情疫苗预约系统学习系统设计与实现
    el-input限制输入整数等分析
    C++基础特性
    为啥 Erlang 没有像 Go、Scala 语言那样崛起？
    复现XSS漏洞及分析
    【UE5.3】笔记4-自定义材质蓝图
    20240417，友元 FRIEND
    纵行科技亮相2023汽车物流行业年会，与菜鸟共推ZETag资产管理方案
  • 原文地址：https://blog.csdn.net/qq_45181299/article/details/126134744