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 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

“基数排序”展现Python的优雅与简洁

在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

3005
来自专栏大前端开发

ES6特性之:参数默认值

作为一个开发者,跟进行业步伐是非常需要的,不能躺在现有的知识和经验温床上做美梦。JavaScript的ES2015标准(即我们说的ES6)在2016年已经被广泛...

854
来自专栏菩提树下的杨过

as3:Function以及call,apply

Function类在as3中是直接从Object继承下来的,通常开发者定义的每一个function,均可以认为是Function类的一个实例。  如果硬要跟c#...

1929
来自专栏IT可乐

Java数据结构和算法(七)——链表

  前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷。在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且...

3667
来自专栏黑泽君的专栏

Java语言中:在数据类型的讲解中补充的几个小问题

============================================================================= 1...

761
来自专栏从零开始学 Web 前端

js变量提升与函数提升的详细过程

在这里我会从 Web 前端零基础开始,一步步学习 Web 相关的知识点,期间也会分享一些好玩的项目。现在就让我们一起进入 Web 前端学习的冒险之旅吧!

2013
来自专栏Brian

C++11基础学习系列一

---- 概述 C++11标准越来越趋于稳定和成熟,国外c++11如火如荼而国内却依然处于观望期。每当提到C++很多程序员都很抵触,特别是学术界的呼声更高一些。...

2754
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过...

3406
来自专栏趣谈编程

直接插入排序

登鹳雀楼 唐·王之涣 白日依山尽,黄河入海流。  欲穷千里目,更上一层楼。 面试官:聊聊插入排序 插入排序是一种比较简单直观的排序算法,适用处理数据量比...

3935
来自专栏编程

Python函数之一切皆对象

今天我们要讲的是 对象 避免误会,常老师先澄清一下,这里面说的对象指的是object,不是你的lover,也不是你的sweetheart…… 有的小伙伴可能会觉...

1967

扫码关注云+社区

领取腾讯云代金券