[数据结构与算法]2021-08-04计算机各种算法上

算法：
广义：解决特定问题的方法。
狭义：数据结构具备的功能。

算法的特征：
有穷性：
算法应该在有限步骤内完成。
确切性：
算法的每一步骤必须要有目的性且无歧义。
输入项：指n个输入的值用于算法运算，输入个数可以为0这种情况特指算法本身给定了初始条件举个简单的例子：

void HelloWrold(void)
{
	printf("hello wrold");
}

输出项：
算法应该有一个及以上的输出项，没有输出的算法无意义。算法必须有输出。
可行性：
一个算法必须在现有的条件里可行且符合常理，那些理论上可行的不一定能实现，举个例子：

//计算出100万秒等于多少小时。
void time(void)
{
	//读取当前时间（年月日）time1；
	while(i<1000000)
	{
		sleep(1);
		i++;
	}
	//读取当前时间（年月日）time2；
	time1-time2=100万秒的天数。
}

这个算法确实可以求出100万秒等于多少天，但是正常人都不会这么用，这就是可行性为0；类似于给喜马拉雅山造电梯或给马里亚纳海沟贴瓷砖一样，成功率不为0但是一定不可能发生

算法的评定：正确性、时间复杂度、空间复杂度、可读性、健壮性。
正确性：
一个算法的首要前提是正确性，即结果正确，如果不正确时间复杂度、空间复杂度、可读性、健壮性这些都将毫无意义。

时间复杂度：
一个用于描述算法在执行时，随着输入参数数量的变化，而执次数发生变化的函数。
一般采用大O表示法：O(函数)

常见的时间杂度：
常数阶 O(1)
对数阶 O(logn)
线性阶 O(n)
线性对数阶 O(nlogn)
平方阶 O(n^2)
指数阶 O(2^n)

空间复杂度：
一个用于描述算法在执行时，随着输入参数数量的变化，而需要存储空间发生变化的函数。

常见的空间复杂度：
O(1)、O(n)、O(2n)、O(n^2)

查找算法：
顺序查找：
最简单的一种查找算法，对待查找数据没有要求.
时间复杂度为：O(n)
这是最简单的查找代码如下：

for(int i=0;i<100;i++)
{
	if(a[i]==x)
		return x;
}

二分查找：
效率比较高的一种查找算法，要求待查找数据有序。
时间复杂度：O(logn)
如果有多个符合的数据，返回的下标是不确定的。
部分代码如下：

//假设是升序min初始为0，max初始为100；
if(x<a[mid])
max=(max+min)/2;
if(x>a[mid])
min=(max+min)/2;

哈希查找：
首先要创建哈希表，创建哈希表的前提是对数据有一定了解。
创建哈希表最重要的就是解决数据冲突问题，没有固定统一的方法，要根据数据的特性找到合适的方法。
一旦哈希表创建完成它查找的时间复杂度接近O(1)。
速度虽然很快，但有很大的局限性。
假设有十三个数，同时用7求余，然后根据余数找，对除数没有特别要求，什么合适用什么。找到余数后再具体找值。比如a[10] = {2,3, 4 ,5, 6, 7, 8, 9, 10, 15}
构建哈希表用7求余变成b[10]={2,3,4,5,6,0,1,2,3,1}然后要找的x备份后也求余x=8，y=1，去b[]里找1，找到后对应a中的8，15.这两个里找8，就方便多了。

块查找：
当面对海量数据时，可以根据数据的特性，把数据分块、再分块降低数据规模，再使用以查找算法查找数据。类似于找身份证，找一个身份证码先找开头的地区再出生年月，最后找精确的人，这样就能减少一大部分时间
下面是各种排序。
排序算法：
排序算法的稳定性：
当待排序的数据中有相同的数据，排序算法是否会更改它们的前后关系，不会更改的叫稳定排序，可能会更改的叫不稳定排序。

冒泡：
特点：找到目标值后移动对数据的有序性敏感
是否稳定：稳定
时间复杂度：O(n) O(n^2)
空间复杂度：O(1)
选择：
特点：找到目标之后和目标位交换，数据的交换次数少，如果待排序的数据字节较多，选择排序是一个不错的方案。
是否稳定：不稳定
时间复杂度：O(n^2)
空间复杂度：O(1)
插入：
特点：目标插入到数组，数据的交换次数少，适合对有序的数据添加新的数据。
是否稳定：
是否稳定：稳定
时间复杂度：O(n^2)
空间复杂度：O(1)
希尔：
特点：在插入排序的基础添加增量概念，提高了数据到达合适位置的速度。
是否稳定：不稳定
时间复杂度：O(nlogn)
空间复杂度：O(1)

堆：
特点：把数据看作完全二叉树，然后把这个二叉树调整为大根堆，然后把堆顶的数据交换到末尾，再把二叉树的数量-1，再调整为大根堆，直到二叉树的数量为1，排序完成。
是否稳定：不稳定
时间复杂度：O(nlogn)
空间复杂度：O(1)