前言
很早之前就知道计算机算法与数据结构重要，需要补基础，但是又不知道以一种怎样的方式去学习，循序渐进。盲目的拿着《算法基础》啃也不是个学习好办法。选择一本书，需要满足两个前提条件：一是适合当前你的知识水平；二是你具备这本书籍的前置知识。换句话来说，最好的不一定是最适合你的。对于那些领域内的经典书籍，的确是好书，但是不一定适合你当前的知识水平。这种情况下，所谓的经典好书对你而言，就成了知识毒药，不利于个人知识水平的提高。
出于此，我的切入点是从最平常，最简单的东西入手。但是要做到知其所以然，了解其中蕴含的思想与思维方式，而不是死记硬背特定的代码（这样做的结果往往是过眼既忘，浪费时间与徒增焦虑）。
以上，写给自己，引以为戒。
冒泡排序(Bubble Sort)
常见的排序算法主要有这么几种：冒泡排序，选择排序，插入排序，快速排序和归并排序。清楚几种算法的运行过程和复杂度，是我写这篇文章要达到的目的。
冒泡排序(Bubble Sort)中的冒泡出自小金鱼吐泡泡，小金鱼在水下面吐泡泡，泡泡随着升上水面，一点点变大，最终破碎。建议结合小鲤鱼历险记进行形象化记忆。因为泡泡是一点点变大的，所以冒泡排序默认是升序的。其排序的思想是遍历所有的元素，依次比较相邻元素的大小，如果顺序错误就交换，如果顺序正确就继续下一对相邻元素的比较。
现在我们思考一个问题，对于[4,5,3,7,1,3,9]这个数组，我们排序的时候，需要找多少次最大值呢？答案是6次，因为我们找到了6次最大值之后，剩下的最后最后一个数，自然就是最小的，无需我们将它再次与其他数进行比较。在抽象归纳一下，对于数组长度为n的数组，我们需要进行n-1次最大值的寻找。所以对于冒泡排序最外层的遍历次数是array.length-1次。
这里还要理解的冒泡排序的嵌套遍历，最外层的遍历是为了找到当前无序数组中的最大值，需要遍历array.length-1次。这个最大值是一个虚的概念，所以在里面的遍历需要将这个虚的概念用具体数填充。这个方法就是遍历当前无序数组，进行相邻元素比较。具体代码如下：
// Bubble Sort
let array = [2,3,5,4,2,6,1,3,7,3]
function BubbleSort(array) {
var i,j,temp;
for (i=1;i<array.length;i++) {
for (j=0;j<array.length-i;j++) {
if (array[j]>array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array;
}
console.log(BubbleSort(array)) // [ 1, 2, 2, 3, 3, 3, 4, 5, 6, 7 ]
再来看复杂度，本文所说的复杂度均为时间复杂度，不包含空间复杂度，因为空间复杂度我也没弄明白。算法复杂度是输入规模与操作步骤之间的关系。它用于在程序运行之前，理论上用于比较算法优劣的参考标准。（这里的优劣指的是耗费内存大小和运行时间长短等）。上文的数组长度是7，是个有限数，我们常常将输入规模取n，趋近与无限大，来比较这种情况下的操作步骤。而对于一个算法，当输入规模趋近于n时，步骤中最多的就是遍历步骤，冒泡算法因为有两层循环，就达到了n^2。复杂度使用符号大O表示，所以冒泡算法的时间复杂度就是O(n^2)。
性能：
- 时间复杂度：O(n^2)
选择排序(Selection Sort)
选择排序的核心是序列中每个数的位置。我们需要把序列看成是一行箱子，每个箱子里面装着一个数字。这一行箱子是排列在一行的，并且位置是固定的。我们首先假设左边的第一个箱子里面装的数字是最小的数字，那么循环遍历剩下箱子里面的数字，如果其他箱子里面的数字比我们指定的第一个箱子里面的数还要小，那么就交换两个箱子里面的数字。注意**箱子是不动的，变化的是箱子里面装的数字。这样一次循环后，第一个箱子里面装的数字确实是整个序列中最小的了。接下来，指定第二个箱子里面装的是未排序序列里面最小的数字，继续遍历剩下的箱子里面的数字。
具体代码如下：
// Selection Sort
let array = [ 1, 2, 2, 3, 3, 3, 4, 5, 6, 7 ]
let selectionSort = function(array) {
for (let i=0;i<array.length-1;i++) {
for (let j=i+1;j<array.length;j++) {
let temp = null
if (array[i]>array[j]) {
temp = array[i]
array[i] = array[j]
array[j] = temp
}
}
}
return array;
}
console.log(selectionSort(array)) // [ 1, 2, 2, 3, 3, 3, 4, 5, 6, 7 ]
性能：
- 时间复杂度：O(n^2)
插入排序
具体代码如下：
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
var array = [2,3,5,4,2,6,1,3,7,3]
function InsertionSort(array) {
var i,j,temp;
for (i=1;i<array.length;i++) {
for (j=i-1;j>=0;j--) {
if (j===0 && array[i]<=array[j]) {
array.splice(j,0,array[i]);
array.splice(i+1,1);
break;
} else if (j>0 && array[i]<=array[j] && array[i]>=array[j-1]) {
array.splice(j,0,array[i]);
array.splice(i+1,1);
break;
}
}
}
return array;
}
console.log(InsertionSort(array))
性能：
- 时间复杂度：O(n^2)
快速排序
var array = [2,3,5,4,2,6,1,3,7,3]
function QuickSort(array) {
if (array.length <= 1) {
return array;
}
let base = array[0];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i]<base) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return QuickSort(left).concat(base,QuickSort(right));
}
console.log(QuickSort(array));
性能：
- 时间复杂度：O(nlogn)
归并排序
归并排序图解
如上图所示，归并排序（英语：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法。该算法采用分治法，第一阶段是分割(递归地把当前序列平均分割成两半)，第二阶段是整合(在保持元素顺序的同时将上一步得到的子序列整合到一起)。
代码如下：
// Merge Sort
function merge(left, right) {
var temp = [];
while (left.length && right.length) {
temp.push(left[0] <= right[0] ? left.shift() : right.shift())
}
return temp.concat(left,right)
}
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 merge(MergeSort(left), MergeSort(right));
}
let a = [3,22,4,1,5,1,4,8,6,9,4,0]
console.log(MergeSort(a));
性能：
- 时间复杂度：O(nlogn)
网友评论