文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

JavaScript怎么实现基础排序算法

2023-07-02 14:17

关注

本文小编为大家详细介绍“JavaScript怎么实现基础排序算法”,内容详细,步骤清晰,细节处理妥当,希望这篇“JavaScript怎么实现基础排序算法”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。

正文

1、冒泡排序

算法思想:比较相邻两个元素的大小,如果第一个比第二个大,就交换它们。从头遍历到尾部,当一轮遍历完后,数组最后一个元素是最大的。除去最后一个元素,对剩下的元素重复执行上面的流程,每次找出剩余元素中最大的,遍历完后,数组是升序的

算法分析:总共需要进行length * (length - 1) / 2 次比较,所以时间复杂度为O(n^2),因为只需要有一个存放常量的空间,元素本身在原数组上进行交换,所以空间复杂度为O(1)

function bubbleSort(array) {            if (!Array.isArray(array)) {                throw new Error('参数必须为数组');                return;            }            var n = 0, m = 0 // n表示趟数,m表示比较次数            for (let i = array.length - 1; i > 0; i--) { // 外层for表示遍历的趟数                for (let j = 0; j < i; j++) { // 内层for表示每趟需要比较的 j 和 j+1 对应的数                    if (arr[j] > arr[j + 1]) {                        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]                    }                    m++                }                n++            }            console.log("遍历趟数" + n, "比较次数" + m);//遍历趟数8 比较次数36            return array        }        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]        console.log(bubbleSort(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]

我们在每一轮循环中,可以记住最后一次交换的元素,这之后的元素就肯定是已经排完序的,这样可以减少总的循环次数

function bubbleSort2(array) {            if (!Array.isArray(array)) {                throw new Error('参数必须为数组');                return;            }            var n = 0, m = 0 // n表示趟数,m表示比较次数            for (var i = array.length - 1; i > 0;) { // 用来表示遍历 n-1 趟                var cursor = 0;  // 用来记录本轮最后一次交换的元素位置                for (var j = 0; j < i; j++) {                    if (array[j] > array[j + 1]) {                        cursor = j;                        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]                    }                    m++                }                n++                i = cursor;                            }            console.log("遍历趟数" + n, "比较次数" + m);//遍历趟数6 比较次数29            return array        }        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]        console.log(bubbleSort2(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]

2、选择排序

实现思路

(1)从头遍历到尾部,找出所有项中最大的一个元素

(2)将这个元素和第一个元素交换

(3)对剩下的元素重复进行上面的操作,每次找出剩余中最大的最后的数组是降序排列的

(4) 算法分析

总共需要进行length * (length - 1) / 2 次比较,所以时间复杂度为O(n^2),因为只需要有两个存放常     量的空间,元素本身在原数组上进行交换,所以空间复杂度为O(1)

function selectSort(array) {            if (!Array.isArray(array)) {                throw new Error('参数必须为数组');                return;            }            for (let i = 0; i < array.length; i++) {                var maxIndex = i, maxValue = array[i] // 设置i为最大元素下标                // 找出剩下元素中的最大值,第一次循环找出最大值                for (let j = i + 1; j < array.length; j++) {                    if (array[j] > maxValue) {                        maxIndex = j                        maxValue = array[j]                    }                }                // 如果剩下的元素中最大值下标大于i则发生交换                if (maxIndex > i) {                    [array[i], array[maxIndex]] = [array[maxIndex], array[i]]                }            }            return array        }        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]        console.log(selectSort(arr)); //[45, 24, 9, 8, 7, 6, 3, 1, 0]

3、插入排序

实现思路

(1)将数组前面部分看做有序数组

(2)每次将后面部分的第一个与已排序数组作比较,插入到合适的位置

(3)有序数组初始状态有1个数字

(4)算法分析

(5)时间复杂度为O(n^2)

function insertSort(array) {            if (!Array.isArray(array)) {                throw new Error('参数必须为数组');                return;            }            for (var i = 1; i < array.length; i++) {                var temp = array[i] //当前值                for (var j = i; j > 0 && temp < array[j - 1]; j--) {                    // 当前值和之前的每个值进行比较,发现有比当前值小的值就进行重新赋值                    array[j] = array[j - 1];                }                array[j] = temp;            }            return array;        }        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]        console.log(insertSort(arr)); //[45, 24, 9, 8, 7, 6, 3, 1, 0]

4、快速排序

算法思想:将数组的第一个数字作为基准,最后使得基准数字位于数组中间某个位置,它的左边的数字都比它小,它的右边的数字都比它大。

算法实现:设置两个分别指向数组头部和尾部的指针i和j,首先向左移动j,使得array[j] 小于基准。然后向右移动i,使得array[i] 大于基准,交换这两个元素。当i 和j 的值相等时,交换基准与位置i上的元素,然后对i左边以及右边的元素分别进行快速排序。

function quickSort(array) {            const sort = function (arr, left = 0, right = arr.length - 1) {                if (left >= right) {// 递归退出条件                    return                }                let i = left, j = right // 定义两个指针                let pivot = arr[i] // 定义基准数据                while (i < j) { // 把所有比基准数                    while (j > i && arr[j] >= pivot) { //找到一个比基准值小的数位置为j                        j--                    }                    arr[i] = arr[j] // 将j的值给了i位置的元素,此时j位置还是原来的数                    while (i < j && arr[i] < pivot) {                        i++                    }                    arr[j] = arr[i] // 将i位置的值给了j位置的元素,此时i的位置还是原来的数                }                // 本次交换完毕,此时ij两个指针重合,把基准值赋值给i即可                arr[i] = pivot                sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作                sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作            }            const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组            sort(newArr)            return newArr        }        var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]        console.log(quickSort(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]

读到这里,这篇“JavaScript怎么实现基础排序算法”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