排序(冒泡,插入,选择)

八大经典排序:
冒泡排序插入排序选择排序归并排序快速排序计数排序基数排序桶排序

冒泡插入选择 O(n²) 基于比较
快排归并 O(nlogn) 基于比较
计数基数桶 O(n) 不基于比较

如何评价一个排序算法的优劣

排序算法的 执行效率 指时间复杂度,比较次数,移动次数
排序算法的 内存消耗 指空间复杂度
排序算法的 稳定性 指排序后序列中相等元素的原有先后顺序不变

原地排序(Sorted in place),特指空间复杂度为O(1)的排序算法
排序后相等元素顺序不变,称为稳定的排序算法,相反称为不稳定的排序算法

稳定的排序算法 的优势

真实的软件开发中,进行排序的不是单纯的整数,而是一组对象,依赖某个key进行排序.

假设某个订单系统中,存在下单时间订单金额两个属性,
我们希望按金额从小到大进行排序,金额相同的订单按下单时间从早到晚排序,

则先按 下单时间(注意是先时间) 进行排序,之后再用 稳定排序算法 按订单金额排序
稳定排序算法可以保证金额相同的两个对象在排序之后前后顺序不变

冒泡排序(Bubble Sort)

冒泡排序进行多轮,
每一轮从头到尾对相邻两个数进行比较,看是否满足大小关系要求
如果不满足则交换两个数的位置,
每一轮的最终结果会使得一个数 ‘冒泡’,位于正确的位置,进行n轮

// 冒泡排序
const bubbleSort = (arr) => {
    if (arr.length <= 1) return
    for (let i = 0; i < arr.length; i++) {
        let hasChange = false
        // 每次冒泡最末尾的数已经位于正确的位置,后续不需要参与比较所以-i
        for (let j = 0; j < arr.length - i - 1; j++) {
            // 从小到大进行排序
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                hasChange = true
            }
        }
        // 如果某次冒泡没进行任何交换 说明所有元素已经到位
        if (!hasChange) break
    }
    console.log(arr)
}
const test = [4, 5, 6, 3, 2, 1]
bubbleSort(test)

冒泡排序空间复杂度为 O(1),是 原地排序算法,
相邻元素大小相等时不会进行交换是 稳定的排序算法,
时间复杂度为 O(n²)

最好情况全为顺序只要一轮冒泡(只需检查一轮),时间复杂度 O(n)
最好情况全为逆序需要n轮冒泡(需检查n轮),时间复杂度 O(n²)

有序度 和 逆序度:
有序度是数组中具有有序关系的元素对的个数
如:2,4,3,1,5,6,有序度为 11(一个个从前往后找,如24,23,25,26都是有序对,再找4*,3*,1*)

对于1,2,3,4,5,6 这种叫 满有序度,

还可以得出 逆序度 = 满有序度 - 有序度

n位数组满有序度为 n*(n-1)/2
(如上例123456,1往后可找5对,2找4对,最后得5+4+3+2+1满序度)

冒泡排序中每一个逆序度都代表一次交换

最坏情况下有序度为0,逆序度为n*(n-1)/2,最好情况下相反,平均交换n*(n-1)/4次
所以复杂度为 O(n²)

插入排序(Insertion Sort)

插入排序将数据分为两个区间,已排序区间 和 未排序区间,
初始已排序区间就是第一个元素,
每轮取未排序区间的元素,在已排序区间中找合适的位置插入,
直到未排序区间为空

// 插入排序
const insertionSort = (arr) => {
    if (arr.length <= 1) return
    // (0,i) 代表有序区间 i代表无序区间这轮即将要插入有序区间的数
    for (let i = 1; i < arr.length; i++) {
        const temp = arr[i]
        let j = i - 1
        // j 属于 [0,i-1],从后向前比较,比temp大的就后移
        for (j; j >= 0; j--) {
            if (arr[j] > temp) {
                arr[j + 1] = arr[j]
            } else {
                break
            }
        }
        // 直到 找到第一个<j或=j的数下标 或循环完j=-1,
        // temp放这个数后面(j+1)
        arr[j + 1] = temp
    }
    console.log(arr)
}
const testSort = [4, 1, 6, 3, 2, 1]
insertionSort(testSort)

插入排序空间复杂度为 O(1),是 原地排序算法,
发现值相同的元素时插入是 稳定的排序算法,
时间复杂度为 O(n²) (n轮,每轮移动n个数)

最好情况时间复杂度为O(n)

选择排序

也区分 已排序区间 和 未排序区间,
每轮找到未排序区间最小的数,与已排序区间的末尾的数交换,

// 选择排序
const selectionSort = (arr) => {
    if (arr.length <= 1) return
    // 需要注意这里的边界, 因为需要在内层进行 i+1后的循环，所以外层需要 数组长度-1
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j // 找到整个数组的最小值
            }
        }
        const temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    console.log(arr)
}
const testSelect = [4, 8, 6, 3, 2, 1, 0, 12]
selectionSort(testSelect)

插入排序空间复杂度为 O(1),是 原地排序算法,
是 不!稳定的排序算法,
任何情况时间复杂度为 O(n²)

选择排序好理解,但是相比上面两个,略显逊色

总结

冒泡、插入、选择排序都有一个共同点，将待排序数列分为已排序和未排序两部分。
在未排序的部分中查找一个最值，放到已排序数列的恰当位置。

具体到代码层面，外层循环的变量用于分割已排序和未排序数，
内层循环的变量用于在未排序数中查找。
从思路上看，这三种算法其实是一样的，所以时间复杂度也相同

冒泡排序不管怎么优化元素交换次数都是元素数据的逆序度
插入排序不管怎么优化元素移动次数都是元素数据的逆序度

但是插入排序更受欢迎,因为:

// 冒泡排序的交换操作
if (arr[j] > arr[j + 1]) {
    // ---每次交换三次赋值---
    const temp = arr[j]
    arr[j] = arr[j + 1]
    arr[j + 1] = temp
    hasChange = true
}

// 插入排序的移动操作
if (arr[j] > temp) {
    // ---每次移动一次赋值---
    arr[j + 1] = arr[j]
} else {
    break
}