算法
大数据面试中考察的算法相对容易一些，常考的有排序算法，查找算法，二叉树等，下面讲解一些最容易考的算法。
1. 排序算法
十种常见排序算法可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
算法复杂度：
相关概念：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
下面讲解大数据中最常考的两种：快排和归并
# 1) 快速排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现：
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // 分区操作
var pivot = left, // 设定基准值（pivot）
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
# 2) 归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
代码实现：
function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
2. 查找算法
七大查找算法：1. 顺序查找、2. 二分查找、3. 插值查找、4. 斐波那契查找、5. 树表查找、6. 分块查找、7. 哈希查找
这些查找算法中二分查找是最容易考察的，下面讲解二分查找算法。
# 1) 二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列，注意必须要是有序排列。
代码实现：
- 使用递归
/**
* 使用递归的二分查找
*title:recursionBinarySearch
*@param arr 有序数组
*@param key 待查找关键字
*@return 找到的位置
*/
public static int recursionBinarySearch(int[] arr,int key,int low,int high){
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
int middle = (low + high) / 2; //初始中间位置
if(arr[middle] > key){
//比关键字大则关键字在左区域
return recursionBinarySearch(arr, key, low, middle - 1);
}else if(arr[middle] < key){
//比关键字小则关键字在右区域
return recursionBinarySearch(arr, key, middle + 1, high);
}else {
return middle;
}
}
- 不使用递归实现（while循环）
/**
* 不使用递归的二分查找
*title:commonBinarySearch
*@param arr
*@param key
*@return 关键字位置
*/
public static int commonBinarySearch(int[] arr,int key){
int low = 0;
int high = arr.length - 1;
int middle = 0; //定义middle
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
while(low <= high){
middle = (low + high) / 2;
if(arr[middle] > key){
//比关键字大则关键字在左区域
high = middle - 1;
}else if(arr[middle] < key){
//比关键字小则关键字在右区域
low = middle + 1;
}else{
return middle;
}
}
return -1; //最后仍然没有找到，则返回-1
}
3. 二叉树实现及遍历
定义：二叉树，是一种特殊的树，二叉树的任意一个节点的度都不大于2，不包含度的节点称之为叶子。
遍历方式：二叉树的遍历方式有三种，中序遍历，先序遍历，后序遍历。
将一个数组中的数以二叉树的存储结构存储，并遍历打印：
代码实现：
import java.util.ArrayList;
import java.util.List;
public class bintree {
public bintree left;
public bintree right;
public bintree root;
// 数据域
private Object data;
// 存节点
public List<bintree> datas;
public bintree(bintree left, bintree right, Object data){
this.left=left;
this.right=right;
this.data=data;
}
// 将初始的左右孩子值为空
public bintree(Object data){
this(null,null,data);
}
public bintree() {
}
public void creat(Object[] objs){
datas=new ArrayList<bintree>();
// 将一个数组的值依次转换为Node节点
for(Object o:objs){
datas.add(new bintree(o));
}
// 第一个数为根节点
root=datas.get(0);
// 建立二叉树
for (int i = 0; i <objs.length/2; i++) {
// 左孩子
datas.get(i).left=datas.get(i*2+1);
// 右孩子
if(i*2+2<datas.size()){//避免偶数的时候 下标越界
datas.get(i).right=datas.get(i*2+2);
}
}
}
//先序遍历
public void preorder(bintree root){
if(root!=null){
System.out.println(root.data);
preorder(root.left);
preorder(root.right);
}
}
//中序遍历
public void inorder(bintree root){
if(root!=null){
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}
}
// 后序遍历
public void afterorder(bintree root){
if(root!=null){
System.out.println(root.data);
afterorder(root.left);
afterorder(root.right);
}
}
public static void main(String[] args) {
bintree bintree=new bintree();
Object []a={2,4,5,7,1,6,12,32,51,22};
bintree.creat(a);
bintree.preorder(bintree.root);
}
}