首页 > 编程语言 > 笔记 | Sort 的实现逻辑与排序算法

笔记 | Sort 的实现逻辑与排序算法

时间：2023-08-07 09:24:02浏览次数：41  
标签：Sort arr const 算法 length let return 排序

一、Sort

Sort() 的功能是对数组元素就地进行排序，会改变数组本身(返回对象同数组的引用)。默认排序顺序是，先将元素转换为字符串后进行排序。

有一个可选参数 compareFunction 定义排序顺序的函数。返回值应该是一个数字，其正负性表示两个元素的相对顺序。

array.sort([compareFunction])。
sort(compareFn?: (a: T, b: T) => number): this;

compareFunction 默认情况下

const stringArr = ['abd', 'abc', 'abe']
stringArr.sort()
console.log(stringArr) // [ 'abc', 'abd', 'abe' ]

const numberArr = [1, 20, 33, 4, 1999]
numberArr.sort()
console.log(numberArr) // [ 1, 1999, 20, 33, 4 ]

指明 compareFunction 的情况下

规则是 compareFunction 函数得到的结果：

  • 等于 0。相对位置不变；
  • 小于 0。a 在 b 的前面；
  • 大于 0。b 在 a 的前面；
const numberArr = [1, 20, 33, 4, 1999]
numberArr.sort((a, b) => 0)
console.log(numberArr) // [ 1, 20, 33, 4, 1999 ]
numberArr.sort((a, b) => b - a)
console.log(numberArr) // [ 1999, 33, 20, 4, 1 ]
numberArr.sort((a, b) => a - b)
console.log(numberArr) // [ 1, 4, 20, 33, 1999 ]

sort 方法在 V8 中的底层实现

  • 分析：

    1. 当 n <= 10, 采用插入排序
    2. 当 n > 10, 采用三路快速排序
    3. 当 10 < n <= 1000, 采用中位数作为哨兵元素
    4. 当 n > 1000, 每隔 200~215 个元素挑出一个元素放到一个新数组中然后对它排序，找到中间位置的数，作为中位数

  • 为什么元素少的时候采用插入排序？

    因为当 n 足够小的时候，快排 nlogn 的优势会越来越小。插入排序经过优化以后，对于小数据集的排序会有非常优越的性能。

  • 为什么要花大力气选择哨兵元素？

    快排的性能瓶颈在于递归深度，最坏情况是每次的哨兵都是极值，在这种情况下，就会有一边是空的。避免这种情况，就要让哨兵尽可能的处于数组的中间位置，让极值情况尽可能的少出现。

二、常用的排序算法

1. 冒泡排序

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)
  • 稳定排序

const array = [1, 2, 5, 67, 4, 1, 34, 77, 200, 6, 600, 180, 800]

function bubbleSort(arr) {
    if (arr.length < 2) return arr
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[i]) {
                const temp = arr[j]
                arr[j] = arr[i]
                arr[i] = temp
            }
        }
    }
    return arr
}
console.log(bubbleSort(array)) 
// [ 1, 1, 2, 4, 5, 6, 34, 67, 77, 180, 200, 600, 800 ]

2. 选择排序

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)
  • 不稳定排序
  • 将最小的元素放在序列的起始位置，然后再剩余序列中找到最小的，放到已排序的后面
const array = [1, 2, 5, 67, 4, 1, 34, 77, 200, 6, 600, 180, 800]

