美文网首页饥人谷技术博客程序员
用JavaScript实现常见的排序算法

用JavaScript实现常见的排序算法

作者: clancysong | 来源:发表于2018-02-10 21:56 被阅读48次

前戏

  • 复习了一些比较常见的排序算法,用JS实现,带一些实现思路。
  • 无图,无脑贴代码。。

比较排序

冒泡排序

  1. 比较相邻的元素,若第二个比第一个大,则交换位置。
  2. 对每一对相邻元素作比较,一轮交换完成后,最大的元素应该排在最后,即排序完成。
  3. 对剩余待排序元素重复步骤1~2,直到所有元素都已排序完成。
function bubbleSort(paramArr) {
    const arr = paramArr.slice()
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

选择排序

  1. 从未排序序列中选择最小的元素放在已排序序列的末尾。
  2. 重复步骤1,直到所有元素都已被放入已排序序列。
function selectionSort(paramArr) {
    const arr = paramArr.slice()
    for (let i = 0; i < arr.length; i++) {
        let minIndex = 0
        for (let j = 1; j < arr.length - i; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        arr.push(arr[minIndex])
        arr.splice(minIndex, 1)
    }
    return arr
}

插入排序

  1. 取出第一个元素,这个元素可以认为已经被排序。
  2. 取出下一个元素,从后向前依次对比,如果已排序元素大于新元素,则将该元素后移一位。
  3. 重复步骤2,直到找到已排序元素小于等于新元素的位置,将新元素插入。
  4. 重复步骤2~3,直到所有元素都插入完毕。
function insertionSort(paramArr) {
    const arr = paramArr.slice()
    for (let i = 1; i < arr.length; i++) {
        for (let j = i; j > 0; j--) {
            if (arr[j - 1] > arr[j]) {
                const temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
            } else {
                break
            }
        }
    }
    return arr
}

快速排序

  1. 在待排序元素中选择一个元素作为基准。
  2. 将所有小于基准的元素都移到基准的左边,所有大于基准的元素都移到基准的右边。操作结束后,基准就已经处在最终排序后它的位置。
  3. 对左右两个子集重复步骤1~2,直到所有的子集只剩下一个元素。

这里说一下代码细节:

  1. 将序列中最后一个数作为基准数。
  2. 用storeIndex表示移动元素放置的位置,最开始指向序列起点。
  3. 从前向后遍历,移动小于等于基准元素的元素到数组的开头,每次移动 storeIndex 自增 1。
  4. 循环结束后将storeIndex位置上的元素与基准数交换,此时一轮排序完成。
function quickSort(paramArr) {
    const swap = (arr, index1, index2) => {
        const temp = arr[index1]
        arr[index1] = arr[index2]
        arr[index2] = temp
    }

    const partition = (arr, start, end) => {
        let storeIndex = start
        const standardIndex = end
        for (let i = start; i < end; i++) {
            if (arr[i] <= arr[standardIndex]) {
                swap(arr, storeIndex, i)
                storeIndex += 1
            }
        }
        swap(arr, storeIndex, end)
        return storeIndex
    }

    const sort = (arr, start, end) => {
        if (start > end) return []
        const storeIndex = partition(arr, start, end)
        return [
            ...sort(arr, start, storeIndex - 1),
            arr[storeIndex],
            ...sort(arr, storeIndex + 1, end)
        ]
    }

    return sort(paramArr.slice(), 0, paramArr.length - 1)
}

非比较排序

计数排序

懒。。介绍就抄维基的啦。

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第i项
  3. 对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加)
  4. 反向填充目标数组:将每个元素i放在新数组的第 C[i] 项,每放一个元素就将 C[i] 减去1
function countingSort(arr) {
    const bucketArr = []
    const sortedArr = []

    for (let i = 0; i < arr.length - 1; i++) {
        if (!bucketArr[arr[i]]) {
            bucketArr[arr[i]] = 1
        } else {
            bucketArr[arr[i]] += 1
        }
    }

    for (let i = 0; i < bucketArr.length - 1; i++) {
        if (bucketArr[i]) {
            for (let j = 0; j < bucketArr[i]; j++) {
                sortedArr.push(i)
            }
        }
    }

    return sortedArr
}

桶排序

  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列,并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。

这里对每个桶中的元素使用插入排序

function bucketSort(arr, step) {
    const bucket = []
    const sortedArr = []

    for (let i = 0; i < arr.length; i++) {
        const index = Math.floor(arr[i] / step)
        if (!bucket[index]) {
            bucket[index] = []
            bucket[index].push(arr[i])
        } else {
            bucket[index].push(arr[i])
            for (let j = bucket[index].length - 1; j > 0; j--) {
                if (bucket[index][j - 1] > bucket[index][j]) {
                    const temp = bucket[index][j]
                    bucket[index][j] = bucket[index][j - 1]
                    bucket[index][j - 1] = temp
                } else {
                    break
                }
            }
        }
    }

    for (let i = 0; i < bucket.length; i++) {
        if (bucket[i]) {
            for (let j = 0; j < bucket[i].length; j++) {
                sortedArr.push(bucket[i][j])
            }
        }
    }

    return sortedArr
}

结语

还有一些比较常见的如基数排序、堆排序这里没有写(其实是已经忘干净了。。可能以后会再开一篇吧)

惯例贴链接:

相关文章

  • JS实现排序算法

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

  • 用JavaScript实现常见的排序算法

    前戏 复习了一些比较常见的排序算法,用JS实现,带一些实现思路。 无图,无脑贴代码。。 比较排序 冒泡排序 比较相...

  • 常见排序算法JavaScript实现

    排序算法稳定性 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,...

  • 常见的排序算法(JavaScript实现)

    摘要:本文简单介绍几个常见的排序算法,包括:冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序。列出的代码...

  • 常见排序算法详解(JavaScript实现)

    1、选择排序 时间复杂度:O(n^2) 原理:通过两层循环来实现,外层遍历整个数组,内层再遍历一次数组并找到未排序...

  • 排序算法

    常见排序算法比较 参考资料:各种排序算法比较 参考资料:快速排序算法 必须知道的八大种排序算法【java实现】(一...

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

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

  • 插入排序算法实现

    排序算法是最常见,最基础的算法,作者文集中记录了两种排序算法(插入排序,归并排序) 插入排序算法实现很简单直接,附...

  • 编程算法之排序和查找算法

    查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。 一. 排序 常见...

  • 排序与搜索

    排序算法: 一种能将一串数据依照特定顺序进行排列的一种算法 常见排序算法效率的比较 排序算法的实现 1. 冒泡排序...

网友评论

    本文标题:用JavaScript实现常见的排序算法

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