常用算法 #8

tiger5wang · 2019-09-29T06:47:24Z

1. 常见排序算法

冒泡排序
基本思想：
对数组 arr 进行遍历，每次索引值 i 加 1 ，每次循环从数组的第一项开始，跟它后面的值比较，如果当前的值大于后一个值，则交换两个值的位置（升序）（如果当前的值小于后一个值交换两个值的位置为降序），一直比较到 arr.length - i 项（后面的 i 项是已经比较出的最大或最小的升序/降序项），直至循环结束

    bubbleSort = (arr) => {
        if(!Array.isArray(arr)) {
            alert('排序参数错误，请检查参数');
            return
        }
        // i 表示每一次循环时要遍历的数组长度
        for(let i=arr.length - 1; i >= 0; i--) {
            let mapCount = 0;   // 定义一个变量一保存此次遍历，前后两个值交换的次数，作为优化项
            // 遍历数组的前 i 项，两两相互比较
            for(let j=0; j<i; j++) {
                // 当前后两个值付合条件时，交换值
                if(arr[j] > arr[j+1]) {
                    mapCount++;
                    [arr[j], arr[j+1]] = [arr[j+1], arr[j]]  // 交换两个值的位置
                }
            }
            // 当此次遍历前后两个值比较次数为0时表示此时已经排序完成，停止遍历
            if(mapCount === 0) break;
        }
        console.log(arr)
        return arr
    };

快速排序
基本思想：
首先选取数组的任意一项作为目标项，然后进行对数组进行遍历，大于目标项的值都放到一个新的数组，小于目标项的值都放到另一个新的数组，然后对两个新数组进行做相同的行为，直到所有的数组只剩一项，也就是对分类数组进行递归，返回最终结果

     function quickSort(arr) {
            if(!Array.isArray(arr)) {
                alert('排序参数错误，请检查参数');
                return
            }
            // 如果只有一项，直接返回该数组
            if(arr.length <= 1) return arr;
            // 创建两个新数组，用于存放 大于/小于目标值的值
            let left = [];
            let right = [];
            let pivot = arr[0];  // 要比较的目标值， 可以是数组的任意一项
            for(let i=1; i<arr.length; i++) {
                // 对数组进行分类放置
                if(arr[i] >= pivot) {
                    right.push(arr[i])
                }else {
                    left.push(arr[i])
                }
            }
            // 对分类数组进行递归，返回最终结果
            return [...quickSort(left), pivot, ...quickSort(right)]
        };

二分查找

非递归方法

 function binarySearch(arr, target) {
            let low = 0;   // 最小索引
            let high = arr.length - 1;   // 最大索引
            while (low <= high) {  // 当最小索引小于最大索引时，循环执行直到有返回值
                let mid = (low + high) / 2;
                // 如果中间项等于 目标， 则返回索引值
                if(arr[mid] === target) {
                    return mid
                }
                // 如果中间项大于目标值， 则将最小索引改为 中间项的下一位
                if(arr[mid] > target) {
                    high = mid -1
                }
                // 如果中间项小于目标值，则将最大索引改为中间项的前一位
                if(arr[mid] < target) {
                    low = mid + 1
                }
            }
            return -1;
        }

递归方法

   function binarySearch(arr, target, lowIndex, highIndex) {
            let low = lowIndex || 0;  // 最小索引
            let high = highIndex || arr.length - 1;  // 最大索引
            let mid = (low + high) / 2;  // 中间索引
            if(arr[mid] === target) {  // 如果中间项等于 目标， 则返回索引值
                return mid
            }
            if(arr[mid] > target) {  // 如果中间项大于目标值， 则继续在前面一部分查找
                return binarySearch(arr, target, 0, mid-1)
            }
            if(arr[mid] < target) {  // 如果中间项小于目标值，则继续在后面的一部分查找
                return binarySearch(arr, target, mid+1, high)
            }
            // 如果都没有查找到，即不存在目标值，则返回 -1
            return -1
        }

The text was updated successfully, but these errors were encountered:

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

常用算法 #8

常用算法 #8

常用算法 #8

常用算法 #8

Comments

Uh oh!

1. 常见排序算法

二分查找