还记得以前学数据结构与算法课程的时候，开篇就有些句话”程序=算法+ 数据结构“
现在慢慢的发现算法是一名程序员必不可少的技能，之前我和大多数前端er一样，觉得算法在前端使用的非常少，没必要学习算法，如果我们只局限现于前端，那么们的目光也太短浅了。
快速排序
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：选准一个基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程以递归进行，以此达到整个数据变成有序
function quicksort(a,left,right){
if(left>right){ //一定要有这个判断，因为有递归left和i-1，若没有这个判断条件，该函数会进入无限死错位递归
return;
}
var i=left,
j=right,
jizhun=a[left]; //基准总是取序列开头的元素
while(i!=j){ //该while的功能为每一趟进行的多次比较和交换最终找到位置k。当i==j时意味着找到k位置了
while(a[j]>=jizhun&&i<j){j--} //只要大于等于基准数，j指针向左移动直到小于基准数才不进入该while。i<j的限制条件也是很重要，不然一直在i!=j这个循环里，j也会越界
while(a[i]<=jizhun&&i<j){i++} //只要小于等于基准数，i指针向右移动直到大于基准数才不进入该while。等于条件也是必要的，举例[4,7,6,4,3]验证一下是两个4交换
if(i<j){ //如果i==j跳出外层while
t=a[i];
a[i]=a[j];
a[j]=t
}
}
a[left]=a[i];//交换基准数和k位置上的数
a[i]=jizhun;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
var array=[4,7,2,8,3,9,12];
quicksort(array,0,array.length-1);//排完序后再看array是[2, 3, 4, 7, 8, 9, 12]
归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表
function mergeSort(arr) {
const length = arr.length;
if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
return arr;
}
const mid = Math.floor(length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid, length);
return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时，才开始归并
}
function merge(left, right) {
const result = [];
let il = 0;
let ir = 0;
//left, right本身肯定都是从小到大排好序的
while( il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il]);
il++;
} else {
result.push(right[ir]);
ir++;
}
}
//不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
while (il < left.length) {
result.push(left[il]);
il++;
}
while(ir < right.length) {
result.push(right[ir]);
ir++;
}
return result;
}
console.log(mergeSort([2,9,1,8,3,]))
