Js七种排序算法

更新日期: 2020-09-21阅读: 1.9k标签: 算法

一、冒泡排序

冒泡排序的思路:遍历数组,然后将最大数沉到最底部;<br/>时间复杂度:O(N^2);<br/>空间复杂度:O(1)
function BubbleSort(arr) {
    if(arr == null || arr.length <= 0){
        return [];
    }
    var len = arr.length;
    for(var end = len - 1; end > 0; end--){
        for(var i = 0; i < end; i++) {
            if(arr[i] > arr[i + 1]){
                swap(arr, i, i + 1);
            }
        }
    }
    return arr;
}
function swap(arr, i, j){
    // var temp = arr[i];
    // arr[i] = arr[j];
    // arr[j] = temp;
    //交换也可以用异或运算符
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}


二、选择排序

选择排序的实现思路:遍历数组,把最小数放在头部;<br/>时间复杂度:O(N^2);<br/>空间复杂度:O(1)
function SelectionSort(arr) {
    if(arr == null || arr.length < 0) {
        return [];
    }
    for(var i = 0; i < arr.length - 1; i++) {
        var minIndex = i;
        for(var j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
    return arr;
}

function swap(arr, i, j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}


三、插入排序

插入排序实现思路:将一个新的数,和前面的比较,只要当前数小于前一个则和前一个交换位置,否则终止;<br/>时间复杂度:O(N^2);<br/>空间复杂度:O(1)
function insertSort(arr) {
    if(arr == null  || arr.length <= 0){
        return [];
    }
    var len = arr.length;
    for(var i = 1; i < len; i++) {
        for(var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
    return arr;
}

function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


四、归并排序

归并排序的思路:<br/>1.先左侧部分排好序<br/>2.再右侧部分排好序<br/>3.再准备一个辅助数组,用外排的方式,小的开始填,直到有个动到末尾,将另一个数组剩余部分拷贝到末尾<br/>4.再将辅助数组拷贝回原数组<br/>时间复杂度:O(N * logN)<br/>空间复杂度:O(N)
// 递归实现

function mergeSort(arr){
    if(arr == null  || arr.length <= 0){
        return [];
    }
    sortProcess(arr, 0, arr.length - 1);
    return arr;
}

function sortProcess(arr, L, R){
    //递归的终止条件,就是左右边界索引一样
    if(L == R){
        return;
    }
    var middle = L + ((R - L) >> 1);//找出中间值
    sortProcess(arr, L, middle);//对左侧部分进行递归
    sortProcess(arr, middle + 1, R);//对右侧部分进行递归
    merge(arr, L, middle, R);//然后利用外排方式进行结合
}

function merge(arr, L, middle, R){
    var help = [];
    var l = L;
    var r = middle + 1;
    var index = 0;
    //利用外排方式进行
    while(l <= middle && r <= R){
        help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }
    while(l <= middle){
        help.push(arr[l++]);
    }
    while(r <= R){
        help.push(arr[r++]);
    }

    for(var i = 0; i < help.length; i++) {
        arr[L + i] = help[i];
    }
    //arr.splice(L, help.length, ...help);//这个利用了ES6的语法
}
// 循环实现
function mergeSort(arr){
    if(arr ==null || arr.length <= 0){
        return [];
    }
    var len = arr.length;
    //i每次乘2,是因为每次合并以后小组元素就变成两倍个了
    for(var i = 1; i < len; i *= 2){
        var index = 0;//第一组的起始索引
        while( 2 * i  + index <= len){
            index += 2 * i;
            merge(arr, index - 2 * i, index - i, index);
        }
        //说明剩余两个小组,但其中一个小组数据的数量已经不足2的幂次方个
        if(index + i < len){
            merge(arr, index, index + i, len);
        }
    }
    return arr;
}

//利用外排的方式进行结合
function merge(arr, start, mid, end){
    //新建一个辅助数组
    var help = [];
    var l = start, r = mid;
    var i = 0;
    while(l < mid && r < end){
        help[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }
    while(l < mid){
        help[i++] = arr[l++];
    }
    while(r < end){
        help[i++] = arr[r++];
    }
    for(var j = 0; j < help.length; j++){
        arr[start + j] = help[j];
    }
}


五、快速排序

快速排序实现思路:随机取出一个值进行划分,大于该值放右边,小于该值放左边(该算法在经典快排的基础上经过荷兰国旗思想和随机思想进行了改造)<br/>时间复杂度:O(N*logN) <br/>空间复杂度:O(logN)
function quickSort(arr) {
    if(arr == null || arr.length <= 0){
        return [];
    }
    quick(arr, 0, arr.length - 1);
}

function quick(arr, L, R){
    //递归结束条件是L >= R
    if(L < R){
        //随机找一个值,然后和最后一个值进行交换,将经典排序变为快速排序
        swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
        //利用荷兰国旗问题获得划分的边界,返回的值是小于区域的最大索引和大于区域的最小索引,在这利用荷兰国旗问题将等于区域部分就不用动了
        var tempArr = partition(arr, L, R, arr[R]);
        quick(arr, L, tempArr[0]);
        quick(arr, tempArr[1], R);
    }
}
//返回值是小于区域最后的索引和大于区域的第一个索引
function partition(arr, L, R, num){
    var less = L - 1;
    var more = R + 1;
    var cur = L;
    while(cur < more){
        if(arr[cur] < num){
            swap(arr, ++less, cur++);
        }else if(arr[cur] > num) {
            swap(arr, --more, cur);
        }else{
            cur++;
        }
    }
    return [less, more];
}
function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


六、堆排序

堆排序思路:<br/>1.让数组变成大根堆<br/>2.把最后一个位置和堆顶做交换<br/>3.则最大值在最后,则剩下部分做heapify,则重新调整为大根堆,则堆顶位置和该部分最后位置做交换<br/>4.重复进行,直到减完,则这样最后就调整完毕,整个数组排完序(为一个升序)<br/>时间复杂度:O(N * logN)<br/>空间复杂度:O(1)
function heapSort(arr) {
    if(arr == null || arr.length <= 0) {
        return [];
    }

    //首先是建立大顶堆的过程
    for(var i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
    var size = arr.length;//这个值用来指定多少个数组成堆,当得到一个排序的值后这个值减一
    //将堆顶和最后一个位置交换
    /**
     * 当大顶堆建立完成后,然后不断将最后一个位置和堆顶交换;
     * 这样最大值就到了最后,则剩下部分做heapify,重新调整为大根堆,则堆顶位置和倒数第二个位置交换,重复进行,直到全部排序完毕*/
    //由于前面已经是大顶堆,所以直接交换
    swap(arr, 0, --size);
    while(size > 0) {
        //重新变成大顶堆
        heapify(arr, 0, size);
        //进行交换
        swap(arr, 0, --size);
    }
}

//加堆过程中
function heapInsert(arr, index) {
    //比较当前位置和其父位置,若大于其父位置,则进行交换,并将索引移动到其父位置进行循环,否则跳过
    //结束条件是比父位置小或者到达根节点处
    while(arr[index] > arr[parseInt((index - 1) / 2)]){
        //进行交换
        swap(arr, index, parseInt((index - 1) / 2));
        index = parseInt((index - 1) / 2);
    }
}
//减堆过程
/**
 * size指的是这个数组前多少个数构成一个堆
 * 如果你想把堆顶弹出,则把堆顶和最后一个数交换,把size减1,然后从0位置经历一次heapify,调整一下,剩余部分变成大顶堆*/
function heapify(arr, index, size) {
    var left = 2 * index + 1;
    while(left < size) {
        var largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
        largest = arr[index] > arr[largest] ? index : largest;

        //如果最大值索引和传进来索引一样,则该值到达指定位置,直接结束循环
        if(index == largest) {
            break;
        }

        //进行交换,并改变索引和其左子节点
        swap(arr, index, largest);
        index = largest;
        left = 2 * index + 1;
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


七、桶排序

桶排序会经历三次遍历:准备一个数组、遍历一遍数组、重构一遍数组,是非基于比较的排序,下面以一个问题来阐述其思路。<br/>问题:<br/> 给定一个数组,求如果排序之后,相邻两个数的最大差值,要求时间复杂度O(N),且要求不能用基于比较的排序<br/>
思路:<br/>1.准备桶:数组中有N个数就准备N+1个桶<br/>2.遍历一遍数组,找到最大值max和最小值min
。若min = max,则差值=0;若min≠max,则最小值放在0号桶,最大值放在N号桶,剩下的数属于哪个范围就进哪个桶<br/>3.根据鸽笼原理,则肯定有一个桶为空桶,设计该桶的目的是为了否定最大值在一个桶中,则最大差值的两个数一定来自于两个桶,但空桶两侧并不一定是最大值<br/>4.所以只记录所有进入该桶的最小值min和最大值max和一个布尔值表示该桶有没有值<br/>5.然后遍历这个数组,如果桶是空的,则跳到下一个数,如果桶非空,则找前一个非空桶,则最大差值=当前桶min - 上一个非空桶max,用全局变量更新最大值<br/>时间复杂度:O(N)<br/>空间复杂度:O(N)
function maxGap(arr) {
    if(arr == null || arr.length <= 0) {
        return 0;
    }
    var len = arr.length;
    var max = -Infinity, min = Infinity;
    //遍历一遍数组,找到最大值max和最小值min
    for(var i = 0; i < len; i++) {
        max = max > arr[i] ? max : arr[i];
        min = min > arr[i] ? arr[i] : min;
    }

    //若min = max,则差值为0;
    if(min == max) {
        return 0;
    }

    var hasNum = new Array(len + 1);
    var mins = new Array(len + 1);
    var maxs = new Array(len + 1);

    var bid = 0;//指定桶的编号

    for(var i = 0; i < len; i++) {
        bid = bucket(arr[i], min, max, len);//获得该值是在哪个桶//由于有N+1个桶,所以间隔就是N个,所以此处除以的是len,然后通过这个函数得到应该放到哪个桶里
        maxs[bid] = hasNum[bid] ? Math.max(arr[i], maxs[bid]) : arr[i];
        mins[bid] = hasNum[bid] ? Math.min(arr[i], mins[bid]) : arr[i];
        hasNum[bid] = true;
    }

    var res = 0;
    var lastMax = maxs[0];

    for(var i = 0; i < len + 1; i++) {
        if(hasNum[i]) {
            res = Math.max(mins[i] - lastMax, res);
            lastMax = maxs[i];
        }
    }
    return res;
}

//获得桶号
//这个函数用于判断在哪个桶中,参数分别为值、最小值、最大值、桶间隔
function bucket(value, min, max, len) {
    return parseInt((value - min) / ((max - min) / len));
}

链接: https://www.fly63.com/article/detial/9655

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!