function selectSort(arr) {
    if (arr.length < 2) return arr
    const len = arr.length
    let temp
    let minIndex
    for (let i = 0; i < len; i++) {
        minIndex = i
        for (let 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
}
console.log(selectSort(array))
// [ 1, 1, 2, 4, 5, 6, 34, 67, 77, 180, 200, 600, 800 ]

3. 快速排序

  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(nlogn)
  • 不稳定排序
  • 快排就是在一趟排序中，将待排序列分隔成两部分，第一部分均比第二部分数值小
const array = [1, 2, 5, 67, 4, 1, 34, 77, 200, 6, 600, 180, 800]

function quickSort(arr) {
    const quick = function (a) {
        if (a.length < 2) return a
        const len = a.length
        const index = Math.floor(len >> 1) // 找到序列中间元素->长度除以二向下取整
        const pivot = a.splice(index, 1)[0] // 在原序列中删除中间元素，当作判断基准
        const left = []
        const right = []
        for (let i = 0; i < len - 1; i++) { // 遍历去除中间元素的数组，所以len要减一
            // 然后序列各项与基准比较，大的放在right数组中，反之放在left数组中
            if (a[i] > pivot) {
                right.push(a[i])
            } else if (a[i] <= pivot) {
                left.push(a[i])
            }
        }
        // 然后递归调用 quick 方法，
        // 对left和right数组进行排序，
        // 将left排序的结果加上中间元素与right排序的结果进行合并，然后返回
        return quick(left).concat([pivot], quick(right))
    }
    return quick(arr)
}
console.info(quickSort(array)) 
// [ 1, 1, 2, 4, 5, 6, 34, 67, 77, 180, 200, 600, 800 ]

4. 插入排序

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)
  • 稳定排序
  • 对未排序数据，在已排序序列中进行单方向扫描，找到对应位置进行插入。
const array = [1, 2, 5, 67, 4, 1, 34, 77, 200, 6, 600, 180, 800]

function insertSort(arr) {
    if (arr.length < 2) return arr
    const len = arr.length
    let current
    let prev
    for (let i = 0; i < len; i++) {
        current = arr[i]
        prev = i - 1
        while (prev >= 0 && arr[prev] > current) {
            arr[prev + 1] = arr[prev]
            prev--
        }
        arr[prev + 1] = current
    }
    return arr
}
console.info(insertSort(array)) 
// [ 1, 1, 2, 4, 5, 6, 34, 67, 77, 180, 200, 600, 800 ]

5. 堆排序 (大根堆)

  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(1)
  • 不稳定排序
  • 排序过程：
    1. 排序前先建堆
    2. 这个堆其实就是一个完全二叉树。如果双亲结点的序号是 i，那么，左孩子节点的序号就是 2 * i + 1，右孩子节点的序号就是 2 * i + 2。
    • 在将一个数组调整成一个堆的时候，关键之一的是确定最后一个非叶子节点的序号
    • 这个序号为 n / 2-1，n 为序列的长度。
    • 可以分两种情形考虑：
      1. 堆的最后一个非叶子节点若只有左孩子
      2. 堆的最后一个非叶子节点有左右两个孩子
const array = [1, 2, 5, 67, 4, 1, 34, 77, 200, 6, 600, 180, 800]

function heap_sort(arr) {
    if (arr.length < 2) return arr
    const len = arr.length

    function swap(i, j) { // 对应节点做交换
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }

    function max_heapify(start, end) {
        let parents = start
        let child = parents * 2 + 1 // 获取左孩子节点的序号
        if (child >= end) return

        // 保证右孩子节点的值大于左孩子节点
        if (child + 1 < end && arr[child] < arr[child + 1]) {
            child++
        }
        // 如果右孩子节点大于双亲节点，进行交换，然后继续建堆
        if (arr[parents] <= arr[child]) {
            swap(parents, child)
            max_heapify(child, end)
        }
    }

    // 第一个循环是处理双亲节点的顺序
    for (let i = Math.floor(len >> 1) - 1; i >= 0; i--) {
        max_heapify(i, len)
    }

    // 第二个循环是根据双亲节点和孩子节点对比的大小，进行堆的调整
    for (let i = len - 1; i > 0; i--) {
        swap(0, i)
        max_heapify(0, i)
    }

    return arr
}
console.log(heap_sort(array)) 
// [ 1, 1, 2, 4, 5, 6, 34, 67, 77, 180, 200, 600, 800 ]

6. 归并排序

  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(n)
  • 稳定排序
  • 将已经有序的子序列合并，得到完全有序的序列。若将两个有序序列合并，叫做二路归并
const array = [1, 2, 5, 67, 4, 1, 34, 77, 200, 6, 600, 180, 800]

function mergeSort(arr) {
    const merge = (right, left) => {
        const result = []
        let il = 0
        let ir = 0
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++])
            } else {
                result.push(right[ir++])
            }
        }
        while (il < left.length) {
            result.push(left[il++])
        }
        while (ir < right.length) {
            result.push(right[ir++])
        }
        return result
    }
    const mergeSort = a => {
        if (a.length < 2) return a
        const mid = Math.floor(a.length >> 1)
        const left = a.slice(0, mid)
        const right = a.slice(mid, a.length)
        return merge(mergeSort(right), mergeSort(left))
    }
    return mergeSort(arr)
}
console.log(mergeSort(array)) 
// [ 1, 1, 2, 4, 5, 6, 34, 67, 77, 180, 200, 600, 800 ]



