排序：冒泡排序、选择排序、快速排序

冒泡排序

冒泡排序原理

两相邻的数依次比较
若从小到大排列两两比较时前一个数比后一个数大互换位置
相互比较完一轮最大的数就会到最后面，并且不再参与比较
循环比较直到比较完成

简单冒泡排序实现

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

function bubbleSort(arr) {
    // 1. 确定外层循环次数
    for(let i = 0; i < arr.length ; i++) {
        // 2. 确定内层循环次数
        for (let j = 0; j < arr.length - i; j++) {
            // 3. 两两进行比较，如果 arr[j]大于arr[j+1]，将值互换
            if(arr[j+1] < arr[j]) {
                let flag = arr[j+1]
                arr[j+1] =  arr[j]
                arr[j] = flag
            }
        }
    }
    // 4. 返回修改后的数组
    return arr
}

console.log('冒泡排序', bubbleSort(arr))

选择排序

选择排序原理

找未排序的元素中最小的数
将最小数与起始位置互换
直到排序完成

简单选择排序实现

function checkSort(arr) {
    // 1. 定义一个数组用于接受最小值
    let result = []
    // 2. 定义一个最小索引作为中间值
    let minIndex
    // 3. 确定外层循环次数
    for (let i = 0; i < arr.length; i++) {
        // 4. 设置初始最小值为i
        minIndex = i
        // 5. 确定内层循环次数
        for (let j = i + 1; j < arr.length; j++) {
            // 6. 如果arr[j]的数值小于arr[minIndex]，将minIndex赋值为j
            if (arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }
        // 7. 一次内层循环之后得到得就是最小值，将值push到ruselt数组中
        result.push(arr[minIndex])
    }
    // 8. 返回排序好的数组
    return result
}

console.log('选择排序', checkSort(arr))

快速排序

快速排序原理

采用二分法取出中间数
将数组得每个值都与这个中间数作比较
小的放左边，大的放右边
知道数组为空
运用到了递归

简单快速排序实现

function quickSort(arr) {
    // 1. 判断数组是否为空，为空则返回空数组，不做操作
    // 如果没有则会报错Maximum call stack size exceeded即造成：超出最大调用堆栈大小。
    // 原因是，递归函数没有停止的判断
    if(arr.length == 0) {
        return []
    } 
    // 2. 取得中间值
    let middleIndex = Math.floor(arr.length / 2)
    let middleValue = arr.splice(middleIndex, 1)
    // 3. 定义较小数组和较大数组
    let lesser = []
    let bigger = []
    // 4. 遍历数组的值并与中间值作比较，分别将较大值和较小值放入较小数组和较大数组
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] < middleValue) {
            lesser.push(arr[i])
        }
        else {
            bigger.push(arr[i])
        }
    }
    // 5. 返回一个一个通过递归函数调用拼接的数组
    return quickSort(lesser).concat(middleValue, quickSort(bigger))
}

console.log('快速排序', quickSort(arr))

最后编辑于：2020.05.23 09:34:38