关于javascript:常见排序算法原理及JS代码实现

创立工夫：2020-08-07

本文只是将作者学习的过程以及算法了解进行简略的分享，提供多一个角度的了解阐明，或者让你的困惑能得以解决（代码或阐明若有问题，欢送留言、分割更正！免得造成更多困惑）

如果要更深入研究这些算法的同学，社区中同类型更优良，单个算法更深刻分析的文章也是亘古未有，这里或者作为一个常见排序算法入门学习理解更精确

排序名称	最快工夫	最慢工夫	空间复杂度
冒泡排序	O(n)	O(n^2)	O(1)
抉择排序	O(n^2)	O(n^2)	O(1)
插入排序	O(n)	O(n^2)	O(1)
希尔排序	O(n*log2n)	O(n^2)	O(1)
归并排序	O(nlogn)	O(n)	O(n)
堆排序	O(nlogn)	O(nlogn)	O(1)
疾速排序	O(nlogn)	O(n^2)	O(1),O(n)

以上工夫和空间复杂度会依据算法的优化有所不同

生成测试所用，蕴含随机十万条数据的数组

const arr = []
for (let i = 0; i < 100000; i++) {arr.push(Math.random())
}

以下标注的工夫均为对该随机数组的数据排序的工夫，这里的工夫只是作为一个参考，因为并没有管制到只有惟一变量（每个排序算法用到的数组长度雷同，但数组值不同），
所以这里的工夫只反馈惯例状况

运行工夫的计算应用 console.time()

实现也是基于快排做了很多的优化算法，以保障各种状况都能稳固较快的实现排序查看 C ++ 实现源码

工夫：≈ 75ms

function sortCompare(array) {array.sort((a, b) => (a-b))
}

原理：顺次比拟两个相邻的元素，将较大的放到左边（升序排列）

一轮循环只找到一个最值，而后通过屡次这样的循环（所以有两层嵌套循环），取得一个排序后果

以下是通过简略优化的算法实现：

工夫：≈ 21899ms

function bubbling(array) {
    const len = array.length
    let sorted = true
    /* 每找到一个最值，须要一次循环 */
    for (let i = 0; i < len; i++) {
        /* 必须每轮循环前，假如是排好序后的数组，避免只须要前几次循环就排好的状况 */
        sorted = true
        /* 这里的循环是找出以后轮的最值 */
        /* len-1-i 保障 j+1 能取到，同时放到最初的数，不必参加下一轮的循环，因为它曾经是上一轮找出的最值 */
        for (let j = 0; j < len - 1 - i; j++) {if (array[j] > array[j + 1]) {let temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
                sorted = false
            }
        }
        /* 如果是曾经排好序了就间接退出循环，此时最优工夫复杂度 O(n) */
        if (sorted) break
    }

    return array
}

原理：从残余未排序序列中找到最小（大）元素，搁置在已排序序列的开端地位，以此循环，直到所有元素均排序结束

工夫：≈ 6353ms

function selectionSort(array) {
    let len = array.length
    for (let i = 0; i < len; i++) {
        /* 默认开始的第一个值的地位搁置下一个最小值 */
        let minIndex = i
        /* 查找残余数值中的最小值，从 i + 1 开始的目标是防止与本身进行一次比拟 */
        for (let j = i + 1; j < len; j++) {if(array[minIndex] > array[j]) {minIndex = j}
        }
        /* 将最小值和以后地位 (i) 的值进行替换 */
        let temp = array[minIndex]
        array[minIndex] = array[i]
        array[i] = temp
    }
    return array
}

原理：将未排序队列中的数值，一一与已排序队列中的数进行比拟，当呈现大于或小于已排序队列中的某个数时，进行插入操作

留神与抉择排序的区别，抉择排序是在未排序的数中找最值，而后替换地位，插入排序则是在已排序的的数中找对应的第一个绝对最值

工夫：≈ 2416ms

function insertionSort(array) {
    let len = array.length
    for (let i = 1; i < len; i++) {
        /* 记录以后未排序的数，该数将会和有序数列中的数进行比拟 */
        let current = array[i]
        /* 有序数列的最初一个数（如果是从小到大排列，也就是最大的数）*/
        let endIndex = i - 1 
        while (endIndex >=0 && array[endIndex] > current) {
            /* 将有序数列中的数，逐个与以后未排序数进行比拟直到，找出比以后未排序数小的数即进行 */
            array[endIndex + 1] = array[endIndex]
            endIndex--
        }
        /* 将最初一个往后挪动空进去的地位赋值为，以后未排序数 */
        array[endIndex+1] = current
    }
    return array
}

原理：

插入排序的一种优化

设置一个增量，将数组中的数按此增量进行分组（比方增量为 4，那下标为 0，4，8… 的数为一组）
对分组的数进行插入排序
放大增量
反复步骤 1、2、3，直到增量为 1
当增量为 1 时，对整个数组进行一次插入排序，输入最初后果

工夫复杂度与增量选取无关, 以下算法工夫复杂度为 O(n^(3/2))

非稳固排序（2 个相等的数，在排序实现后，原来在后面的数还是在后面，即为稳固排序）

工夫：≈ 35ms

