二叉树与树的转化

树、森林与二叉树的转换 　树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。1．树、森林到二叉树的转换（1）将树转换为二叉树 　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：　　①在所有兄弟结点之间加一连线；　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。【例1】下面(a)图所示的树可转换为(c)图所示的二叉树。具体转换过程可【参见动画演示】　　　
　 注意：　 由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。（2）将一个森林转换为二叉树 具体方法是：　　① 将森林中的每棵树变为二叉树　　② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。【例2】下图中，左边包含三棵树的森林可转换为右边的二叉树。

具体转换过程可【参见动画演示】 2.二叉树到树、森林的转换　 把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。【例3】下图的森林就是由例2中二叉树转换成的。

external sorting

One example of external sorting is the external mergesort algorithm. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:
Read 100 MB of the data in main memory and sort by some conventional method (usually quicksort).
Write the sorted data to disk.
Repeat steps 1 and 2 until all of the data is sorted in 100 MB chunks, which now need to be merged into one single output file.
Read the first 10 MB of each sorted chunk (call them input buffers) in main memory (90 MB total) and allocate the remaining 10 MB for output buffer.
Perform a 9-way merging and store the result in the output buffer. If the output buffer is full, write it to the final sorted file. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk or otherwise mark it as exhausted if there is no more data in the sorted chunk and do not use it for merging.
This algorithm can be generalized by assuming that the amount of data to be sorted exceeds the available memory by a factor of K. Then, K chunks of data need to be sorted and a K-way merge has to be completed. If X is the amount of main memory available, there will be K input buffers and 1 output buffer of size X/(K+1) each. Depending on various factors (how fast the hard drive is, what is the value of K) better performance can be achieved if the output buffer is made larger (for example twice as large as one input buffer).
In the example, a single-pass merge was used. If the ratio of data to available main memory is particularly large, a multi-pass sorting is preferable. For example, merge only the first half of the sorted chunks, then the other half and now the problem has been reduced to merging just two sorted chunks. The exact number of passes depends on the above mentioned ratio, as well as the physical characteristics of the hard drive (transfer rate and seeking time). As a rule of thumb, it is inadvisable to perform a more-than-20-to-30-way merge

基数排序

基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位)

第一次排序(个位):

3 4 2

5 7 6

3 5 6

0 5 8

第二次排序(十位):

3 4 2

3 5 6

0 5 8

5 7 6

第三次排序(百位):

0 5 8

3 4 2

3 5 6

5 7 6

结果: 58 342 356 576

import java.util.ArrayList;

归并排序是一种基于比较的排序算法，在多数的实现方法下它是稳定的。归并排序可是由计算机祖师级人物－冯 诺依曼提出的哦。

归并排序的过程：
1. 如果数据链表的长度为0或1，则返回
2. 将原始数据链表对半分成两个子链表
3. 对每个子链表递归的调用合并排序进行排序
4. 合并两个子链表使其成为一个排序完成的链表

归并排序的时间复杂度为О(nlogn)，空间复杂度为О(n)。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

 

public class Merge{
public List<Integer> mergesort(List<Integer> data){  
    if(data.size()<=1)  
          return data;  
    int middle = data.size()/2;  
    List<Integer> left = new ArrayList<Integer>();  
    List<Integer> right = new ArrayList<Integer>();  
    for(int i=0; i<middle; i++){  
          left.add(data.get(i));  
    }  
    for(int i=middle; i<data.size();i++){  
          right.add(data.get(i));  
    }  
    left = mergesort(left);  
    right = mergesort(right);  
    List<Integer> result = merge(left, right);  
    return result;  
} 
public List<Integer> merge(List<Integer> left, List<Integer> right){  
    List<Integer> result = new ArrayList<Integer>();  
    while(left.size()>0 && right.size()>0){  
          if(((Integer)left.get(0)).intValue()<=((Integer)right.get(0)).intValue()){  
                result.add(left.get(0));  
                left.remove(0);  
          } else{  
                result.add(right.get(0));  
                right.remove(0);  
          }  
    }  
    if(left.size()>0){  
          for(Iterator<Integer> iter = left.iterator(); iter.hasNext();){  
                result.add(iter.next());  
          }  
    }  
    if(right.size()>0){  
          for(Iterator<Integer> iter = right.iterator(); iter.hasNext();){  
                result.add(iter.next());  
          }  
    }  
    return result;  
} 
public int[] merge(int[] left,int[] right){  
    int result[] = new int[left.length + right.length];  
    int index = 0;//index of result  
    int x = 0;//index of left  
    int y = 0;//index of right   

    //compare each element in two arrays, after comparing, index++.  
    while(x<left.length && y<right.length){  
          if(left[x]<right[y]){  
                result[index++] = left[x++];  
          }else{  
                result[index++] = right[y++];  
          }  
    }  
     
    //the length of two arrays might be different,   
    //so we have to copy the rest elements in two arrays  
    while(x<left.length)    
          result[index++] = left[x++];    
    while(y<right.length)    
          result[index++] = right[y++];  
    return result;  
} 
public static void main(String[] args){
 Merge merge=new Merge();
 List<Integer> list=new ArrayList<Integer>();
 Random rand=new Random();
 for(int i=0;i<100;i++){
  int randnum=rand.nextInt(200);
  list.add(randnum);
 }
      List<Integer> result=merge.mergesort(list);
      for(Object o:result){
       int num=(Integer)o;
       System.out.println(num);}
 
}

}

归并排序

归并排序是一种基于比较的排序算法，在多数的实现方法下它是稳定的。归并排序可是由计算机祖师级人物－冯 诺依曼提出的哦。 归并排序的过程：

1. 如果数据链表的长度为0或1，则返回

2. 将原始数据链表对半分成两个子链表

3. 对每个子链表递归的调用合并排序进行排序

4. 合并两个子链表使其成为一个排序完成的链表 归并排序的时间复杂度为О(nlogn)，空间复杂度为О(n)。

java 举例