算法 数据结构 系统设计要点

算法:设计解决具体问题的流程，有评价流程的可量化指标

1.开始在0位置，每一步向左或向右，第i次向左或向右i步，问从0到x，至少几次？

function reactNumber(target){
  target = Math.abs(target);
  let l=0,r=target,m=0,near=0;
  if(target == 0){
      return 0;
  }
  while(l<=r){
    m=(l+r)/2;
    if(sum[m]==target){
        near = m;
        r = m-1;
    }else{
      l = m +1;
    }
  }
  if(sum[near] == target){
    return near
  }
  if(((sum[near] - target) & 1) == 1){
    near++;
  }
  return near;
}
function sum(n){
  return (n+(n+1))/2
}

2.正反冒泡

function bubbleSort(arr){
  let low=0,hight=arr.length;
  while(low<hight){
    for(let i = low;i<high;i++){
      if(arr[i]>arr[i+1]){
        [arr[i],arr[i+1]] = [arr[i+1],arr[i]]
      }
    }
    hight--;
    for(let i = hight;i>low;i--){
      if(arr[i]>arr[i-1]){
        [arr[i-1],arr[i]] = [arr[i],arr[i]]
      }
    }
    low++;
  }
}

3.三路快排

function quickSort3(arr){
  if(arr.length == 0){
    return []
  }
  let left=[],center=[],right=[],pivot=arr[0];
  for(let i=0;i<arr.length;i++){
    if(arr[i]<pivot){
      left.push(arr[i])
    } else if(arr[i] == pivot){
      center.push(arr[i])
    } else{
      right.push(arr[i])
    }
  }
  return [...quickSort3(left),...center,...quickSort3(right)]
}

4.二分插入排序

function insertSort(arr){
  for(let i =0;i<arr.length;i++){
    const temp = arr[i];
    let left =0,right=i-1;
    while(left<=right){
      const mid = parseInt((left+right)/2);
      if(temp < arr[mid]){
        right = mid-1;
      } else{
        left = mid+1;
      }
    }
    for(let j=i-1;j>=left;j-- ){
      arr[j+1]=arr[j]
    }
    arr[left] = temp;
  }
  return arr
}

5.二元选择排序

function selectSort(arr){
  let len=arr.length,min,max,temp;
  for(let i = 0;i<Math.floor(len/2);i++){
    min=i;
    max=i;
    for(let j = i;j<len-i;i++){
      if(arr[j]>arr[max]){
        max = arr[j];
        continue
      }
      if(arr[j]<arr[i]){
        min = arr[j];
      }
    }
    temp= arr[min];
    arr[min]= arr[i];
    arr[i] = temp;
    temp = arr[max];
    arr[max] = arr[len-i-1]
    arr[len-i-1] = temp
  }
  return arr
}