专栏首页vue学习JS数据结构与算法-快速排序与二分查找算法

JS数据结构与算法-快速排序与二分查找算法

  1. 快速排序 快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法通过不断重复这个步骤知道所有数据都是有序的。
  • 算法实现 这个算法首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行,将列表中小于基准值的元素移到数组的底部(左边),将大于基准值的元素移到数组的顶部(右边)。 ①选择一个基准元素,将列表分成两个子序列; ②对列表重新排序,将所有小于基准值的元素放在基准值前面,所有大于基准值的元素放在基准值的后面; ③分别对较小的元素的子序列和较大元素的子序列重复步骤①和步骤②。
function qSort(list) {
    //检查数组的长度是否为0,是则不需要任何排序,返回空数组
    if(list.length == 0) {
        return [];
    }
    //创建两个数组,一个用来存放比基准小的元素,另一个存放比基准值大的元素
    var left = [];
    var right = [];
    //基准值取自数组的第一个元素
    var pivot = list[0];
    //遍历数组,根据它们与基准值的关系放到合适的数组中
    for(var i=1;i<list.length;i++) {
        if(list[i] < pivot) {
            left.push(list[i]);
        }else{
            right.push(list[i]);
        }
    }
    //然后对于较小的数组和较大的数组分别递归调用这个函数
    return qSort(left).concat(pivot,qSort(right));
}

var test = [4,3,5,1,2];

console.log(qSort(test)); //[1,2,3,4,5]

ps:递归的过程大概是这样

灵魂画手

  1. 二分法算法 如果你要查找的数据是有序的,二分查找算法比顺序查找算法更高效。
  • 算法理解 二分搜索算法的原理和猜数字游戏类似,就是那个有人说“我正想着一个1到100的数字”的游戏。我们每回应一个数字,那个人就会说这个数字是高了、低了还是对了。
  • 算法描述 ①选择中间值; ②如果选择的值是待搜索的值,算法结束并返回; ③如果待搜索值比选中值要小,则返回步骤①并在选中值左边的子数组中寻找。 ④如果待搜索值比选中值要大,则返回步骤①并在选中值右边的子数组中寻找。
  • 算法实现
function binSearch(arr,data) {
    //将传入的数组用快速排序算法排序一下
    var arr = qSort(arr);
    //将最后一个元素所在的位置设为上边界
    var upperBound = arr.length-1;
    //将数组的第一个位置设为下边界
    var lowerBound = 0;

    while(lowerBound <= upperBound) {
        //中点
        var mid = Math.floor((upperBound + lowerBound)/2);
        //如果待查询的值大于中点元素,则将下边界设置为中点元素所在下标加1,也就是选取数组的右半边(不包括中点元素),然后再在里面查找
        if(arr[mid] < data) {
            lowerBound = mid+1;
        //如果待查询的值小于中点元素,同理如上
        }else if(arr[mid] > data) {
            upperBound = mid-1;
        //否则如果相等,返回
        }else {
            return mid;
        }
    }
    return -1;
}

var test = [1,2,3,4,5,6];
console.log(binSearch(test,2)); //位置"1"

执行步骤:

执行步骤.png

参考学习

《数据结构与算法javascript描述》 《学习javascript数据结构与算法》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Mysql 的安装

    Ewall
  • 18、webpack从0到1-结语

    Ewall
  • vscode+eslint让你编程快到飞起

    Ewall
  • Redis 持久化之AOF持久化&混合持久化

    RDB(snapshotting) 是一种内存快照的方式进行持久化,AOF(append-only-file)是通过追加写入命令的方式进行持久化,混合持久化是指...

    邹志全
  • 数据结构学习路线

    风骨散人Chiam
  • [jQuery笔记] jQuery语法

    jquert语法通常是选取html元素,并对所则的元素执行某些操作(actions)

    行 者
  • JQuery基础

    学习jQuery的时候,很快过了一遍,发现好多知识点不清晰。看来还是要写出来加深印象,平时多练习! jQuery是一个Javascript函数库,轻量级,“写得...

    用户1149564
  • Redis AOF 持久化详解

    Redis 是一种内存数据库,将数据保存在内存中,读写效率要比传统的将数据保存在磁盘上的数据库要快很多。但是一旦进程退出,Redis 的数据就会丢失。

    程序员历小冰
  • WebSockets实战:在 Node 和 React 之间进行实时通信[每日前端夜话0x6C]

    Web 为了支持客户端和服务器之间的全双工(或双向)通信已经走过了很长的路。这是 WebSocket 协议的主要目的:通过单个 TCP 套接字连接在客户端和服务...

    疯狂的技术宅
  • Redis AOF 持久化详解

    Redis 是一种内存数据库,将数据保存在内存中,读写效率要比传统的将数据保存在磁盘上的数据库要快很多。但是一旦进程退出,Redis 的数据就会丢失。

    程序员历小冰

扫码关注云+社区

领取腾讯云代金券