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

前言

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

异同

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

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

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