【Java面试12】常用算法（冒泡、插入、选择、快速）和二叉树详解
常用算法（冒泡、插入、选择、快速）和二叉树详解
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号（Order）表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
定义
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
算法复杂度
算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。(算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间(即寄存器)资源，因此复杂度分为时间和空间复杂度)。
时间复杂度
1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做:T(n)=O(f(n))
分析:随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。
2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级(它的同数量级有以下:1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!)，找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))
例:算法:
则有 T(n) = n 的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T(n)的同数量级
则有 f(n) = n的三次方，然后根据 T(n)/f(n) 求极限可得到常数c
则该算法的时间复杂度:T(n) = O(n^3) 注:n^3即是n的3次方。
3.在pascal中比较容易理解，容易计算的方法是:看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。
常用排序
|
名称 |
复杂度 |
说明 |
备注 |
|
冒泡排序 |
O(N*N) |
将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮 |
|
|
插入排序 Insertion sort |
O(N*N) |
逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置 |
起初，已经排序的元素序列为空 |
|
选择排序 |
O(N*N) |
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。 |
|
|
快速排序 Quick Sort |
O(n *log2(n)) |
先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。 |
|
|
堆排序HeapSort |
O(n *log2(n)) |
利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。 |
近似完全二叉树 |
|
希尔排序 SHELL |
O(n1+￡) 0<￡<1 |
选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1. |
|
|
箱排序 |
O(n) |
设置若干个箱子，把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。 |
分配排序的一种：通过" 分配 " 和 " 收集 " 过程来实现排序。 |
冒泡排序
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
冒泡排序流程至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
编码思路：
用二重循环实现，外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j的值依次为1,2,...10-i。
/*
* 冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr={9,8,7,6,5,4,3,2,1};
System.out.println("排序前数组为：");
for(int num:arr){
System.out.print(num+" ");
}
for(int i=0;i<arr.length-1;i++){//外层循环控制排序趟数
for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
System.out.println();
System.out.println("排序后的数组为：");
for(int num:arr){
System.out.print(num+" ");
}
}
}
插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
1、将指针指向某个元素，假设该元素左侧的元素全部有序，将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；
2、此时会出现一个空位，将该元素放入到空位中，此时该元素左侧的元素都比它小，右侧的元素都比它大；
3、指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。
编码思路：
需要两层循环，第一层循环index表示上述例子中的指针，即遍历从坐标为1开始的每一个元素；第二层循环从leftindex=index-1开始，leftindex--向左遍历，将每一个元素与i处的元素比较，直到j处的元素小于i出的元素或者leftindex<0；遍历从i到j的每一个元素使其右移，最后将index处的元素放到leftindex处的空位处。
public class InsertSort {
private int[] array;
private int length;
public InsertSort(int[] array){
this.array = array;
this.length = array.length;
}
public void display(){
for(int a: array){
System.out.print(a+" ");
}
System.out.println();
}
/**
* 插入排序方法
*/
public void doInsertSort(){
for(int index = 1; index<length; index++){//外层向右的index，即作为比较对象的数据的index
int temp = array[index];//用作比较的数据
int leftindex = index-1;
while(leftindex>=0 && array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
array[leftindex+1] = array[leftindex];
leftindex--;
}
array[leftindex+1] = temp;//把temp放到空位上
}
}
public static void main(String[] args){
int[] array = {38,65,97,76,13,27,49};
InsertSort is = new InsertSort(array);
System.out.println("排序前的数据为：");
is.display();
is.doInsertSort();
System.out.println("排序后的数据为：");
is.display();
}
}
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
1、从第一个元素开始，分别与后面的元素向比较，找到最小的元素与第一个元素交换位置；
2、从第二个元素开始，分别与后面的元素相比较，找到剩余元素中最小的元素，与第二个元素交换；
3、重复上述步骤，直到所有的元素都排成由小到大为止。
编程思路：
需要两次循环，第一层循环i表示每轮指针指向的位置，将最小值min初始化为第i个元素，第二层循环从j=i+1开始，分别与min比较，如果小于min，则更新min的值，内层循环结束后；交换min元素和第i个元素的位置。以此类推进行下一轮循环，直到i=length时停止循环。当i=length时，说明小的元素已经全部移到了左面，因此无需进行内层循环了。
package com.test.insertsort;
/**
* 选择排序
* @author Administrator
*
*/
public class ChooseSort {
private int[] array;
private int length;
public ChooseSort(int[] array){
this.array = array;
this.length = array.length;
}
/**
* 打印数组中的所有元素
*/
public void display(){
for(int i: array){
System.out.print(i+" ");
}
System.out.println();
}
/**
* 选择排序算法
*/
public void chooseSort(){
for(int i=0; i<length-1; i++){
int minIndex = i;
for(int j=minIndex+1;j<length;j++){
if(array[j]<array[minIndex]){
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
public static void main(String[] args){
int[] array={100,45,36,21,17,13,7};
ChooseSort cs = new ChooseSort(array);
System.out.println("排序前的数据为：");
cs.display();
cs.chooseSort();
System.out.println("排序后的数据为：");
cs.display();
}
} 快速排序
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动
注：在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。
要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
排序演示
示例
假设用户输入了如下数组：
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|
数据 |
6 |
2 |
7 |
3 |
8 |
9 |
创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。
我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|
数据 |
3 |
2 |
7 |
6 |
8 |
9 |
i=0 j=3 k=6
接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|
数据 |
3 |
2 |
6 |
7 |
8 |
9 |
i=2 j=3 k=6
称上面两次比较为一个循环。
接着，再递减变量j，不断重复进行上面的循环比较。
在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
|
数据 |
3 |
2 |
6 |
7 |
8 |
9 |
如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
package com.test.insertsort;
/**
* 划分、递归、快排
* @author bjh
*
*/
public class QuickSort {
/**待排序、划分数组*/
private int[] array;
/**数组长度*/
private int length;
public QuickSort(int[] array){
this.array = array;
this.length = array.length;
}
/**
* 打印元素
*/
public void printArray(){
for(int i=0; i<length; i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
/**
* 划分
* @return 划分的分界点
*/
public int partition(int left, int right, int pivot){
//左指针的起点，left-1是由于在后面的循环中，每循环一次左指针都要右移，
//这样可以确保左指针从左边第一个元素开始，不然是从第二个开始
int leftpoint = left-1;
//右指针的起点，right+1是由于后面的循环中，每循环一次右指针都要左移，
//这样可以确保右指针从最右边开始，不然是从倒数第二个开始
int rightpoint = right+1;
while(true){
//找到左边大于pivot的数据，或者走到了最右边仍然没有找到比pivot大的数据
while(leftpoint<right && array[++leftpoint]<pivot);
//找到右边小于pivot的数据，或者走到了最左边仍然没有找到比pivot小的数据
while(rightpoint>left && array[--rightpoint]>pivot);
//左指针和右指针重叠或相交
if(leftpoint >= rightpoint){
break;
}else{
//交换左边大的和右边小的数据
swap(leftpoint,rightpoint);
}
}
//返回分界点，即右边子数组中最左边的点
return leftpoint;
}
/**
* 交换数据
*/
public void swap(int leftpoint,int rightpoint){
int temp = array[leftpoint];
array[leftpoint] = array[rightpoint];
array[rightpoint] = temp;
}
public static void main(String args[]){
int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85};
QuickSort qs = new QuickSort(array);
System.out.println("划分前的数据为：");
qs.printArray();
int bound = qs.partition(0, array.length-1, 50);
System.out.println("划分后的数据为：");
qs.printArray();
System.out.println("划分的分界点为：" + array[bound] + "，分界点的坐标为：" + bound);
}
}二叉树遍历
树的特征和定义
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树：
树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。
每个节点可以有多个子节点(children)，而该节点是相应子节点的父节点(parent)。比如说，3,5是6的子节点，6是3,5的父节点；1,8,7是3的子节点, 3是1,8,7的父节点。树有一个没有父节点的节点，称为根节点(root)，如图中的6。没有子节点的节点称为叶节点(leaf)，比如图中的1,8,9,5节点。从图中还可以看到，上面的树总共有4个层次，6位于第一层，9位于第四层。树中节点的最大层次被称为深度。也就是说，该树的深度(depth)为4。
如果我们从节点3开始向下看，而忽略其它部分。那么我们看到的是一个以节点3为根节点的树：
三角形代表一棵树
再进一步，如果我们定义孤立的一个节点也是一棵树的话，原来的树就可以表示为根节点和子树(subtree)的关系:
上述观察实际上给了我们一种严格的定义树的方法：
1. 树是元素的集合。
2. 该集合可以为空。这时树中没有元素，我们称树为空树 (empty tree)。
3. 如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与它的子树的根节点用一个边(edge)相连。
上面的第三点是以递归的方式来定义树，也就是在定义树的过程中使用了树自身(子树)。由于树的递归特征，许多树相关的操作也可以方便的使用递归实现。我们将在后面看到。
树的实现
树的示意图已经给出了树的一种内存实现方式: 每个节点储存元素和多个指向子节点的指针。然而，子节点数目是不确定的。一个父节点可能有大量的子节点，而另一个父节点可能只有一个子节点，而树的增删节点操作会让子节点的数目发生进一步的变化。这种不确定性就可能带来大量的内存相关操作，并且容易造成内存的浪费。
一种经典的实现方式如下:
树的内存实现
拥有同一父节点的两个节点互为兄弟节点(sibling)。上图的实现方式中，每个节点包含有一个指针指向第一个子节点，并有另一个指针指向它的下一个兄弟节点。这样，我们就可以用统一的、确定的结构来表示每个节点。
计算机的文件系统是树的结构，比如Linux文件管理背景知识中所介绍的。在UNIX的文件系统中，每个文件(文件夹同样是一种文件)，都可以看做是一个节点。非文件夹的文件被储存在叶节点。文件夹中有指向父节点和子节点的指针(在UNIX中，文件夹还包含一个指向自身的指针，这与我们上面见到的树有所区别)。在git中，也有类似的树状结构，用以表达整个文件系统的版本变化 (参考版本管理三国志)。
二叉树：
二叉树是由n（n≥0）个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个根和称为左、右子树的两个不相交的二叉树组成。
特点：
（1）二叉树是有序树，即使只有一个子树，也必须区分左、右子树；
（2）二叉树的每个结点的度不能大于2，只能取0、1、2三者之一；
（3）二叉树中所有结点的形态有5种：空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点。
二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：
二叉树
由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。
如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。
(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小)
二叉搜索树，注意树中元素的大小
二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:
1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)
2. 如果x小于根节点，那么搜索左子树
3. 如果x大于根节点，那么搜索右子树
二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。
二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
例如：求下面树的三种遍历
前序遍历：abdefgc
中序遍历：debgfac
后序遍历：edgfbca
二叉树的类型
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
如何判断一棵树是完全二叉树？按照定义，
教材上的说法：一个深度为k，节点个数为 2^k - 1 的二叉树为满二叉树。这个概念很好理解，
就是一棵树，深度为k，并且没有空位。
首先对满二叉树按照广度优先遍历（从左到右）的顺序进行编号。
一颗深度为k二叉树，有n个节点，然后，也对这棵树进行编号，如果所有的编号都和满二叉树对应，那么这棵树是完全二叉树。