function shellSort(array) {
    let len = array.length, gap = 1;
    /* 此处获取一个最大增量，增量的获取办法不固定，这里采纳比拟常见的形式，肯定要保障最初能取到 1 */
    while(gap < len/3) {gap = gap*3+1;}

    /* 每更新一次增量就进行一次插入排序 */
    while(gap>0) {
        /* 以下逻辑与插入排序统一，当增量变为 1 时即完全一致 */
        for (let i = gap; i < len; i++) {
            /* 这里要循环到数组最初是因为要保障以后分组中的每一个数都通过排序，所以以后分组靠前的数据会被与前面的数据进行屡次排序 */
            let current = array[i]
            let endIndex = i - gap
            while(endIndex>=0 && array[endIndex] > current) {array[endIndex + gap] = array[endIndex]
                endIndex -= gap
            }
            array[endIndex+gap] = current
        }
        gap = Math.floor(gap/3)
    }
    return array
}

分治法：把一个简单的问题分成两个或更多的雷同或类似的子问题，再把子问题分成更小的子问题……直到最初子问题能够简略的间接求解，原问题的解即子问题的解的合并

原理：将以后数组，递归分组，比拟大小后再一一合并分组，是采纳分治法的一个利用

获取一个两头地位的值，而后以该地位为中心点分组
递归进行分组
比拟以后两个分组，将其合并为一个数组

工夫：≈ 1170ms

function mergeSort(array) {
    const len = array.length
    if(len<2) return array
    const middle = Math.floor(len/2)
    
    /* 取两头值进行分组 */
    const left = array.slice(0, middle)
    const right = array.slice(middle)

    /* 递归分组 */
    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {const result = []
    /* 两个分组都有值时，一一进行比拟 */
    while (left.length && right.length) {if(left[0] <= right[0]) {result.push(left.shift())
        } else {result.push(right.shift())
        }
    }

    /* 只有一个分组时，表明其全副为最大值，间接全副放入后果数组即可 */
    if(left.length){result.push(...left)
    }

    if(right.length){result.push(...right)
    }
    return result
}

分为大顶堆（子节点都小于父节点），小顶堆（子节点都大于父节点）

原理：

依据给定的数据创立堆
将堆顶和堆尾调换，将堆长度减 1
递归步骤 1、2

工夫：≈ 46ms

function heapSort(array) {
    let length = array.length
    /* 第一个非叶子节点（叶子节点：没有子节点的节点）：n/2 -1 */
    /* 为什么从这个点开始，也是因为这是最初一个领有子节点的父节点，其可能会产生父子节点替换 */
    const node =  Math.floor(length/2) - 1

    /* 第一步先将数组构建为堆 这里是大顶堆 */
    for (let i = node; i >= 0 ; i--) {maxHeap(array, i, length)
    }

    /* 第二步 将堆顶元素与堆尾元素替换 再将前 (n-1) 个数反复构建堆 */
    for (let j = length - 1; j > 0; j--) {swap(array, 0, j)
        length--
        /* 这里相当于把第一个叶子节点扭转了，所以上面从 0 开始, 以后堆的堆尾前一个数为完结 从新构建堆 */
        maxHeap(array, 0, length)
    }

    return array
}

function maxHeap(array, i, length) {
    /* 左子节点 */
    let left = i*2 + 1
    /* 右子节点 */
    let right = i*2 + 2
    /* 父节点 */
    let parent = i

    /* 找出子节点中比父节点大的数进行替换 */
    if(left < length && array[left] > array[parent]) {parent = left}

    /* 这里两个条件都触发也没有关系，只有保障，一个比父节点大的子节点被移上去即可 */
    if(right < length && array[right] > array[parent]) {parent = right}

    if(parent !== i) {swap(array,i, parent)
        /* 示意有数据挪动，所以要重排一下数据挪动后, 所影响到的父子节点, 也就是此时的 parent 节点和其子节点 */
        maxHeap(array, parent, length)
    } 
}

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

原理：

在数组中找一个基准
数组中的数与该基准相比拟，比它小的放在其后面，比它大的放在其前面（分区操作）
再递归的去操作基准前、后的分区

形式一：

须要 O(n) 的额定存储空间，和归并排序一样

然而代码更清晰的体现快排的思维

工夫：≈ 77ms

function quickSort (array) {if (array.length < 2) return array;
    const pivot = array[0];
    let left = []
    let right = []
    for (let i = 1, length = array.length; i < length; i++) {if(array[i] < pivot) {left.push(array[i])
        } else {right.push(array[i])
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

形式二：

原地排序

工夫：≈ 34ms

function quickSort(array, left, right) {if(left<right) {pivotIndex = fill(array, left, right)
        quickSort(array, left, pivotIndex-1)
        quickSort(array, pivotIndex+1, right)
    }
    return array
}

function fill(array, left, right) {const pivotValue = array[left]
    while(left < right){
        /* 左边大于基准的数据不须要挪动地位 */
        /* 这里或上面的循环，肯定要确保有一处把相等的状况蕴含在内 */
        while(array[right] >= pivotValue && left < right){right--}
        /* 将左边第一个扫描到的小于基准的数据挪动到右边的空位 */
        array[left] = array[right]

        /* 右边小于基准的数据不须要挪动地位 */
        while(array[left] < pivotValue && left < right){left++}
        array[right] = array[left]
    }

    /* 这里 right 和 left 相等了 */
    array[right] = pivotValue

    return right
}

还有一些更好的优化，比方基准数的选取，防止最坏工夫复杂度状况的产生，可自行摸索

总结：

在理论我的项目中可能间接用到这些算法就能解决掉业务需要的状况并不多，甚至间接用 Array.sort() 也能解决。

然而业务需要变幻无穷，多种多样，总有须要你从底层去更改、优化、变异算法的状况，此时就须要用你了解的这些根本算法的原理来疾速解决业务问题。

最初祝大家数据结构某几个章节温习顺利！

欢送交换 Github

数组 sort() 办法

冒泡排序

抉择排序

插入排序

希尔排序

归并排序

堆排序

疾速排序