正文
前言
归并排序与快速排序是两种有实际应用的排序算法，它们有一些共同的特点，整体思路上也比较相近。本文会从更简单的一些排序算法开始，过渡到归并排序和快速排序的实现，并对它们做一些简单的对比思考和总结。在这之前，先简单介绍一下排序算法的意义。
排序算法就是将一串数据依照特定排序方式进行排列，它们在计算机科学中有大量研究以及应用。
想象一下下列场景：
-
从通讯录中寻找某个联系人
-
从一大堆文件中寻找某个文件
-
到了影厅之后，寻找电影票上指定的座位
如果以上情况中，联系人、文件、影厅座位这些“数据”没有按照需要的顺序组织，如何找到想要的特定“数据”呢？会非常麻烦！所以说，对于需要搜索的数据，往往应该先排个序！
热身一：选择排序
本文的示例都是数值排序，对于这个问题，最简单直观的方法是：先找出最小的、再找出第二小的、接着找出第三小的……这就是选择排序的思路。
function selectionSort(array) {
const len = array.length;
let minIndex = 0;
for (let i = 0; i < len; i++) {
minIndex = i;
for (let j = i; j < len; j++) {
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
if (i !== minIndex) {
[ array[i], array[minIndex] ] = [ array[minIndex], array[i] ];
}
}
return array;
}
实现解析：
-
遍历数组
-
找到当前范围内最小的元素，用 minIndex 记录它的下标，第一次遍历时范围就是整个数组
-
将下标为 minIndex 的元素的值与当前最小下标的元素交换，第一次遍历时下标最小的元素就是 a[0]
-
第二次遍历时，范围就从第二个数据元素的下标开始，那么当前最小下标元素就是 a[1]
-
重复交换直至遍历结束
用一段辅助代码，做一些展示用的示例。
function createUnsortedArray(size) {
const array = [];
for (let i = size; i > 0; i--) {
const num = (i / 10 > 1) ? i : 10;
array.push( Math.round(Math.random(i) * num + Math.round(Math.random(i)) * Math.random(i) * num * 10) );
}
return array;
}
function show(fn, size = 11) {
console.log('------------------------------------------');
console.log(`Method: ${fn.name}`);
console.log('------------------------------------------');
const array = createUnsortedArray(size);
console.log('before:');
console.log(array.toString());
console.log('after:');
console.log(fn(array).toString());
}
先创建一个随机生成的未排序的数组，然后打印结果。
show(selectionSort);
热身二：冒泡排序
冒泡排序与选择排序有些类似，区别在于冒泡排序是先将最大值冒泡到最后的位置。早在 1956 年，就已经有人研究冒泡排序。
function bubbleSort(array) {
for (let first = 0, len = array.length; first < len; first++) {
let isSorted = true;
for (let second = 0; second < len - first - 1; second++) {
if (array[second] > array[second + 1]) {
let temp = array[second];
array[second] = array[second + 1]
array[second + 1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
return array;
}
show(bubbleSort);
实现解析：
-
遍历数组
-
做第二层遍历，从前到后依次对比相邻两项，前一项的值大于后一项，则交换（冒泡）。第一遍冒泡，将最大的元素值冒泡至最后
-
由于每一遍冒泡都确定一个当前最大值并放到当前范围的最后的位置，每一遍的冒泡就可以少检查一个位置
-
可以使用一个变量记录当前一遍的冒泡有没有产生元素交换，如果没有，说明当前已经是排序完成的状态，终止循环。
归并排序（递归实现）
选择排序和冒泡排序的时间复杂度都是 O(n^2)，很少用在实际工程中；归并排序的时间复杂度是 O(nlog(n))，是实际工程中可选的排序方案。
function mergeSort(unsorted) {
function merge(leftArr, rightArr) {
const lenL = leftArr.length;
const lenR = rightArr.length;
let indexL = 0;
let indexR = 0;
const result = [];
while (indexL < lenL && indexR < lenR) {
if (leftArr[indexL] < rightArr[indexR]) {
result.push(leftArr[indexL++]);
} else {
result.push(rightArr[indexR++]);
}
}
while (indexL < lenL) {
result.push(leftArr[indexL++]);
}
while (indexR < lenR) {
result.push(rightArr[indexR++]);
}
return result;
}
function split(array) {
const len = array.length;
if (len <= 1) {
return array;
}
const mid = Math.floor(len / 2);
const leftArr = array.slice(0, mid);
const rightArr = array.slice(mid, len);
return merge( split(leftArr), split(rightArr) );
}
return split(unsorted);
}
show(mergeSort);
实现分析：
-
将数组从中间切分为两个数组
-
切分到最小之后，开始归并操作，即合并两个已排序的数组
-
递归合并的过程，由于是从小到大合并，所以待合并的两个数组总是已排序的，一直做同样的归并操作就可以
快速排序（递归实现）
快速排序是实际应用非常多的排序算法，它通常比其他 O(nlog(n)) 时间复杂度的算法更快。
function quickSort(unsorted) {
function partition
