冒泡、插入、选择排序

冒泡排序

思路

• 冒泡排序只需要比较相邻的两个数据
• 每次冒泡都需要对比较相邻两个数据的大小，如果不满足大小关系就让它们互换位置
• 一次冒泡至少能让一个数据移到它应该在的位置，重复n次就完成了n个数据的排序

let arr = [7,10,6,3,5,2,9,4,8,1]

const Bubbling = arr => {
    let length = arr.length - 1
    //冒泡length次
    for (let i = 0; i < length; i++) {
        let bool = true //提前突出的标志位
        //循环比较（length-i）次
        for (let j = 0; j< length-i; j++) {
            //比较相邻元素的大小 前一个元素 > 后一个元素则替换位置
            if (arr[j] > arr[j+1]) {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                bool = false
            }
        }
        //当前冒泡循环中没有发生元素替换 说明当前冒泡后数据已经排序成功 提前退出
        if (bool) break
    }
}

Bubbling(arr)

优化： 当某次循环中比较完所有相邻数据后还未替换位置 说明当前排序已经完成所有通过添加一个bool标志位 符合条件时提前退出循环比较

插入排序

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素大于新元素，将该元素移到下一位置
• 重复比较后直到找到已排序的元素小于或等于新元素的位置
• 将新元素插入到该位置后 重复2～5

let arr = [7,10,6,3,5,2,9,4,8,1]

const insertionSort = arr => {
    let length = arr.length
    if (length <= 1) return

    let preIndex, current
    for (let i = 1; i < length; i++ ) {
        preIndex = i-1
        current = arr[i]
        while (preIndex >= 0 && arr[preIndex] > current ) {
            arr[preIndex + 1] = arr[preIndex]
            preIndex--;
        }
        if (preIndex + 1 != i){
            arr[preIndex + 1] = current
        }
        console.log(arr)
    }
}

insertionSort(arr)

选择排序

• 首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕

const selectionSort = arr => {
    let length = arr.length
    if (length <= 1) return

    let minIndex, temp
    for (let i = 0; i < length-1 ; i++) {
        minIndex = i
        current = arr[i]
       for (let j = i+1; j<length; j++) {
           if (arr[j] < arr[minIndex]) {
               minIndex = j
           }
       }
       temp = arr[i]
       arr[i] = arr[minIndex]
       arr[minIndex] = temp
    }
    return arr 
}

selectionSort(arr)