前端经典八大算法

作者: Grandperhaps | 来源:发表于2021-06-16 21:19 被阅读0次

    1. 冒泡排序

    var arr = [1,56,9,6,3,5,8,2]
    function sort(arr){
      for(let i = 0;i<arr.length-1;i++){
        for(let j = 0;j<arr.length-1-i;j++){
          if(arr[j]>arr[j+1]){
            let temp = arr[j+1];
            arr[j+1] = arr[j];
            arr[j] = temp
          }
        }
      }
      return arr
    }
    sort(arr)
    console.log(arr);
    

    2. 插入排序

    var arr = [1,56,9,6,3,5,8,2]
    function sort(arr){
      for(var i =1;i<arr.length;i++){
        var val = arr[i];
        var last = i-1;
        while(last>=0 && arr[last]>val){
          arr[last+1] = arr[last]
          last--
        }
        arr[last+1] = val
      }
      return arr
    }
    sort(arr)
    console.log(arr);
    

    3. 快速排序

    var arr = [1,56,9,6,3,5,8,2]
    function quickSort(arr){
      if(arr.length<2){
        return arr
      }
      var mid = Math.floor(arr.length/2)
      var pivot = arr.splice(mid,1)[0]
      var left = [];
      var right = [];
      for(var i = 0;i<arr.length;i++){
        if(arr[i]<pivot){
          left.push(arr[i])
        } else {
          right.push(arr[i])
        }
      }
      return quickSort(left).concat(pivot,quickSort(right))
    }
    
    console.log(quickSort(arr));
    

    4. 归并排序

    var arr = [1,56,9,6,3,5,8,2];
    function mergeSort(arr) {
      var len = arr.length
      if(len<2){
        return arr
      }
      var mid = Math.floor(arr.length/2)
      var left = arr.slice(0,mid)
      var right = arr.slice(mid)
      return merge(mergeSort(left),mergeSort(right))
    }
    function merge(left,right) {
      var result = []
      while(left.length>0 && right.length>0){
        if(left[0]>right[0]){
          result.push(right.shift())
        } else {
          result.push(left.shift())
        }
      }
      while(left.length){
        result.push(left.shift())
      }
      while(right.length){
        result.push(right.shift())
      }
      arr = result
      return arr
    }
    mergeSort(arr)
    console.log(arr);
    

    5. 希尔排序

    var arr = [1,56,9,6,3,5,8,2]
    function sort(arr){
      var gap = arr.length
      for(gap = Math.floor(arr.length/2);gap>0;gap = Math.floor(gap/2)){
        for(var i=gap;i<arr.length;i++){
          var val = arr[i];
          var  j = i;
          while(j-gap>=0 && arr[j-gap]>val){
            arr[j] = arr[j-gap]
            j = j-gap
          }
          arr[j] = val
        }
      }
      return arr
    }
    sort(arr)
    console.log(arr);
    

    6. 堆排序

    var arr = [1,56,9,6,3,5,8,2]
    var len; 
    function buildMaxHeap(arr) {
      len = arr.length
      for(var i = 0;i<Math.floor(arr.length/2);i++){
        heapify(arr,i)
      }
    }
    function heapify(arr,i){
      var left = i*2+1;
      var right = i*2+2;
      var largest = i;
      if(left<len && arr[left]>arr[largest]){
        largest = left
      }
      if(right<len && arr[right]>arr[largest]){
        largest = right
      }
      if(largest !== i){
        swap(arr,i,largest)
        heapify(arr,largest)
      }
    }
    function swap(arr,i,j){
      var temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp
    }
    function heapSort(arr){
      buildMaxHeap(arr) 
      for(var i = arr.length-1;i>=0;i--){
        len-=1;
        swap(arr,0,i)
        heapify(arr,0)
      }
      return arr
    }
    console.log(heapSort(arr));
    

    7. 计数排序

    var arr = [1,56,9,6,3,5,8,2];
    function countingSort(arr, maxValue){
      var bucket = new Array(maxValue+1)
      var index = 0
      for(var i =0;i<arr.length;i++){
        if(!bucket[arr[i]]){
          bucket[arr[i]] = 0
        }
        bucket[arr[i]]++
      }
      for(var j = 0;j<bucket.length;j++){
        while(bucket[j]>0){
          arr[index++] = j
          bucket[j]--
        }
      }
      return arr
    }
    console.log(countingSort(arr,56));
    

    8. 选择排序

    var arr = [1,56,9,6,3,5,8,2]
    function sort(arr){
      for(let i =0;i<arr.length-1;i++){
        var index
        let min = i
        for(let j = i+1;j<arr.length;j++){
          if(arr[j]<arr[min]){
            min = j
          }
        }
          var temp = arr[i];
          arr[i] = arr[min];
          arr[min] = temp
      }
      return arr
    }
    sort(arr)
    console.log(arr);
    

    相关文章

      网友评论

        本文标题:前端经典八大算法

        本文链接:https://www.haomeiwen.com/subject/zywfyltx.html