[数据结构与算法]记录数据结构的学习013

(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）

散列表（哈希表）：数据元素的关键字与其存储地址直接相关

若通过散列函数映射到同一个值，称之为同义词，如果目标位置已经被占，则冲突

处理冲突的方法——拉链法：把所有同义词放在一个链表中

装填因子（ASL失败）：

无元素格记为查找次数0，有1个元素格记为1，有多个元素（同义词）的记为1+2+...+n，故装填因子a=记录数/散列表长度

状态因子记为查找失败的平均查找长度，越大代表冲突越多

常见的散列函数：

除留取余法：H(key) = key % p

散列表表长为m，取一个不大于m但最接近或等于m的质数p

当关键字随机时，用质数p可以使得分布更均匀，冲突更少，装填因子更小

直接定址法：H(key) = key 或?H(key) = a* key + b

这种方法不会冲突，适合关键字的分布基本连续的情况

数字分析法：选取数码分布较为均匀的若干位作为散列地址（例如使用手机号后四位的数字来区分）

平方取中法：取关键字的平方值的中间几位作为算列地址。这种方法得到的散列地址与关键字的每一位都有关系，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数，分布均匀

处理冲突的方法——开放地址法：

Hi = ( H ( key ) + di ) % m

?i 表示第 i 次发生冲突，m为散列表表长，di为增量序列

1.线性探测法：di=0，1，2，3...m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空

查找线性探测法的哈希表时，先将试图查找的元素按照哈希函数计算地址后，再进行比对，如果不是，即地址+1后再比对，以此类推，直至遇到空位置，查找失败。

删除线性探测法的哈希表时，删除一个元素时，不能将其置为空，会导致查找时误以为失败，需要将已删除结点进行逻辑删除（即不置空，只标记一下此为空）

此方法的ASL比较高，效率比较低

2.平方探测法（二次探测法）：di=02，12，-12，22，-22，...，k2，-k2（k<=m/2)

散列表长度m必须为一个可以表示成 4J+3的素数，才能探测到所有位置

3.伪随机序列法：di是一个伪随机序列，如di = 0，45，24，11...

再散列法：除了原始的散列函数以外，再多准备几个散列函数，当冲突时，用下一个散列函数计算一个新地址，直到不冲突为止。

排序：将关键字按照递增或递减顺序进行排列

排序算法稳定性：当相同关键字进行排序后，其之间顺序仍能保持排序前的相对顺序，即稳定。

稳定的排序算法不一定比不稳定的好，看需求。

内部排序：数据都在内存中（关注算法的时间空间复杂度）

外部排序：数据太多，无法全部存入内存（还要关注磁盘读写次数）

插入排序：每次将一个待排序元素按其关键字大小，与前面排好序的子序列进行一一对比后排序，直到全部插入完毕。

void InsertSort(int A[], int n){
	int i,j,temp;
	for(i=1;i<n;i++){			//将各元素插入已排好序的序列中
		if(A[i]<A[i-1]){		//若A[i]关键字小于前驱
			temp=A[i];			//用temp暂存A[i]
			for(j=i-1;j>=0 && A[i]>temp;--j)//检查所有前面已排好序的元素
				A[j+1]=A[j];	//所有大于temp的元素都向后挪位
			A[j+1]=temp;		//复制到插入位置
		}
	}

空间复杂度：O(1)

时间复杂度：最好情况：原本就有序，每趟只需要对比前驱即可，不用处理元素。O(n)

? ? ? ? ? ? ? ? ? ? ?最坏情况：原本逆序排放，每趟都需要对比整个有序子序列。O(n2)

? ? ? ? ? ? ? ? ? ? ?平均时间复杂度：O(n2)

优化插入排序——折半插入排序：先用折半查找找到应该插入的位置，再移动元素（向前一一比对变为折半查找）

带哨兵的折半插入排序（A[0]为哨兵，空出存放待排序元素

void InsertSort(int A[],int n){
	int i,j,low,hign,mid,temp;
	for(i=2;i<=n;i++){			//已排序完毕的存入A[1]到A[i-1]中
		A[0]=A[i];				//将A[i]暂存到temp里面
		low=1;hign=i-1;			//设置折半范围
		while(low<=high){		//折半查找
			mid = (low+high)/2;	//取中间点	
			if(A[mid]>A[0])		//查找左半边
				hign=mid-1;
			else				//查找右半边
				low=mid+1;
		}
		for(j=i-1;j>=high+1;--j)	
			A[j+1]=A[i];		//统一后移动元素，空出插入位置
		A[high+1]=A[0];			//插入操作
	}
}

当low大于high时折半查找停止，应该将low到i-1内的元素全部右移，并且将A[0]复制到low所指位置，当A[mid]==A[0]时，为了保证算法的稳定性，应继续在mid所指位置右边寻找插入位置