编程面试的10大算法概念汇总(2)

public class GraphTest {
 
 public static void main(String[] args) {
  GraphNode n1 = new GraphNode(1);
  GraphNode n2 = new GraphNode(2);
  GraphNode n3 = new GraphNode(3);
  GraphNode n4 = new GraphNode(4);
  GraphNode n5 = new GraphNode(5);
 
  n1.neighbors = new GraphNode[]{n2,n3,n5};
  n2.neighbors = new GraphNode[]{n1,n4};
  n3.neighbors = new GraphNode[]{n1,n4,n5};
  n4.neighbors = new GraphNode[]{n2,n3,n5};
  n5.neighbors = new GraphNode[]{n1,n3,n4};
 
  breathFirstSearch(n1, 5);
 }
 
 public static void breathFirstSearch(GraphNode root, int x){
  if(root.val == x)
   System.out.println("find in root");
 
  Queue queue = new Queue();
  root.visited = true;
  queue.enqueue(root);
 
  while(queue.first != null){
   GraphNode c = (GraphNode) queue.dequeue();
   for(GraphNode n: c.neighbors){
 
    if(!n.visited){
     System.out.print(n + " ");
     n.visited = true;
     if(n.val == x)
      System.out.println("Find "+n);
     queue.enqueue(n);
    }
   }
  }
 }
}

输出：

value: 2 value: 3 value: 5 Find value: 5
value: 4

5. 排序

下面是不同排序算法的时间复杂度，你可以去wiki看一下这些算法的基本思想。

Algorithm   Average Time   Worst Time   Space  
冒泡排序   n^2   n^2   1  
选择排序   n^2   n^2   1  
Counting Sort   n+k   n+k   n+k  
Insertion sort   n^2   n^2      
Quick sort   n log(n)   n^2      
Merge sort   n log(n)   n log(n)   depends  

另外，这里有一些实现/演示：: Counting sort、Mergesort、 Quicksort、 InsertionSort。

推荐阅读：

Linux 多线程同步（信号量）

Linux C++动态链接库so编写

Linux多线程──主线程和子线程分别循环一定次数

Linux多线程──3个子线程轮流运行

Linux多线程──生产者消费者

Linux多线程──读者写者问题

Linux基础编程 多线程中的互斥锁 pthread_mutex_lock

Linux基础编程 多线程同步 pthread_cond_signal