手写JS系列（二）

1.手写二分查找

//假设一个数组已经排好序了，现在要在数组里找一个数flag的位置。 //首先先找到长度中间位置，通过与中间位置的数比较，比中间值大在右边找， //比中间值小在左边找。然后再在两边各自寻找中间值，持续进行，直到找到全部位置。 function binarySearch(arr,flag){ let h=arr.length-1; let l=0; while(l<=h){ let m=Math.floor((h+l)/2); if(arr[m]==flag){ return m} if(arr[m]<flag) { l=m+1; }else{ h=m-1; } } return flase }

2.手写冒泡排序

//比较相邻两个元素的，如果前一个比后面的大，就交换位置， //第一轮之后最后一个元素是最大的一个，按照这种方法依次比较。 function bubbleSort(arr){ for(let i=arr.length-1;i>=0;i--){ for(j=0;j<i;j++){ if(arr[j]>arr[j+1]){ let tmp=arr[j+1]; arr[j+1]=arr[j] arr[j]=tmp } } } return arr } //平均时间复杂度：O(n^2) //空间复杂度：O(1)

3.手写选择排序

//选择排序第一次将第0位置的人取出, 和后面的人(1, 2, 3...)依次比较, //如果后面的人更小, 那么就交换.这样经过一轮之后, 第一个肯定是最小的人. function selectionSort(arr){ let len=arr.length; for(var i=0;i<len-1;i++){ var min=i; for(var j=min+1;j<len;j++){ if(arr[min]>arr[j]){ min=j } } tmp=arr[i]; arr[i]=arr[min] arr[min]=tmp; } return arr } //平均时间复杂度：O(n^2) //空间复杂度：O(1)

4.手写插入排序

//插入排序的思路：从第一个元素开始，该元素可认为已经被排序，取出下一个元素 //在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，将该元素移到 //下一位置，重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置，将新元 //素插入到该位置后，重复上面的步骤 function insertSort(arr){ //外层循环：从第1个位置开始获取数据，向前面局部有序进行插入 for(var i=0;i<arr.length;i++){ var temp=arr[i]; var j=i; //内层循环：获取i位置的元素，和前面的数据依次进行比较 while(arr[j-1]>temp&&j>0){ arr[j]=arr[j-1] j-- } arr[j]=temp; } } //平均时间复杂度：O(n^2) //空间复杂度：O(1)

5.手写希尔排序

//先将整个待排序的数据集分割为若干组，然后对每一个组分别进行直接插入排序。 //此时每个组内插入排序所作用的数据量小，效率比较高。 //希尔排序相当于插入排序的升级版 function shellSort(arr){ //获取数组的长度 var len=arr.length; //初始化增量 var gap=Math.floor(len/2); //while循环，gap不断减小 while(gap>=1){ //以gap作为间隔，进行分组，对分组进行插入排序 for(var i=gap;i<len;i++){ var temp=arr[i]; j=i; while(arr[j-gap]>temp&&j>gap-1){ arr[j]=arr[j-gap]; j-=gap; } //将j位置的元素赋值temp arr[j]=temp } gap=Math.floor(gap/2) } } //平均时间复杂度：O(nlogn) //空间复杂度：O(1)

6.手写快速排序

//相当于冒泡排序的升级版 //快速排序可以在一次循环中，找出某个元素的正确位置，并且该元素之后不需要任何移动 //快速排序最重要的思想是分而治之 //利用二分查找对冒泡排序的改进，选一个元素作为基准，把数字分为两部分， //一部分全部比它小，一部分全部比它大，然后递归调用，在两部分都进行快排。 function quickSort(arr){ if(arr.length<=1){ return arr } //取出中间位置的元素 let middle=Math.floor(arr.length/2); let flag=arr.splice(middle,1)[0]//删除中间这个元素，返回的是一个数组 let left=[]; let right=[]; for(let i=0;i<arr.length;i++){ if(arr[i]<flag){ left.push(arr[i]); }else{ right.push(arr[i]) } } return quickSort(left).concat([flag],quickSort(right)); }