晨起开门雪满山，雪晴云淡日光寒。
上篇文章介绍了两种数据结构,数组与集合,集合与数组特性基本相同,不同的是集合中的元素是不能相同的.所以在执行插入的时候,集合比数组多了一步”查重”的操作,这是一个遍历所有元素的操作,这是一个很优秀的特性,比如你列了一个单子去超市买东西,你当然不想买重复的东西.
算法为何重要
虽然数组与集合数据结构相似,但是在高负荷的环境下它们的性能也可能表现的天差地别.为什么呢?因为除了数据结构影响性能之外还有一个重要的因素也影响这程序的性能,那就是算法.
算法,指的是解决某个问题的办法,也有的说是解决问题的一套流程.
比如把大象放进冰箱需要几个步骤?这里的”几个步骤”指的就是算法.
上一篇文章中介绍了4种数据的操作:”读取,查找,删除,插入”,在本文章种仍会提到,但是本文在提到的时候,会带上算法,即用什么算法来实现这4种操作会更快.
上篇文章中介绍的数组,我们称之为”常规数组“,这里再介绍一种新的数据结构:”有序数组“,有序数组比一般数组多了一个限定,即数组中的元素是有顺序的,如果要在有序数组中插入一个元素,这个元素不是用户通过下标来确定这个元素在数组中的位置.而是通过比较将值插入在合适的位置.
例如下面的有序数组
|
1 |
2 |
3 |
4 |
6 |
7 |
|---|
现在要插入5这个元素,我们不能随便找个位置插入,因为那样这个数组的数据结构就变成了常规数组,所以我们要挨个比较:
5与1比较,比1大,应该是在1的右边
5与2比较,比2大,应该是在2的右边
…
5与6比较,比6小,应该是在6的左边
所以,将6的位置让给6,6与6后面的元素全部向后移一个单位.
至此,一个有序数组的插入操作完成.
虽然有序数组的插入在性能方面比不上常规数组,但是在查值方面,有序数组有着特殊优势
上篇文章介绍的查找方式是线性查找,即从开头按顺序查找,直到找到,比如在下面的常规数组中查找一个元素10,我们人眼一眼就可以看到,这个常规数组中根本不存在这个值,但是计算机没有眼睛,它仍旧会从左查到右.查完了告诉用户:这个数组中没有这个值,即这个程序做了7个步骤(对比大小对比了7次).
|
9 |
52 |
77 |
100 |
201 |
99 |
2 |
|---|
那么假如把上面的常规数组元素排序变成有序数组呢?
|
2 |
9 |
52 |
77 |
99 |
100 |
201 |
|---|
那么当程序在比较到52的时候它就会知道这个有序数组中没有10这个元素,为什么呢?因为有序的话,10不可能出现在52的右边.当程序得出这个结论的时候,程序一种操作了3次对比.
那么加入是最坏的情况呢?就是说在上面的有序数组中查找1000这个值,或者就是查找最大的值.线性查找仍旧会操作7次,然后得出结论,该元素在最后或者根本不存在.
这样看来,是不是就是说有序数组和常规数组基本差不多呢?因为我们在考虑程序做了几个步骤的时候一般都是考虑到最坏的情况(后续文章中的大O记法会有介绍).有序数组和常规数组在线性查找方面在最坏的情况下是同样的操作.
那是因为数据结构没有和算法相结合,线性查找算法不适合用在有序数组上,那么,什么方法会比线性查找快呢?
二分查找
如果我告诉你我心里想一个数字,这个数字在1-10之间,如果你猜错了我会告诉你往大了猜或者往小了猜,请问你最快说几次能猜出来.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|---|
第一次猜5
提示你要猜大一点
|
6 |
7 |
8 |
9 |
10 |
|---|
第二次猜8
提示你要猜小一点
|
6 |
7 |
|---|
猜6
提示你要猜大一点
所以这个数字是7.
有序数组和常规数组相比较,有序数组不仅仅能用线性查找,它也可以使用二分查找,因为常规数组的元素没有规律可言,所以常规数组是不能用二分查找的.
二分查找的实现:
public class NewBehaviourScript : MonoBehaviour
{
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
private void Start(){
BinarySearch(array, 6);
}
void BinarySearch(int [] array ,int seachNum)
{
int start = 0;
int end = array.Length - 1;
int middle;
while (start <=end )
{
middle = (start + end) / 2;
if (array[middle] > seachNum)
{
end = middle - 1;
}
else if (array[middle] < seachNum)
{
start = middle + 1;
}
else if (array[middle] == seachNum)
{
Debug.Log("Find it");
return;
}
}
Debug.Log("Not found ");
return;
}
}对于长度很小的数组,二分查找并不比线性查找好多少,但是我们来看更大的数组,比如一个长度为100的数组,如果常规数组,在最坏的情况下查找一个数,将会是100步,那么如果是有序数组的话,最坏的情况下,查找的步数是7步.
二分查找每次查找都会排除掉一半的数组.那么二分查找有规律吗?下面来看.
如果是长度为3的有序数组,二分查找所需要的是2步
如果是长度为7的有序数组,二分查找所需要的是3步
如果是长度为15的有序数组,二分查找所需要的是4步
….
其实为了好查找我把数组的长度*2并加上1,因为单数长度的数组可以很容易的找到中间的值.从上面可以看出来长度每增加一倍加一,步数只增加1步.
规律如下图:
如果数组变得更大,长度到了10000,使用二分查找的话,最坏的情况下只有14步,现在你应该明白数据结构+算法=高效的程序.
其实也有一种说法,算法+数据结构才叫编程.
不过虽然有序数组查找很快,但是在插入方面却比常规数组要慢了许多,所以在衡量要不要用有序数组时一定要酌情考虑.
总结
关于算法的初级入门介绍就是这两篇内容,很多时候,做同样的一种功能会有许多不一样的实现方式,换一种算法可以极大的提高程序运行效率.
同时,你也应该意识到,世界上没有哪一种算法适用于任何一个场景,你不能因为看到了有序数组查找比常规数组快,就永远用有序数组,还是那句话,在使用前要酌情考虑.还有一点值得提的是,比较算法适合不适合的方法就是计算步数,而这个步数一定是最坏的情况.
接下来的文章就是讲解规范的描述数据结构和算法的时间复杂度,有了通用的表达式后,就可以更容易的知道在哪些场景下该使用哪些算法.