JavaScript常用算法（面试）------Sestid

柔光的暖阳◎ 2024-04-18 16:33 69阅读 0赞

**目录**

(一)快速排序算法

(二)希尔排序，也称递减增量排序算法

(三)选择排序算法

(四)归并排序算法

(五)冒泡排序算法

(六)插入排序算法

(七)二分插入排序算法

--------------------

### (一)快速排序算法 ###

1.1: 先从数列中取出一个数作为“基准”。

1.2: 分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。

1.3: 再对左右区间重复第二步，直到各区间只有一个数。

代码实现：

var quickSort = function(arr) {
        if (arr.length <= 1) { return arr; }
        var pivotIndex = Math.floor(arr.length / 2);   //基准位置（理论上可任意选取）
        var pivot = arr.splice(pivotIndex, 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));  //链接左数组、基准数构成的数组、右数组
    };

### (二)希尔排序，也称递减增量排序算法 ###

1.1: 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

1.2: 按增量序列个数 k，对序列进行 k 趟排序；

1.3: 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码实现：

function shellSort(arr) {
        var len = arr.length,
            temp,
            gap = 1;
        while(gap < len/3) {          //动态定义间隔序列
            gap = gap*3+1;
        }
        for (gap; gap > 0; gap = Math.floor(gap/3)) {
            for (var i = gap; i < len; i++) {
                temp = arr[i];
                for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j+gap] = arr[j];
                }
                arr[j+gap] = temp;
            }
        }
        return arr;
    }

### (三)选择排序算法 ###

1.1: 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

1.2: 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

1.3: 重复第二步，直到所有元素均排序完毕。

代码实现：

function selectionSort(arr) {
        var len = arr.length;
        var minIndex, temp;
        for (var i = 0; i < len - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                    minIndex = j;                 // 将最小数的索引保存
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

### (四)归并排序算法 ###

1.1: 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

代码实现：

function merge(leftArr, rightArr){  
        var result = [];  
        while (leftArr.length > 0 && rightArr.length > 0){  
          if (leftArr[0] < rightArr[0])  
            result.push(leftArr.shift()); //把最小的最先取出，放到结果集中   
          else   
            result.push(rightArr.shift());  
        }   
        return result.concat(leftArr).concat(rightArr);  //剩下的就是合并，这样就排好序了  
    }  
    
    function mergeSort(array){  
        if (array.length == 1) return array;  
        var middle = Math.floor(array.length / 2);       //求出中点  
        var left = array.slice(0, middle);               //分割数组  
        var right = array.slice(middle);  
        return merge(mergeSort(left), mergeSort(right)); //递归合并与排序  
    }  
    
    var arr = mergeSort([32,12,56,78,76,45,36]);
    console.log(arr);   // [12, 32, 36, 45, 56, 76, 78]

### (五)冒泡排序算法 ###

1.1: 先从数列中取出一个数作为“基准”。

1.2: 第一轮的时候最后一个元素应该是最大的一个。

1.3: 按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。

代码实现：

function sortarr(arr){
        for(i=0;i<arr.length-1;i++){
            for(j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    var temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        return arr;
    }

### (六)插入排序算法 ###

1.1: 从第一个元素开始，该元素可以认为已经被排序；

1.2: 取出下一个元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，将该元素移到下一位置；

1.3: 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后；

1.4: 重复步骤2~5。

代码实现：

function insertSort(arr){
        var len = arr.length;
            for (var i = 1; i < len; i++) {
                var key = arr[i];
                var j = i - 1;
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = key;
             }
        return arr;
    }

### (七)二分插入排序算法 ###

1.1: 从第一个元素开始，该元素可以认为已经被排序；

1.2: 取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置；

1.3: 将新元素插入到该位置后；

1.4: 重复上述两步;

代码实现：

function insertSort(arr){
        var len = arr.length;
            for (var i = 1; i < len; i++) {
                var key = arr[i];
                var j = i - 1;
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = key;
             }
        return arr;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读

相关 JavaScript常用算法（面试）------Sestid

*目录** (一)快速排序算法 (二)希尔排序，也称递减增量排序算法 (三)选择排序算法 (四)归并排序算法 (五)冒泡排序算法 (六)插入排序算法 (七)...

柔光的暖阳◎/ 2024年04月18日 16:33/ 0 赞/ 70 阅读

相关算法常用面试题汇总

1.说一下什么是二分法？使用二分法时需要注意什么？如何用代码实现？二分法查找（Binary Search）也称折半查找，是指当每次查询时，将数据分为前后两部分，再用中值

不念不忘少年蓝@/ 2023年10月05日 12:35/ 0 赞/ 34 阅读

相关 JavaScript 总结【面试笔记 + 经典面试题 + 常用算法】，帮你搞定前端 JavaScript 面试！

![fea183c36f30269d7a5683038623e24b.png][] 前言：据 Stackoverflow 的 2021 年开发者调查，JavaScri

曾经终败给现在/ 2022年10月13日 12:59/ 0 赞/ 172 阅读

相关常用javascript

1. 后退加刷新 window.location.replace(document.referrer); 1. 禁止网页另存为 <noscript><

素颜马尾好姑娘i/ 2022年06月13日 04:49/ 0 赞/ 234 阅读

相关常用算法

冒泡排序：冒泡排序是一种极其简单的排序算法，也是我接触到的第一种算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复

素颜马尾好姑娘i/ 2022年06月08日 00:18/ 0 赞/ 195 阅读

相关 JavaScript常用基础算法

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] 基础算法一、排序 1. 冒泡排序 //冒泡排

我就是我/ 2022年01月15日 11:41/ 0 赞/ 254 阅读

相关面试常用算法整理

知识点：基本算法 algorithms 1.线性查找 2.二分查找描述：在数组中查找指定数值首先要求该组元素必须是有序的，假设默认是从小到大排列，使用该组元素的中

绝地灬酷狼/ 2021年12月21日 23:51/ 0 赞/ 298 阅读

相关面试常用算法

1. 求数组中和最大的子序列 2. 快速排序基本思想在于把排序对象分割为两列子序列，而其中一个子序列的值都大雨另一子序列，并且进一步递归排序所有子序列 stat

傷城~/ 2021年10月24日 02:32/ 0 赞/ 361 阅读

相关 Java笔试面试-算法常用面试题

1.说一下什么是二分法？使用二分法时需要注意什么？如何用代码实现？二分法查找（Binary Search）也称折半查找，是指当每次查询时，将数据分为前后两部分，再用中值

红太狼/ 2021年09月23日 11:16/ 0 赞/ 477 阅读

相关面试难点！常用算法技巧之“滑动窗口”

算法简介滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。可以想象成队列，一端在push元

ゝ一世哀愁。/ 2021年07月24日 20:08/ 0 赞/ 582 阅读