用JavaScript实现常见的排序算法

前端开发 简书

前戏

  • 复习了一些比较常见的排序算法,用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[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  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 randomizedQuickSort(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]  {
        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  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
}

结语

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

惯例贴链接:

简书稿源:简书 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 前端开发 » 用JavaScript实现常见的排序算法

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录