数据结构期末复习五：内部排序

2023-05-16

排序的基本概念和分类

排序：将杂乱无章的数据按关键字递增（或递减）有序排列

假设Ki=Kj，排序前Ri领先于Rj
稳定排序：排序后的序列Ri仍领先于Rj
不稳定排序：排序后的序列Rj领先于Ri

时间开销：关键字比较次数和记录移动次数

内部排序：待排序记录存储在随机存储器中
外部排序：待排序记录数量很大，需对外存进行访问

待排序的顺序表的数据结构：

#define MAXSIZE 20

typedef int KeyType;
typedef struct{
	KeyType key;//关键字 
	InfoType otherType;
}RecType;//记录类型 

typedef struct{
	RecType  r[MAXSIZE+1];//r[0]为哨兵项
	int length;
}SqList;

一、插入排序

将待排序的记录按其关键字大小插入已排好的子表中的适当位置

直接插入排序

1.令第一个元素作为初始有序表
2.依次插入一个元素构造新的有序表

//直接插入法 
void InsertSort(SqList &L){ 
	for(int i=2;i<L.length;i++){
		if(L.r[i].key<L.r[i-1].key){
			L.r[0]=L.r[i];
			L.r[i]=L.r[i-1];
		
		for(int j=i-2;L.r[j].key>L.r[0].key;i--){
			L.r[j+1]=L.r[j];
		}
		L.r[j+1]=L.r[0];
		}
	}
}

算法分析：
1.1个辅助空间r[0]
2.最好情况（正序）：
关键词比较次数：n-1
记录不需要移动
3.最差情况（逆序）：
关键词比较次数：(n+2)(n-1)
记录移动次数：(n+4)(n-1)
4.算法时间复杂度O(n^2)
5.稳定

其他排序

2-路插入排序

折半插入排序

//折半插入法
void BInsertSort(SqList &L){
	for(int i=2;i<L.length;i++){
		L.r[0]=L.r[i];
		int low=1;
		int high=i-1;
		while(low<=high){
			mid=(low+high)/2;
			if(L.r[0].key<L.r[mid].key) high=mid-1;
			else low=mid+1;
		}//插入位置为high+1(或low) 
		for(int j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];
		L.r[j+1]=L.r[0];
	}
}

算法分析：
1.比较次数与初始状态无关，依赖于记录个数
2.时间复杂度O(n^2)
3.稳定

表插入排序

不移动记录，只移动指针
每个记录维护一个next指针，构成循环链表

希尔排序

将待排序列中相隔某个增量的记录分为若干子序列进行直接插入排序，待基本有序再进行直接插入排序，

增量序列递减，互为质数，最后一个必须是1

//Shell
void ShellSort(SqList &L,int dlta[],int t){//增量存在dlta[]中 
	for(int k=0;k<t;k++){
		ShellInsert(L,dlta[k]);
	}
}

void ShellInsert(SqList &L,int dk){
	for(int i=dk+1;i<=length;i+=dk){	
		if(L.r[i-dk].key>L.r[i].key){
			L.r[0]=L.r[i];
		for(int j=i-dk;L.r[j].key>L.r[0].key;j-=dk){
			L.r[j+dk]=L.r[j];	
		} 
		L.r[j+dk]=L.r[0];
	}
}

算法分析：
1.不稳定
2.时间复杂度
最好：O（n）
最坏：O（n^2）

二、快速排序

思想：
1.任取一个元素为中心 pivot中心点
2.小的前方，大的后方，形成两个子表（两头向中间交替式逼近法）
3.递归，直到剩一个元素

void QSort(SqList &L,int low,int high){
	if(low<high){
		pivot=Partition(L,low,high);
		QSort(L,low,pivot-1);
		QSort(L,pivot+1,high);
	}
} 

int Partition(SqList &L,int low,int high){
	if(low<high){
		L.r[0]=L.r[low];
		while(low<high&&L.r[0].key<=L.r[high].key){
			high--;
		}
		L.r[low]=L.r[high];
		while(low<high&&L.r[0].key>=L.r[low].key){
			row++;			
		}
		L.r[high]=L.r[low];
	}
	L.r[low]=L.r[0];
	return low;
}
void main(){
	QSort(L,1,L.length);
}

算法分析：
1.时间复杂度：O（nlog2n）
2.空间复杂度：平均O（logn）不是原地排序
递归调用栈的支持，栈的长度取决于栈的深度
3.不稳定
4.不适用于原本有序或基本有序的记录序列进行排列

三、选择排序

简单选择排序

在待排序的数据中选出最大（小的元素）放在其最终的位置
第一趟：n-1次排出最小的
第二趟：n-2次排出次小的
共需n-1趟

堆排序

堆：任一非叶子结点均小于（大于）孩子结点的完全二叉树
小根堆：小于
大根堆：大于

堆排序思想:
输出堆顶最大（小）值；
剩下的元素调整为新的堆

堆调整（筛选）：
小根堆：
1.以堆中最后一个元素代替之
2.根节点与左、右子树的根结点值比较，与其中小者交换
3.重复，直到叶子结点

堆建立：
从最后一个非叶子结点开始调整（依次从序号n/2 、n/2-1……1调整）

//堆排序
void HeapSort(elem R[]){
	int i;
	for(i=n/2;i>=1;i--){
		HeapAdjust(R,i,n);
	}
	for(i=n;i>1;i--){
		Swap(R[1],R[i]);
		HeapAdjust(R,1,i-1);
	}
}

算法分析：
1.时间复杂度：最坏情况下为O（nlog2n）不会最好最坏
2.空间复杂度：O(1)
3.不稳定
4.对元素多时有效

四、归并排序

两个及以上的有序子序列归并为一个有序序列
2-路归并排序：
算法分析：
1.时间复杂度：O（nlog2n）
2.空间复杂度：O(n)
3.稳定

五、基数排序（桶排序/箱排序）

思想：分配+收集
适用于关键字的取值范围一定
算法分析：
1.时间复杂度：O（k*（n+m））
2.空间复杂度：O（n+m）
3.稳定

综合比较

时间性能

时间复杂度为O(nlogn):快速（最好）、归并、堆
O(n^2)：直接插入（最好）、冒泡、简单选择
适合近似有序
O(n)：基数排序

时间复杂度的下限

比较关键字的排序方法最快的时间时O（nlogn）
基数排序除外

空间性能

O（1）：直接插入冒泡简单选择堆
O（logn）：快速排序（栈）
O（n）：归并

稳定性

快速排序和堆排序不稳定

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)