美文网首页
JavaScript实现排序算法【施工中】

JavaScript实现排序算法【施工中】

作者: Kagashino | 来源:发表于2019-03-01 01:29 被阅读0次

快速排序

非常有名的排序,顾名思义,快速排序突出一个快,方法:
1.选取数组中的一个元素作为【基准点】
2.比基准点大的,换到基准点右边,比它小的放到左边
3.再对基准点两边的部分重复1、2,直到所有元素有序为止

/**
 * 快速排序(递归法)
 * Average Time Complexity: O(nlog2n)
 * Stable: false
 * @param origin
 * @returns {Array}
 */
function quickSortRecursive (origin) {
    function swap (arr,i,j) {
      let t = arr[i]
      arr[i] = arr[j]
      arr[j] = t
    }
    let arr = [...origin]
    partition(arr,0,arr.length-1)
    function partition ( arr, start, end) {
        if (start >= end) {
            return
        }
        let mid = arr[end];
        let left = start, right = end - 1
        while (left < right) {
            while (arr[left] < mid && left < right)
                left++
            while (arr[right] >= mid && left < right)
                right--
            swap(arr, left, right)
        }
        if (arr[left] >= arr[end]){
            swap(arr, left, end)
        } else {
            left++
        }
        if (left) {
            partition(arr, start, left - 1)
        }
        partition(arr, left + 1, end)
    }
    return arr
}

缺点:
1.分治法需要开辟大量的空间存放分割数组,递归法限制于函数调用栈的最大空间
2.当数组基本有序或者数组为倒序时,效率非常低

冒泡排序

这个大概是最好理解的排序方法了,从左往右起比对,如果后一个元素小于前一个,则交换两者位置,每一趟都会把最大的元素排到最后

/**
 * Average Time Complexity: O(n^2)
 * Stable: true
 * @param origin
 * @returns { Array }
 */
function bubbleSort ( origin ) {
    let arr = [...origin]
    for ( let i = 0, len = arr.length; i < len; i++) {
        for (let j = 0; j < arr.length-i-1; j++) {
            if ( arr[j] > arr[j+1] ) {
                [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
            }
        }
    }
    return arr
}

选择排序

从左往右起,每趟从未排序的区间选择最大/最小值换到左边,排到上一趟排好的元素后面

/**
 * Average Time Complexity:
 * Stable: false
 * @param origin
 * @returns { Array }
 */
function selectSort ( origin ) {
    let arr = [...origin];
    let len = arr.length;
    for (let i = 0; i < len; i++ ) {
        let minIndex = i;
        for ( let j = i+1; j < len; j++) {
            if ( arr[j] < arr[minIndex] ) {
                minIndex = j;
            }
        }
        [ arr[i], arr[minIndex] ] = [ arr[minIndex], arr[i] ]
    }
    return arr
}

插入排序

我们平常打扑克整牌的时候非常类似于插入排序
从左往右起,每次选取一个元素插入左边有序区间,如果该元素比前一个大且比后一个小,则插入这两者之间

/**
 * 直接插入排序
 * Stable: true
 * @param origin
 * @returns { Array }
 */
function insertSort ( origin ) {
    let arr = [...origin]
    let len = arr.length;
    for ( let i = 1; i < len; i++ ) {
        let temp = arr[i];
        let j = i - 1;
        while ( j >= 0 && arr[j] > temp ) {
            arr[j+1] = arr[j];
            j--;
        }
        if ( j !== i - 1 ) {
            arr[j+1] = temp;
        }
    }
    return arr;
}

希尔排序

分治型的插入排序
1.定义增量(以折半增量为例),首先定义数组长度一半(向下取整)为增量 gap
2.从0开始,每隔一个gap取数组下标,形成新的分数组,以一个长度10的数组为例,gap=5,将数组下标(不是元素本身)为 [0,5] [1,6] [2,7] [3,8] [4,9] 的元素组成5个分数组
3.对这些分数组进行插入排序
4.开始下一趟:将增量减半(向下取整),gap = 2,则分成下标[0,2,4,6,8],[1,3,5,7,9]的分数组,重复3,4直到gap为1为止
5.当gap为1时,直接进行最后的插入排序

/**
 * 希尔排序
 * @param origin
 * Stable: false
 */
function shellSort ( origin ) {
    let arr = [...origin]
    let len = arr.length
    for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < len; i++) {
            for (let j = i - gap; j >= 0 && arr[j] > arr[gap + j]; j -= gap) {
                let temp = arr[j];
                arr[j] = arr[gap + j];
                arr[gap + j] = temp;
            }
        }
    }

}

堆排序

