用JS写算法的作用？
-
锻炼思维，提高开发效率。
-
虽然平时工作不一定能用到，但是面试的时候吹逼很有用。
函数式编程有啥用？
-
更短的代码、更少的BUG。
-
函数式编程这个名词比较装逼。
冒泡排序
冒泡排序是所有排序算法里最简单的一个，（但是从效率来讲是最差的一个，时间复杂度为O(n^2)）。
冒泡排序会以此比较任何相邻的元素，如果第一个比第二个大，则交换他们。
较小的元素不断向前排列，就像轻的气泡上升一样，所以叫冒泡排序。
每一次循环遍历数组的时候，元素只会向前移动一个位置，所以如果要保证所有元素正确排序，
比如最小的元素在原数组的最后，需要排到最前，需要循环套循环，才能保证排序正确。
//函数式版
const bubbleSort = (array)=>{
return array.reduce((pre)=>{
return pre.reduce((p,c,i,arr)=>{
if(arr[i]>arr[i+1]){
[arr[i],arr[i+1]]=[arr[i+1],arr[i]];
}
return arr
},[]);
},[...array]);
};
//命令式版
const bubbleSort = (array) =>{
for(let i=0; i<array.length; i++){
for(let i=0; i<array.length; i++){
if(array[i]>array[i+1]){
[array[i],array[i+1]]=[array[i+1],array[i]]
}
}
}
};
选择排序
选择排序的原理是，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
每次循环遍历数组只能找到1个元素并排序，所以和冒泡排序一样，需要循环套循环才能保证排序正确，时间复杂度也是O(n^2)。
// 函数式版
const selectionSort = (array)=>{
return array.reduce((pre,cur,index)=>{
return pre.reduce((_pre,_cur,_index,arr)=>{
if(_index>=index && arr[_index]<arr[index]){
[arr[_index],arr[index]]=[arr[index],arr[_index]]
}
return arr;
},[])
},[...array])
};
//命令式版
const selectionSort = (array)=>{
const length = array.length;
let indexMin;
for(let i=0; i<length-1; i++){
indexMin = i;
for(let j=i;j<length;j++){
if(array[indexMin]>array[j]){
indexMin = j;
}
}
if(i !== indexMin){
[array[indexMin],array[i]] = [array[i],array[indexMin]]
}
}
};
插入排序
插入排序的工作原理是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。时间复杂度也是O(n^2)
//函数式版
const insertionSort = (array) =>{
return array.reduce((pre,cur)=>{
return [...pre,cur].reduce((_pre,_cur,index,arr)=>{
const last = arr.length - index-1;
const _last = arr.length - index - 2;
if(arr[last] < arr[_last]){
[arr[last], arr[_last]] = [arr[_last], arr[last]];
}
return arr
},[])
},[])
};
//命令式版
const insertionSort = (array)=>{
const length = array.length;
let j,temp;
for(let i=1; i<length; i++){
j=i;
temp = array[i];
while(j>0 && array[j-1]>temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
};
归并排序
前三个排序算法性能不好，但归并排序性能不错，是一个可以被实际使用的排序算法,时间复杂度为O(nlogn)，但是会比前三种算法难一些。
归并排序的是一种分治算法,意思就是把数组分成较小的数组，直到每个数组只有一个元素，然后对小数组逐级往上合并排序一个大数组，
直至所有排序完成。
//函数式版
const mergeSort = (array) => {
if(array.length < 2) return array;
return merge(
mergeSort(array.splice(0,Math.floor(array.length/2))),
mergeSort(array)
);
};
const merge = (left, right)=> {
return [...left,...right].reduce((pre)=>{
if(left[0]<right[0] || !right[0] ){
return [...pre,left.shift()]
}else{
return [...pre,right.shift()]
}
},[]);
};
//命令式版
const mergeSort = (array)=>{
const length = array.length;
if(length === 1){
return array;
}
const mid = Math.floor(length/2),
left = array.slice(0,mid),
right = array.slice(mid, length);
return merge(mergeSort(left), mergeSort(right))
};
const merge = (left,right)=>{
const result = [];
let il=0,ir=0;
while(il<left.length && ir < right.length){
if(left[il]<right[ir]){
result.push(left[il++]);
}else{
result.push(right[ir++]);
}
}
while(il<left.length){
result.push(left[il++]);
}
while(ir<right.length){
result.push(right[ir++]);
}
return result;
};
快速排序
快速排序是最常用的排序算法了，它的复杂度为O(nlogn)，和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组。
在这个排序中，函数式版和命令式版略为不同。
函数式版的思想为，每次抽取数组的第一号元素，剩下的元素中，把比一号元素小的都放在一号元素的左边，剩下的放在右边，组成一个新的数组。
并且对剩下的大/小数组进行递归，直至完成排序。这个排序算法比node原生的排序都要快，有兴趣的朋友可以试试。详情请撸以下代码。
//函数式版
const quick_sort =(array)=> {
if(array.length < 2) return array;
const arr = array.reduce((pre,cur,index)=>{
if(cur<array[0] && index !==0){
pre.left.push(cur);
return pre ;
}else if(cur >= array[0] && index !==0){
pre.right.push(cur);
return pre;
}
return pre;
},{left:[],right:[]});
return [...quick_sort(arr.left), array[0], ...quick_sort(arr.right)]
};
命令式版的思想为
- 首先，从数组中选择中间一项作为主元。
- 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。
移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交
换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之
前，而比主元大的值都排在主元之后。这一步叫作划分操作。 - 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的
子数组）重复之前的两个步骤，直至数组已完全排序。
//命令式版
const quick = (array,left,right)=>{
let index;
if(array.length>1){
index = partition(array,left,right);
if(left < index -1){
quick(array, left, index -1);
}
if(index<right){
quick(array, index, right);
}
}
return array
};
const partition = (array, left, right) =>{
const pivot = array[Math.floor((left+right)/2)];
let i = left,
j = right;
while(i<=j){
while(array[i]<pivot){
i++;
}
while(array[j]>pivot){
j--;
}
if(i<=j){
[array[i],array[j]]=[array[j],array[i]];
i++;
j--;
}
}
return i;
};
网友评论