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

前言

排序算法在编程中是最简单最基础的算法，同时快速排序和归并排序都是通过递归调用的方式进行排序的，对于递归而言，比较不好理解。记录一下快速排序和归并排序的 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;
        }

异同

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

• 差异 进行的分组策略不同，后面的合并策略也不同。

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