广度优先搜索是图的一种算法,一是可以确定有没有到达的路径,而是如果有那么这个路径就是最短路径。就像水波那样,先从原点向周围一圈一圈的搜索(假设一圈有好多数据),没有才向更外圈搜索。
class Vertex { public string data; public bool isVisited; public Vertex(string d) { data = d; isVisited = false; } } class Program { static Dictionary<string, Vertex[]> dict = new Dictionary<string, Vertex[]>(); static void Main(string[] args) { Vertex A = new Vertex("Bom"); Vertex B = new Vertex("Tom"); Vertex C = new Vertex("Chicai"); Vertex D = new Vertex("Marry"); //构建关系图,谁是谁的好友 //I是原点,AB为第一圈,D为第二圈,C为第三圈 dict.Add("I", new Vertex[] { A, B }); dict.Add("Bom", new Vertex[] { D }); dict.Add("Tom", new Vertex[] { D }); dict.Add("Marry", new Vertex[] { A,B,C }); dict.Add("Chicai", new Vertex[] { D }); Search("Chicai"); Console.ReadKey(); } static void Search(string name) { Queue<Vertex> queue = new Queue<Vertex>(); Vertex[] datas; dict.TryGetValue("I", out datas); foreach (Vertex x in datas) { queue.Enqueue(x); } while (queue.Count > 0) { Vertex x = queue.Dequeue(); if (x.isVisited) { continue; } x.isVisited = true; if (x.data == name) { Console.WriteLine("找到了:" + name); return; } else { Console.WriteLine(x.data); Vertex[] vertex; dict.TryGetValue(x.data, out vertex); foreach (Vertex v in vertex) { queue.Enqueue(v); } } } Console.WriteLine("找不到啊"); } }
这里是一个找好友的游戏,通过好友来找好友,例如找一个叫Chicai的好友,首先从我自己这里找AB(Bom,Tom)都不是,那么就将他们的好友也加进队列中进行查找,这时候就有了D(Marry),发现D也不是,那么将Marry的好友也加进队列,这时候才有了C(Chicai),这时候就找到了。如果好友关系网中都没有这个人(那就是队列为空了)。
散列表也叫做字典(哈希),这个就熟悉了吧。它通过将字符串等映射到数组的索引中,实现了通过字符串一下子就查找到目标值O(1)。散列表有着数组,散列函数,通过散列函数将字符串转换成数组对应的索引,一个良好的散列函数会有较少的冲突(就是两个不同的字符串对应到了同一个索引),这时候会在该索引位置生成一个链表,如果链表(冲突)很长,说明这个散列函数不好。散列表的查找、删除、插入等操作都很快,就是填装因子大到一定程度时>0.7(数组的位置不够装了),需要重构散列表时比较耗时。
很典型的一个例子就是DNS的解析,每个域名都对应着一个ip,通过域名查找ip,若是不适用散列表,查找时间为O(n),全世界有多少个域名,想想就觉得可怕。
还有就是网站的缓存,通过域名来获取到对应的缓存页面。
快速排序是一种比选择排序快得多的算法,当然是数据量大的时候,主要思想就是利用一个参考值,将大的组分成两个小的组,一个组都比参考值小,一个组都比参考值大。一直分,分到不能再分,再把每个组和参考值都合并起来
static void Main(string[] args) { List<int> list = new List<int>(); Random r = new Random(); for (int i = 0; i < 100000; i++) { list.Add(r.Next(1, 10000)); } Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); List<int> sort = quickSort(list); stopwatch.Stop(); foreach (int data in sort) { Console.WriteLine(data); } Console.WriteLine("运行时间:" + stopwatch.ElapsedMilliseconds); Console.ReadKey(); } static List<int> quickSort(List<int> datas) { int length = datas.Count; //只有一个元素或则没有元素就返回自身(已经排序好了) if (length < 2) { return datas; } //随机一个参考数 Random r = new Random(); int random_index = r.Next(0, length); int val = datas[random_index]; datas.RemoveAt(random_index); List<int> left = new List<int>();//比参考值小的组 List<int> right = new List<int>();//比参考值大的组 foreach (int data in datas) { if (data < val) { left.Add(data); } else { right.Add(data); } } left = quickSort(left); right = quickSort(right); //合并起来 left.Add(val); left.AddRange(right); return left; }
快速排序的运行时间:O( nlog(n) )
10W个随机数据排序运行时间:207ms(不知道是不是用了List的原因,还是写法问题,总觉得慢了)
详情看:吃菜网-选择排序和快速排序
就是讲一个大的问题,分割成小的问题,在将这个小的问题分割成更小的问题
再解决这些问题,达到基准线,再退出
例如:二分法和快速排序
二分法查找每次查找都缩小了一半的范围
快速排序每次寻找一个参考点,分成两个小的排序组,再分,直到每个小的组都排序好(只有一个元素或则空了),再合成为一个组
适合小的,也适合大的
栈的调用虽然很方便,但是需要大量的栈空间来存储函数的调用
static void Main(string[] args) { Console.WriteLine(Mul(5)); Console.ReadKey(); } //计算1到n的累积 static int Mul(int n) { if (n == 1) { return 1;//等于1的时候就该退出啦 } return n * Mul(n - 1); }
递归主要就是自己调用自己,提供一个出口来退出,停止自己调用自己
说下 n * Mul(n - 1) ,例如这里的 5
5*Mul(4) = 5*4*Mul(3) = 5*4*3*Mul(2) = 5*4*3*2*Mul(1)
这时候最后一个Mul(1)直接返回的1,没有调用自己,程序就退出了
返回 5*4*3*2*1的值
最简单粗暴的一个排序,遍历循环比较每一个值,发现更小的就交换位置
static void Main(string[] args) { int[] datas = new int[100000]; Random r = new Random(); for (int i = 0; i < 100000; i++) { datas[i] = r.Next(1, 10000); } Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); int[] newdatas = Sort(datas); stopwatch.Stop(); foreach (int data in newdatas) { Console.WriteLine(data); } Console.WriteLine("用时:" + stopwatch.ElapsedMilliseconds); Console.ReadKey(); } static int[] Sort(int[] datas) { int length = datas.Length; int[] newArr = new int[datas.Length]; for (int x = 0; x < length; x++) { newArr[x] = datas[x];//复制数组到新数组 } //对新数组进行排序 for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if (newArr[j] < newArr[i]) { //对比发现后面值较小时,交换值 int temp = newArr[i]; newArr[i] = newArr[j]; newArr[j] = temp; } } } return newArr;//返回新的数组(排序好的) }
对于冒泡排序的执行次数为(n+n-1+n-2...+1) = n/2(n+1)
所以运行时间为 O(n2)
模拟排序10W条数据用时:24439ms
class Data { public int id; public string Name; } class Program { static Dictionary<int,Data> list; static void Main(string[] args) { list = new Dictionary<int, Data>(); for (int i = 1; i <= 100; i++) { Data data = new Data(); data.id = i; data.Name = "Name" + i; list.Add(i,data); } while (true) { Console.WriteLine("输入你要查找的数字"); string input = Console.ReadLine(); int num; Int32.TryParse(input, out num); int index = searchNum(num, 1, list.Count); Console.WriteLine(index); } } static int searchNum(int value, int from, int to) { int result = -1; int temp = (int)Math.Floor((double)(from + to) / 2); if (temp < 1 || temp > list.Count) { return -1; } //获取中间元素的值 int tempVal = list[temp].id; if (tempVal == value) { return temp; } if (from == to) {//找不到 return -1; } if (tempVal > value) { result = searchNum(value, from, temp-1); } if (tempVal < value) { result = searchNum(value, temp+1, to); } return result; } }
运行时间为:O(log(n))
对于一个已经排好序的列表,使用中间值的方式来比较值
如果小了,就往左边查找,缩小一半的范围
同样的这样循环,一直对半缩小范围,直到查找到值或找不到(范围内只有一个值了)