常用算法（冒泡、插入、选择、快速）和二叉树详解

• 划分、递归、快排

• <span style="color: #808080">@author<span style="color: #008000"> bjh

• <span style="color: #008000">*/
  <span style="color: #0000ff">public <span style="color: #0000ff">class<span style="color: #000000"> QuickSort {

  <span style="color: #008000">/*<span style="color: #008000">待排序、划分数组<span style="color: #008000">/
  <span style="color: #0000ff">private <span style="color: #0000ff">int<span style="color: #000000">[] array;
  <span style="color: #008000">/*<span style="color: #008000">数组长度<span style="color: #008000">/
  <span style="color: #0000ff">private <span style="color: #0000ff">int<span style="color: #000000"> length;

  <span style="color: #0000ff">public QuickSort(<span style="color: #0000ff">int<span style="color: #000000">[] array){
  <span style="color: #0000ff">this.array =<span style="color: #000000"> array;
  <span style="color: #0000ff">this.length =<span style="color: #000000"> array.length;
  }

  <span style="color: #008000">/**<span style="color: #008000">

  • 打印元素
    <span style="color: #008000">*/
    <span style="color: #0000ff">public <span style="color: #0000ff">void<span style="color: #000000"> printArray(){
    <span style="color: #0000ff">for(<span style="color: #0000ff">int i=0; i<length; i++<span style="color: #000000">){
    System.out.print(array[i]+" "<span style="color: #000000">);
    }
    System.out.println();
    }

  <span style="color: #008000">/**<span style="color: #008000">

  • 划分
  • <span style="color: #808080">@return<span style="color: #008000"> 划分的分界点
    <span style="color: #008000">*/
    <span style="color: #0000ff">public <span style="color: #0000ff">int partition(<span style="color: #0000ff">int left,<span style="color: #0000ff">int right,<span style="color: #0000ff">int<span style="color: #000000"> pivot){
    <span style="color: #008000">//<span style="color: #008000">左指针的起点，left-1是由于在后面的循环中，每循环一次左指针都要右移，
    <span style="color: #008000">//<span style="color: #008000">这样可以确保左指针从左边第一个元素开始，不然是从第二个开始
    <span style="color: #0000ff">int leftpoint = left-1<span style="color: #000000">;
    <span style="color: #008000">//<span style="color: #008000">右指针的起点，right+1是由于后面的循环中，每循环一次右指针都要左移，
    <span style="color: #008000">//<span style="color: #008000">这样可以确保右指针从最右边开始，不然是从倒数第二个开始
    <span style="color: #0000ff">int rightpoint = right+1<span style="color: #000000">;
    <span style="color: #0000ff">while(<span style="color: #0000ff">true<span style="color: #000000">){
    <span style="color: #008000">//<span style="color: #008000">找到左边大于pivot的数据，或者走到了最右边仍然没有找到比pivot大的数据
    <span style="color: #0000ff">while(leftpoint<right && array[++leftpoint]<<span style="color: #000000">pivot);
    <span style="color: #008000">//<span style="color: #008000">找到右边小于pivot的数据，或者走到了最左边仍然没有找到比pivot小的数据
    <span style="color: #0000ff">while(rightpoint>left && array[--rightpoint]><span style="color: #000000">pivot);
    <span style="color: #008000">//<span style="color: #008000">左指针和右指针重叠或相交
    <span style="color: #0000ff">if(leftpoint >=<span style="color: #000000"> rightpoint){
    <span style="color: #0000ff">break<span style="color: #000000">;
    }<span style="color: #0000ff">else<span style="color: #000000">{
    <span style="color: #008000">//<span style="color: #008000">交换左边大的和右边小的数据
    <span style="color: #000000"> swap(leftpoint,rightpoint);
    }
    }
    <span style="color: #008000">//<span style="color: #008000">返回分界点，即右边子数组中最左边的点
    <span style="color: #0000ff">return<span style="color: #000000"> leftpoint;
    }

  <span style="color: #008000">/**<span style="color: #008000">

  • 交换数据
    <span style="color: #008000">*/
    <span style="color: #0000ff">public <span style="color: #0000ff">void swap(<span style="color: #0000ff">int leftpoint,<span style="color: #0000ff">int<span style="color: #000000"> rightpoint){
    <span style="color: #0000ff">int temp =<span style="color: #000000"> array[leftpoint];
    array[leftpoint] =<span style="color: #000000"> array[rightpoint];
    array[rightpoint] =<span style="color: #000000"> temp;
    }

  <span style="color: #0000ff">public <span style="color: #0000ff">static <span style="color: #0000ff">void<span style="color: #000000"> main(String args[]){
  <span style="color: #0000ff">int[] array = {99,78,26,82,9,81,22,100,30,20,85<span style="color: #000000">};
  QuickSort qs = <span style="color: #0000ff">new<span style="color: #000000"> QuickSort(array);
  System.out.println("划分前的数据为："<span style="color: #000000">);
  qs.printArray();
  <span style="color: #0000ff">int bound = qs.partition(0,array.length-1,50<span style="color: #000000">);
  System.out.println("划分后的数据为："<span style="color: #000000">);
  qs.printArray();
  System.out.println("划分的分界点为：" + array[bound] + "，分界点的坐标为：" +<span style="color: #000000"> bound);
  }

}

?二叉树：　

二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：

二叉树

由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。

(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小)

二叉搜索树，注意树中元素的大小

二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:

1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)

2. 如果x小于根节点，那么搜索左子树

3. 如果x大于根节点，那么搜索右子树

二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。

<h3 dir="ltr">二叉树的遍历
<blockquote dir="ltr">
<p dir="ltr">遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

?二叉树的类型