七种常见排序算法的JS实现

1.冒泡排序

// 交换函数
function swap(arr, i, j) {
    var temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    return arr
}

// 1.冒泡排序
function bubbleSort(nums) {
    let len = nums.length
    if (len == 0 || len == 1) return nums
    // 从 len-1 遍历到 1 的位置
    for (let i = len - 1; i > 0; i--) {
        // j从 0 遍历到 i-1 的位置
        for (let j = 0; j < i; j++) {
            // 和 j+1 的元素进行比较
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1)
            }
        }
    }
    return nums
}
复制代码

2.选择排序

// 2.选择排序：选择未排序元素中的最小值和当前位（从左往右遍历）元素进行交换
function selectSort(nums) {
    var len = nums.length
    if (len == 0 || len == 1) return nums
    // 从左到右遍历每一个位置（最后一个不用）
    var curPosition = 0
    for (let i = 0; i < len - 1; i++) {
        // 选出从当前位置到最后一个元素中最小的元素并记录其索引index
        var min = nums[i]
        var index = i
        for (let j = i + 1; j < len; j++) {
            if (nums[j] < min) {
                min = nums[j]
                index = j
            }
        }
        // 交换当前位置元素和最小值所在的位置
        swap(nums, i, index)
    }
    return nums
}
复制代码

3.插入排序

// 3.插入排序：从左到右遍历每个位置，将当前位置元素插入到前面已排序数组的合适位置
function insertSort(nums) {
    let len = nums.length
    if (len == 0 || len == 1) return nums
    // 从左到右遍历每一个位置（第一个可以除外）
    for (let i = 1; i < len; i++) {
        // 和前面已经排好序的元素比较
        let j = i - 1
        while (j >= 0) {
            if (nums[j + 1] < nums[j]) {
                swap(nums, j, j + 1)
                j--
            } else break // 否则就退出循环
        }
    }
    return nums
}
复制代码

4.希尔排序

// 4.希尔排序：根据增量进行分组插入排序（多个增量需互质，且最后一个为1）
function shellSort(nums) {
    var len = nums.length
    if (len == 0 || len == 1) return nums
    var gap = parseInt(len / 2) // 设置增量（步长）的初始值
    while (gap) { // nlogn 次
        // 循环 步长 次
        for (let n = 0; n < gap; n++) {
            var num = Math.ceil(len / gap) // 定义组数
            // 对间隔步长的元素进行插入排序
            // 从左到右遍历每一个位置（第一个可以除外）
            for (let i = gap; i < num + gap; i++) {
                if (i < len) { // 最后一组可能不是gap个
                    // 和前面已经排好序的元素比较
                    var j = i - gap
                    while (j >= n) {
                        if (nums[j + gap] < nums[j]) {
                            swap(nums, j, j + gap)
                            j -= gap
                        } else break
                    }
                }
            }
        }
        gap = parseInt(gap / 2)
    }
    return nums
}
复制代码

5.归并排序

// 5.归并排序：分治
function mergeSort(nums) {
    var len = nums.length
    if (len < 2) return nums
    var mid = Math.floor(len / 2)
    var left = nums.slice(0, mid) // 包括 begin，不包括end
    var right = nums.slice(mid) // 如果 end 被省略，则 slice 会一直提取到原数组末尾
    return merge(mergeSort(left), mergeSort(right))
}
// 归并两个有序数组
function merge(left, right) {
    var newArr = []
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            newArr.push(left.shift())
        } else newArr.push(right.shift())
    }
    return newArr.concat(left).concat(right)
}
复制代码

6.快速排序

// 6.快速排序：分治、双指针；设置最左元素为基准点，右指针先动 // 内存不足
function quickSort(nums) {
    var len = nums.length
    if (len == 0 || len == 1) return nums
    var piovt = nums[0] // 设置基准点的值为nums[0]
    var left = 0 // 设置左指针
    var right = len - 1 // 设置右指针
    while (left < right) {
        // 右指针先动，找到比基准点小的元素
        if (nums[right] < piovt) {
            // 再动左指针，找到比基准点大的元素
            if (nums[left] > piovt) {
                // 进行交换
                swap(nums, left, right)
            } else left++
        } else right--
    }
    if (left == right) {
        swap(nums, 0, left)
    }
    // 拼接字符串：对当前基准点元素的左边排序 + 基准点元素 + 对当前基准点元素的右边排序
    return quickSort(nums.slice(0, left)).concat(nums[left]).concat(quickSort(nums.slice(left + 1)))
}
复制代码

7.堆排序

// 7.堆排序：
function heapSort(nums) {
    var len = nums.length
    if (len < 2) return nums
    for (let i = len - 1; i >= 0; i--) {
        // 1.将未排序部分的nums[0-i]调整为最大堆
        nums = adjustMaxHeap(nums, 0, i)
        // 2.交换堆顶和数组最后一个元素
        nums = swap(nums, 0, i)
    }
    return nums
}
// 构建最大堆
function adjustMaxHeap(nums, start, end) { // 为了不浪费新的内存空间，新增end参数，保证后面已经排好的元素可以保留
    var left = 2 * start + 1 // 左节点
    var right = 2 * start + 2 // 右节点
    // 如果当前节点是不是根节点
    if (left > end) return nums
    // 如果当前节点是根节点，调整他的左右子节点为最大堆
    adjustMaxHeap(nums, left, end)
    right <= end && adjustMaxHeap(nums, right, end)

    // 先和左节点比较
    if (nums[start] < nums[left]) {
        swap(nums, start, left)
    }
    // 如果有右节点还需要和右节点进行比较
    if (right <= end && nums[start] < nums[right]) {
        swap(nums, start, right)
    }
    return nums
}
复制代码