利用“堆”这个数据结构,构建最大/最小堆,再从堆中取走元素的排序法

/**
 * Heapsort 最大堆排序
 * @param origin
 * @returns { Array }
 */
function maxHeapSort ( origin ) {
    let arr = [...origin]
    //交换数组元素
    function swap(arr, i, j) {
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //将元素与父节点比对并交换位置,满足最大堆性质为止
    function maxHeapify(start, end) {
        let dad = start;
        let son = dad * 2 + 1;
        if (son >= end){
            return;
        }
        if (son + 1 < end && arr[son] < arr[son + 1]){
            son++;
        }
        if (arr[dad] <= arr[son]) {
            swap(arr, dad, son);
            maxHeapify(son, end);
        }
    }

    let len = arr.length;
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--)
        maxHeapify(i, len);
    for (let i = len - 1; i > 0; i--) {
        swap(arr,0, i);
        maxHeapify(0, i);
    }

    return arr;
}

基数排序

本例使用LSD,即从低位到高位排序
从个位开始,将数字按当前位数装入一个{0,1,2,3,4,5,6,7,8,9}的桶中,然后按桶的下标倒出,再进行下一位数的装桶操作
如果存在如 24 110这样位数不一样的数,不足的数字需要在位数前补0

/**
 * Radix Sort基数排序
 * 从个位开始,将数字按当前位数排入一个{0,1,2,3,4,5,6,7,8,9}的桶中;
 * @param origin 原数组
 * @returns { Array } 输出新数组
 */
function radixSort ( origin ) {
    let arr = [...origin]
    let digit = ( Math.max(...arr) + '').length
    let bucket = {};
    // 初始化桶
    for ( let i = 0; i < 10; i++) {
        bucket[i] = []
    }

    // 从各位到高位排序
    for ( let bit = 1; bit < 10**digit; bit*=10) {
        /**
         * 将元素按照位数作为下标装入桶中
         * example 456:
         * 第一轮 bit = 1 -> 456个位数6,将456装进bucket[6]
         * 第二轮 bit = 10 -> 456十位数5,将456装进bucket[5]
         */
        for (let i = 0, len = arr.length; i < len; i++) {
            if ( arr[i]/bit < 1 ) {
                bucket[0].push(arr[i])
            } else {
                //获取当前位数的数字,如当前位数100,则取这个数的百位数
                let bitNum = Math.floor(arr[i]%(bit*10)/bit);
                bucket[bitNum].push(arr[i])
            }
        }
        arr = []; //清空数组

        //将元素从桶内倒出来
        for( let i in Object.keys(bucket) ) {
            while( bucket[i].length ) {
                arr.push( bucket[i].shift() )
            }
        }
    }
    return arr;
}

相关文章

  • JavaScript实现排序算法【施工中】

    快速排序 非常有名的排序,顾名思义,快速排序突出一个快,方法:1.选取数组中的一个元素作为【基准点】2.比基准点大...

  • 几种排序算法浅析--JavaScript

    算法好难啊!写点简单的。然后用JavaScript实现。 排序算法(Sorting Algorithm) 概念 一...

  • JS实现排序算法

    原文:常见排序算法之JavaScript实现 - 知乎 目录 冒泡排序 选择排序 插入排序 合并排序 快速排序 1...

  • JavaScript实现快速排序算法的最佳实践,没有之一

    1.快速排序的基本思想 长话短说,排序算法中快速排序的性能还是不错的,今天我就讲讲javascript中实现快速排...

  • JavaScript实现经典排序算法

    使用JavaScript实现的经典排序算法 util 冒泡 简单选择 直接插入 快速排序 堆排序 归并排序

  • 斌斌学院JS-task5

    任务目的 学习与实践JavaScript的基本语法、语言特性 练习使用JavaScript实现简单的排序算法 任务...

  • JavaScript 实现多种排序算法

    本章将介绍 JavaScript 如何实现排序,几种排序算法介绍如下图: 准备工具函数 util.js 备用: 借...

  • 排序算法总结

    JavaScript实现十大排序算法,代码+动图+在实现代码的时候遇到的坑 冒泡算法 (1) 实现思路 不断的重复...

  • JavaScript实现排序算法

    排序算法主要用于元素的数组排序,常见的排序算法有冒泡排序,选择排序,插入排序,希尔排序,快速排序,归并排序等,这些...

  • javascript实现排序算法

    在上一篇博客中,介绍了插入排序的第一种,直接插入排序。再加上前面介绍过的快速排序,冒泡排序和简单选择排序。这四种排...

网友评论

      本文标题:JavaScript实现排序算法【施工中】

      本文链接:https://www.haomeiwen.com/subject/rkfruqtx.html