springleo's blog

# 排序算法

# 1. 冒泡排序

所有排序算法中最简单的，但不实用。因为时间复杂度：O(n2)。

数组中有 n 个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。

// 从小到大冒泡排序
function bubbleSort(arr) {
    for (var i = 0; i < arr.length - 1 ; i++) { // 两两比较，所以是arr.length - 1
        for(var j = 0; j < arr.length - i - 1 ; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1)
            }
        }
    }
    return arr
}

function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

// 优化
function bubbleSort(arr) {
    var max = arr.length - 1;
    for(var i = 0; i < max; i++) {
        var done = true // 声明一个变量，作为标志位
        for (var j = 0; j < max - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j+1)
                done = false
            }
        }
        // 如果标记在某一排序中没有变动，即都正序了，可跳出循环
        if (done) {
            break
        }
    }
    return arr
}

image

# 2. 选择排序

一种原址比较排序，每次找到最小值，并放在第一位，接着找接下里的最小值，放在第二位。时间复杂度：O(n2)。

function selectionSort(arr) {
    var minIndex = 0
    for (var i = 0; i < arr.length - 1; i++) { // i作为currentIndex
        minIndex = i // 先默认currentIndex作为最小index
        for (var j = i; j < arr.length; j++) {
            // 每次筛选出最小val的下标
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
    }

    if (minIndex !== i) {
        swap(arr, i, minIndex)
    }
    return arr
}

image

# 3. 插入排序

时间复杂度：O(n2)。

将一个元素插入到其它已经有序的牌中的适当位置，因此其他所有元素在插入之前都向右移动一位，为新元素腾出空间。有点类似摸扑克牌排序。

如果对一个已经有序的数组使用插入排序，插入排序只会遍历数组一遍，时间复杂度退化为 O(n)；可以想象，如果对一个接近有序的数组使用插入排序，其效率是非常可观的，而很多时候我们处理的数据是接近有序的，只需调整一些无序项，所以插入排序是很有用的。

function insertSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var j = i
        var temp = arr[j] // 待排序值，0-（j-1）已经排好序列
        while(j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1] // j - 1的值，往后挪，给temp值留位置
            j-- // 循环继续判断
        }
        arr[j] = temp // 找到考察的数应处于的位置
    }
    return arr
}

排序小型数组时，此算法比选择排序和冒泡排序性能要好。

image

# 4. 归并排序

前三种算法性能都不好，归并排序是第一个可以被实际使用的排序算法。时间复杂度：O(nlogn)。

使用left和right两个数组存储，每次循环都减少一半（但也每次多两个变量数组），空间换时间。

从数组的中间拿一个值，然后通过这个值挨个和数组里面的值进行比较，如果大于的放一边，小于的放一边，然后把这些合并，再进行比较，如此反复即可。

function mergeSort(arr) {
    if (arr.length <= 1) return arr

    // 取中间index/value
    var index = Math.floor(arr.length / 2)
    var middle = arr.splice(index, 1)

    var left = [], right = []
    for (var i = 0; i < arr.length; i++) {
        var cur = arr[i]
        cur > middle ? right.push(cur) : left.push(cur)
    }

    // 递归调用left/right快排
    return mergeSort(left).concat(middle, mergeSort(right))
}

image

# 5. 快速排序

最常用的排序算法，时间复杂度：O(nlogn)，性能通常比其他复杂度为O(nlogn)的排序算法高。

和归并排序一样，使用分治的方法，将原始数组分为较小的数组（但没有像归并那样将他们分割开,没有占据额外的空间）。

  1. 从数组选择一项作为主元（一般有头/中间/尾三种算法选择）
  2. 划分操作：创建两个指针，分别指向头和尾，移动左指针和右指针，双方一个大于一个小于时，交换。这样在一次循环中，在主元中左边都比主元小，右边都比主元大。
  3. 重复2

# 1. 选择头作为主元：

function quickSort(arr) {
    quick(arr, 0, arr.length - 1)
}

function quick(arr, left, right) {
    if (arr.length <= 1) return
    if (left >= right) return

    // 基于主元，把合理的val左右互调，以及确定好主元的位置。
    var index = partition_By_First(arr, left, right)

    // 剩下的继续递归
    quick(arr, left, index - 1)
    quick(arr, index + 1, right)
}

let partition_By_First = function(arr, i, j) {
    let pivot = arr[i] // 取第一个作为主元
    while(i < j) {
        if (arr[i + 1] < pivot) {
            a[i] = a[i+1] // 小于，则往左边堆，i+1 后退
            i++
        } else {
            swap(arr, i + 1, j) // 大于，则跟右边互换
            j--
        }
    }
    a[i] = pivot // i即为最终的基元位置（分割点）
    return i

    // // 以上代码等价于wiki快排的以下代码：
    // let pivot = arr[i]
    // while(i < j) {
    //     while(arr[i] < pivot) {
    //         i++
    //     }
    //     while(arr[j] > pivot) {
    //         j--
    //     }

    //     if (i <= j) {
    //         swap(arr, i, j)
    //         i++
    //         j--
    //     }
    // }
    // a[i] = pivot // i即为最终的基元位置（分割点）
    // return i
}

# 2. 选择中间作为主元：

function quickSort(arr) {
    quick(arr, 0, arr.length - 1)
}

function quick(arr, left, right) {
    if (arr.length <= 1) return
    if (left >= right) return

    var index = partition_By_Middle(arr, left, right)

    // 剩下的继续递归
    quick(arr, left, index - 1)
    quick(arr, index, right)
}

function partition_By_Middle(arr, i, j) {
    var pivot = arr[Math.floor((i + j) / 2)]
    while(i < j) {
        while(arr[i] < pivot) {
            i++
        }
        while(arr[j] > pivot) {
            j--
        }

        if (i <= j) {
            swap(arr, i, j)
            i++
            j--
        }
    }
    return i // left作为和right的交汇点，返回
}

正则表达式 →