资讯专栏INFORMATION COLUMN

常见排序及查找算法的JS实现

icattlecoder / 784人阅读

摘要:冒泡排序临时交换变量记录数组长度计数,记录一共进行了多少次交换数组长度为输出数组成都外层循环排序出数组的的值交换标志内层循环,从底往上冒泡,将小泡浮到位置比较两个元素大小,并交换位置确定交换标志记录比较元素的次数共交换了次输出数

1.冒泡排序
function bubbleSort(arr) {
            var temp;                                //临时交换变量
            let n = arr.length;                      //记录数组长度
            let count=0;                             //计数,记录一共进行了多少次交换
            //document.write("数组长度为:"+n+"
") //输出数组成都 for (let i=0; ii; j-- ) { //内层循环,从底往上冒泡,将小泡浮到arr[i]位置 //alert(0); if (arr[j-1]>arr[j]) { //比较两个元素大小,并交换位置 temp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=temp; flag=flag+1; //确定交换标志 count=count+1; //记录比较元素的次数 //console.log(flag); //console.log("共交换了:"+count+"次"); } //console.log(arr) //输出数组 } if (flag==0) { //跳出循环 break; } } document.write("冒泡排序执行次数为:"+count+"
") return arr; //返回数组 }
2.简单选择排序
function selectSort(arr) {
        let temp;
        let n = arr.length;
        let count =0;
        for (let i=0; i
3.直接插入排序
function insertSort(arr) {
        let i,j;
        let n= arr.length;
        let count = 0;
        for (i=1; iarr[-1];j--) {  //当i位置前面的值比哨兵小,后移i位置的值,并插入哨兵到原先i位置
                    arr[j+1] = arr[j];
                    arr[j] = arr[-1];
                    count++;
                }
            }
        }
    document.write("直接插入排序执行次数为:"+count);
    return arr;
}
4.希尔排序
function shellSort(arr) {
     let d = arr.length;
     let i;
     let temp; //暂存
     do {
        //设置增量
       d = Math.floor(d / 3) + 1;
       for (i = d ; i < arr.length; i++) {
         if (arr[i] < arr[i - d]) {
           temp = arr[i];
           for (var j = i - d; j >= 0 && temp < arr[j]; j -=d) {
               arr[j + d] = arr[j];
               arr[j] = temp;
           }
         }
       }
     }
     while (d > 1)
     return arr;
    }
5.去重算法
function unique(arr) {
            let brr=[];
            for (let i=0; i
6.快速排序
function partition(arr,low,high) {
        let    temp=arr[low],   //基准值
            changetemp;         //用于交换的临时变量
        while (low=temp) {  
                high--;
            }               //当从high往前扫时,大于基准值时,high--
            //swap(arr, low, high);   //当从high往前扫时,小于基准值时,交换基准值和arr[high]位置
            changetemp=arr[low];
            arr[low]=arr[high];
            arr[high]=changetemp;
            while(low");
            quick(arr, pivot+1, high);          //对枢轴值后面的序列排序   
        }
        //return pivot;                        //返回枢轴值
        return arr;                            //返回排序后的数组
    }
7.使用JS方法并将形参减少为仅输入一个数组的快排
function quickSort (arr) {
        if (arr.length<=1) {
            return arr;
        }
        let left = [],
            right = [],
            pivotIndex = Math.floor(arr.length/2);
        let pivot = arr.splice(pivotIndex,1)[0];
        for (let i=0; i
8.JS实现归并排序
function mergeSort (arr) {
    //合并两个有序数组为一个数组
    function merge(left,right) {
        let arr=[];
        while (left.length && right.length) {
            if (left[0] < right[0]) {
                arr.push(left.shift());
            } else {
                arr.push(right.shift());
            }
        }
        return arr.concat(left,right);
    }

    let len=arr.length;
    if (len <= 1) {
        return arr;
    } else {
        let index = Math.floor(len/2),
            left = arr.slice(0,index),
            right = arr.slice(index);
        return merge(mergeSort(left),mergeSort(right));//用递归对数组进行拆分,再返回合并后的数组
    }
}
9.堆排序
function heapSort(array) {
    var result = array.slice(0);
    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    function maxHeapify(array, index, heapSize) {
        var iMax, iLeft, iRight;
        while (true) {
          iMax = index;
          iLeft = 2 * index + 1;
          iRight = 2 * (index + 1);
          
          if (iLeft < heapSize && array[index] < array[iLeft]) {
              iMax = iLeft;
          }

          if (iRight < heapSize && array[iMax] < array[iRight]) {
              iMax = iRight;
          }

          if (iMax != index) {
              swap(array, iMax, index);
              index = iMax;
          } else {
              break;
          }
        }
    }

    function buildMaxHeap(array) {
        var i, iParent = Math.floor(array.length / 2) - 1;

        for (i = iParent; i >= 0; i--) {
            maxHeapify(array, i, array.length);
        }
    }

    function sort(array) {
        buildMaxHeap(array);

        for (var i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            maxHeapify(array, 0, i);
        }
        return array;
    }

        return sort(result);
}
10.JS实现顺序查找
function listSearch(arr,data) {
    var result;
    for (var i = 0;i
11.JS实现二分查找
function binarySearch(arr,key) {
    var low = 0,
        high = arr.length-1;
    while (low <= high) {
            var mid = parseInt((low+high)/2);    
            if (key < arr[mid]) {
                high = mid-1;
            } else if (key > arr[mid]) {
                low = mid+1;
            } else {
                return mid;
            }
    }
    return -1;
}
        
12.统计字符串中出现次数最多的字符
function count(str) {
    var obj = {},
        mostStr = "",
        key;
    for(var i = 0; i obj[mostStr]) {
            mostStr = key
        }
    }
    return [mostStr,obj[mostStr]]
}
13.斐波拉契数列递归写法
function fibonicco(n) {
    if (n ===1 || n === 2) {
        return 1;
    } else {
        return fibonicco(n-1)+fibonicco(n-2);
    }
}
14.斐波拉契数列迭代写法
function fibonicco(n) {
    var a,b,res;
    a = b = res =1;
    for (var i =3; i<=n; i++) {
        res = a+b;
        a = b;
        b = res;
    }
    return res;
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/83580.html

相关文章

  • JavaScript数据结构和算法

    摘要:栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构,比如下面介绍的二叉查找树。 前言 在过去的几年中,得益于Node.js的兴起,JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器,程序员发现他们需要更多传统语言(比如C++和Java)提供的工具。这些工具包括传统的数据结构(如链表,栈,队列,图等),...

    EastWoodYang 评论0 收藏0
  • 前端排序算法总结;前端面试题2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    aaron 评论0 收藏0
  • 前端排序算法总结;前端面试题2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    ARGUS 评论0 收藏0
  • 前端排序算法总结;前端面试题2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    April 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<