★ 数组排序

let arr = [3, 2, 4, 5, 1]

sort 方法实现

arr.sort((x, y) => {
    return x - y
})
console.log(arr)

冒泡排序 时间复杂度O(n2)

  • 冒泡排序(Bubble Sort)是最易懂的排序算法,但是效率较低,生产环境中很少使用。
  • 它的基本思想是,依次比较相邻的两个数,如果不符合排序规则,则调换两个数的位置。这样一遍比较下来,能够保证最大(或最小)的数排在最后一位。然后,再对最后一位以外的数组,重复前面的过程,直至全部排序完成。由于每进行一遍这个过程,在最后一个位置上,正确的数会自己冒出来,就好像“冒泡”一样,这种算法因此得名。
  • 以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
    1.第一位的“3”与第二位的“2”进行比较,3大于2,所以互换位置,数组变成[2, 3, 4, 5, 1] 。
    2.第二位的“3”与第三位的“4”进行比较,3小于4,数组不变。
    3.第三位的“4”与第四位的“5”进行比较,4小于5,数组不变。
    4.第四位的“5”与第五位的“1”进行比较,5大于1,所以互换位置,数组变成[2, 3, 4, 1, 5] 。
  • 第一轮排序完成,可以看到最后一位上的5,已经是正确的数了。然后,再对剩下的数[2, 3, 4, 1] 重复这个过程,每一轮都会在本轮最后一位上出现正确的数。直至剩下最后一个位置,所有排序结束。
// 冒泡排序
function bubble(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        console.log(`第 ${i} 次循环`)
        for(let j = 0; j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                let temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
            console.log(arr)
        }
    }
    return arr
}

选择排序

  • 选择排序(Selection Sort)与冒泡排序类似,也是依次对相邻的数进行两两比较。不同之处在于,它不是每比较一次就调换位置,而是一轮比较完毕,找到最大值(或最小值)之后,将其放在正确的位置,其他数的位置不变。
  • 以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
    1.假定第一位的“3”是最小值。
    2.最小值“3”与第二位的“2”进行比较,2小于3,所以新的最小值是第二位的“2”。
    3.最小值“2”与第三位的“4”进行比较,2小于4,最小值不变。
    4.最小值“2”与第四位的“5”进行比较,2小于5,最小值不变。
    5.最小值“2”与第五位的“1”进行比较,1大于2,所以新的最小值是第五位的“1”。
    6.第五位的“1”与第一位的“3”互换位置,数组变为[1, 2, 4, 5, 3]。
  • 这一轮比较结束后,最小值“1”已经排到正确的位置了,然后对剩下的[2, 4, 5, 3]重复上面的过程。每一轮排序都会将该轮的最小值排到正确的位置,直至剩下最后一个位置,所有排序结束。
// 选择排序
function selectionSort(arr) {
    for(let i = 0; i < arr.length; i++) {
        let minIndex = i
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        if(i != minIndex) {
            let trans = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = trans
        console.log(arr, '------------')
        }
    }
    return arr
}

插入排序

  • 插入排序(insert sort)比前面两种排序方法都更有效率。它将数组分成“已排序”和“未排序”两部分,一开始的时候,“已排序”的部分只有一个元素,然后将它后面一个元素从“未排序”部分插入“已排序”部分,从而“已排序”部分增加一个元素,“未排序”部分减少一个元素。以此类推,完成全部排序。


    插入排序
  • 以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
    1.将数组分成[3]和[2, 4, 5, 1]两部分,前者是已排序的,后者是未排序的。
    2.取出未排序部分的第一个元素“2”,与已排序部分最后一个元素“3”比较,因为2小于3,所以2排在3前面,整个数组变成[2, 3]和[4, 5, 1]两部分。
    3.取出未排序部分的第一个元素“4”,与已排序部分最后一个元素“3”比较,因为4大于3,所以4排在3后面,整个数组变成[2, 3, 4]和[5, 1]两部分。
    4.取出未排序部分的第一个元素“5”,与已排序部分最后一个元素“4”比较,因为5大于4,所以4排在5后面,整个数组变成[2, 3, 4, 5]和[1]两部分。
    5.取出未排序部分的第一个元素“1”,与已排序部分最后一个元素“5”比较,因为1小于5,所以再与前一个元素“4”比较;因为1小于4,再与前一个元素“3”比较;因为1小于3,再与前一个元素“2”比较;因为小于1小于2,所以“1”排在2的前面,整个数组变成[1, 2, 3, 4, 5]。
const insertSort = (arr) => {
    // 从第二项开始向前比较
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] < arr[i - 1]) {
            // 如果它小于前一项 则首先保存一下值
            let current = arr[I]
            // 定义一下前一项的 index
            let j = i - 1
            // 循环向前判断并把值依次后移
            while(j >=0 && current < arr[j]) {
                arr[j + 1] = arr[j]
                j--
            }
            // 直到找到小于它的前一项停止并把当前项复制给 j +1
            arr[j + 1] = current
        }
    }
    return arr
}

快速排序

  • 快速排序(quick sort)是公认最快的排序算法之一,有着广泛的应用。
  • 它的基本思想很简单:先确定一个“支点”(pivot),将所有小于“支点”的值都放在该点的左侧,大于“支点”的值都放在该点的右侧,然后对左右两侧不断重复这个过程,直到所有排序完成。
    1.找基准(一般是以中间项为基准)
    2.遍历数组,小于基准的放在left,大于基准的放在right
    3.递归
const quickSort = (arr) => {
    // 判断 arr 只有一个元素直接返回
    if(arr.length <= 1) return arr

    // 找到中间 index 和 element 
    let midIndex = Math.floor(arr.length / 2)
    let midEle = arr.splice(midIndex, 1)[0]

    // 定义 left 和 right 循环 arr 对比 midEle 小的放左边大的放右边
    let leftArr = []
    let rightArr = []

    for(let i = 0; i < arr.length; i++) {
        if(arr[i] <= midEle) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }

    // 递归上述步骤
    return quickSort(leftArr).concat(midEle, quickSort(rightArr))
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容