❧


标签：Sort,arr,const,算法,length,let,return,排序
From： https://www.cnblogs.com/inslog/p/17610597.html

相关文章

  • 【算法】组合数学初步
    参考资料OI-Wiki组合数学一、概念\(\dbinom{n}{m}\)表示从\(n\)个小球内拿\(m\)个的方案数，小球一样但顺序不一样算同一种方案，可用\(\dbinom{n}{m}=\frac{n!}{m!(n-m)!}\)计算，称为组合。\(A_n^m\)表示从\(n\)个小球内拿\(m\)个的方案数，小球一样但顺序不一样算不......
  • 【算法】网络流初步
    参考资料用最通俗的语言让你学会网络流OI-Wiki网络流算法学习笔记(28):网络流一、概念网络流指的是在一个每条边都有容量的有向图中找到一种方案，使得源点到汇点的流量最大。网络流问题常见的有三类，分别是最大流，费用流和最小割。最大流顾名思义，表示的是在有向图中找到一种......
  • 扩展欧几里得算法与乘法逆元
    Part1：前置知识欧几里得算法\[\foralla,b\in\mathbb{N},\gcd(a,b)=\gcd(b,a\bmodb)\]\(\mathrm{Bézout}\)定理对于任意整数\(a,b\)，存在一对整数\(x,y\)，满足\(ax+by=\gcd(a,b)\)证明：在欧几里得算法的最后一步，即\(b=0\)时，显然有一对整数\(x=1,y=0\)，使得\(a......
  • Dijkstra最短路径算法及其优化
    Dijkstra最短路径算法及其优化图示过程可以参考图文详解Dijkstra最短路径算法(freecodecamp.org)直接给出Java版本的普通实现方式：/***最普通的实现形式，时间复杂度是O(n2)，空间复杂度是O(n)*@paramweight*@paramstart*@return*/publicstaticint[]getDij......
  • 【学习笔记】类欧几里得算法
    概述主要是求以下三个式子：\[f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor\]\[g(a,b,c,n)=\sum_{i=0}^ni\left\lfloor\dfrac{ai+b}{c}\right\rfloor\]\[h(a,b,c,n)=\sum_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor^2\]求\(f......
  • 算法 华为
     1、链表，两两交换位置，不允许修改值，只能改节点例如1234，=>21432、拔河比赛选拔队员，输入身高，体重。按这两个优先级排序例如输入1827019060输出1906019060 3、最小花费问题（这个分值200，比前面的难）输入产品数量n，需要输出k种方案n个产品对应的价格数组输出：前k小......
  • 数据结构与算法（四）：双向链表
    基本概念双向链表概念和单向链表是一致的，区别在于双向链表在单向链表的基础上，指针区域多了一个指向上一个节点的指针。单向链表内容可以参考我的上一篇文章：http://t.csdn.cn/Iu56H。基本的数据结构如图所示：链表结构双向链表结构包含了节点的数据内容和两个指针：指向前一个节点......
  • m基于FFT傅里叶变换的QPSK基带信号频偏估计和补偿算法FPGA实现,包含testbench和matlab
    1.算法仿真效果本系统进行了Vivado2019.2平台的开发，并使用matlab2022a对结果进行星座图的显示：将FPGA的频偏基带QPSK信号和频偏补偿后的QPSK基带信号使用matlab显示星座图，结果如下：2.算法涉及理论知识概要QPSK（QuadraturePhaseShiftKeying）是一种常用的调制方式，它可以在相位和......
  • m基于FFT傅里叶变换的QPSK基带信号频偏估计和补偿算法FPGA实现,包含testbench和matlab
    1.算法仿真效果本系统进行了Vivado2019.2平台的开发，并使用matlab2022a对结果进行星座图的显示：   将FPGA的频偏基带QPSK信号和频偏补偿后的QPSK基带信号使用matlab显示星座图，结果如下：   2.算法涉及理论知识概要       QPSK（QuadraturePhaseShiftKeying）......
  • 基于位相光栅的四波横向剪切干涉法波前检测算法的matlab仿真
    1.算法理论概述      波前检测技术是现代光学中的重要技术之一，可以用于衡量光学系统的成像质量和研究光学系统的异常现象。随着现代光学技术的不断发展，波前检测技术也在不断地发展和完善。其中，基于位相光栅的四波横向剪切干涉法波前检测算法是一种常用的波前检测算法，本文......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99