算法

## 前言

排序算法在编程中是最简单最基础的算法，同时快速排序和归并排序都是通过递归调用的方式进行排序的，对于递归而言，比较不好理解。记录一下快速排序和归并排序的 Javascript 代码实现以及两种算法的相同点与差异性。

## 快速排序

```javascript
 function quickSort(arr) {
            if (arr.length <= 1) {
                return arr;
            }
            const mid = Math.floor(arr.length / 2);
            const midNum = arr.splice(mid, 1)[0];
            let left = [];
            let right = [];
            for (let a of arr) {
                if (a < midNum) {
                    left.push(a);
                } else {
                    right.push(a);
                }
            }
            return quickSort(left).concat(midNum, quickSort(right));
        }
```

## 归并排序

```javascript
 function mergeSort(arr) {
            if (arr.length <= 1) {
                return arr;
            }
            let mid = Math.floor(arr.length / 2);
            let left = arr.slice(0, mid);
            let right = arr.slice(mid);
            return mergeArray(mergeSort(left), mergeSort(right));
        }

        function mergeArray(left, right) {
            let result = [];
            while (left.length && right.length) {
                if (left[0] < right[0]) {
                    let a = left.shift();
                    result.push(a)
                } else {
                    let b = right.shift();
                    result.push(b)
                }
            }

            while (left.length) {
                let a = left.shift();
                result.push(a);
            }

            while (right.length) {
                let b = right.shift();
                result.push(b)
            }
            return result;
        }
```

### 异同

- **相同**
  两者原理都是采用“分而治之”的思想，即首先把待排序的元素分为两组，然后分别对这两组排序，最后把两组结果进行合并。
- **差异**
  进行的分组策略不同，后面的合并策略也不同。

  归并排序的分组策略是假设待排序的元素存放在数组中，那么其把数组前面一半元素作为一组，后面一半所谓另一组。而快速排序则是根据元素的值来进行分组，即大于某个值的元素放在一组，小于的放在另外一组，该值称为基准。总的来说，如果分组策略越简单，则后面的合并策略就越复杂，因为快速排序在分组时，已经根据元素大小来分组了，在合并时，只需要把两个分组合并起来就行了，而归并排序则需要对两个有序的数组根据大小合并。


前言排序算法在编程中是最简单最基础的算法，同时快速排序和归并排序都是通过递归调用的方式进行排序的，对于递归而言，比较不好理解。记录一下快速排序和归并排序的Javascript代码实现以及两种算法的相同点与差异性。快速排序functionquickSort(arr){if(arr.length=1){returnarr;}constmid=Math.floor(arr.length/2);const

分治思想在排序算法中的应用 - 快速排序&归并排序

## 问题

![问题图片](http://api.portal.levenx.com/e44ed0b5f25743049249d51a2719ac2c.jpg)

## 解决方案

- BFS 广度遍历

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    //定义结果集数组
    let result = [];

    if (root) {
        //因为期望结果是分层数组输出的，区分层次定义父层与子层
        let parent = [];
        let children = [];
        //暂存当前层的val值
        let tmpCache = [];

        parent.push(root)
        while (!!parent.length) {
            //出栈
            let current = parent.shift();
            tmpCache.push(current.val);
             //如果当前节点存在，把左右节点暂存到children数组中
            if (current.left) {
                children.push(current.left);
            }
            if (current.right) {
                children.push(current.right);
            }
            //如果parent数组长度为0,说明当前层遍历结束，做相应的处理
            if (parent.length === 0) {
                if (tmpCache.length) {
                    result.push(tmpCache);
                }
                tmpCache = [];
                parent = children;
                children = []
            }
        }
    }
    return result;

};
```


从上到下按层打印二叉树问题解决方案BFS广度遍历/***Definitionforabinarytreenode.*functionTreeNode(val){*this.val=val;*this.left=this.right=null;*}*//***@param{TreeNode}root*@return{number[][]}*/varlevelOrder=function(root){

从上到下按层打印二叉树

![715141-20181106190033609-1693577031](http://api.portal.levenx.com/db99c385bce6400fa1209698dc22c0d7.jpg)

```javascript
function dfs(root){
    //do sth
    dfs(root.left);
    dfs(root.right);
}
```

![715141-20181106190310845-797901347](http://api.portal.levenx.com/64ae1623a05f477aaebc281311f40970.jpg)

```javascript
function dfs(root){
    dfs(root.left);
    //do sth
    dfs(root.right);
}
```

![715141-20181106190341618-298002101](http://api.portal.levenx.com/fc4d1e8213de41958e13fc5254fe5f7f.jpg)

```javascript
 function dfs(root){
    dfs(root.left);
    dfs(root.right);
    //do sth
}
```


functiondfs(root){//dosthdfs(root.left);dfs(root.right);}functiondfs(root){dfs(root.left);//dosthdfs(root.right);}functiondfs(root){dfs(root.left);dfs(root.right);//dosth}...

分治思想在排序算法中的应用 - 快速排序&归并排序

从上到下按层打印二叉树

「数据结构」树的遍历