常见排序算法及动画演示js实现

[Cyrilszq]

部分动画展示在这里，源码在这，动画是直接操作DOM用CSS3实现的，每次运行时排序程序直接运行完，但会在每一步记录一个状态并将状态push进一个数组，排序完成后根据数组还原排序过程。

选择排序

比较简单，过程如下，首先找到数组最小的那个元素，将它与数组第一个元素交换，然后在剩下的元素中找到最小的元素将它与数组第二个元素交换，这样循环直至结束。其最优、平均、最差时间复杂度均为 О(n²)，几乎用不到。

function selectionSort(arr) {
    for (let i = 0, len = arr.length; i < len; i++) {
        let min = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j
            }
        }
        if (min !== i) {
            swap(arr, min, i) //交换
        }
    }
}

冒泡排序

平均时间复杂度О(n²)，最坏О(n²)，最优О(n)

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

function bubbleSort(arr) {
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j + 1, j);
            }
        }
    }
}

插入排序

与冒泡有相同的时间复杂度，不过交换次数变少，整体过程类似于整理扑克牌。

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

function insertionSorting(arr) {
    let temp,j
    for (let i = 1, len = arr.length; i < len; i++) {
        temp = arr[i]
        j = i - 1
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = temp
    }
}

快速排序

最常用的排序，平均Ο(nlogn)，最坏О(n²)，最优Ο(nlogn)，但快速排序通常明显比其他Ο(nlogn)算法更快

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

// 原地快排
function quickSort(arr, left = 0, len = arr.length) {
    let pivot
    if (left < len) {
        pivot = patition(arr, left, len)
        quickSort(arr, left, pivot - 1)
        quickSort(arr, pivot, len)
    }
    function patition(arr, left = 0, len = arr.length) {
        let pivot = left
        for (let right = left + 1; right < len; right++) {
            if (arr[pivot] >= arr[right]) {
                left++
                swap(arr, left, right)
            }
        }
        swap(arr, left, pivot)
        return left + 1
    }
}

// js版实现
function quickSort(arr){
  if (arr.length <= 1)  return arr
　　let pivotIndex = Math.floor(arr.length / 2)
　　let pivot = arr.splice(pivotIndex, 1)[0]
　　let left = []
　　let right = []
　　for (let i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i])
　　　　} else {
　　　　　　right.push(arr[i])
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right))
}

归并排序

所有情况均为Ο(nlogn)，主要策略是分治。

1. 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

// 递归版
function mergeSort(arr) {
    function merge(left, right) {
        let result = []
        while (left.length && right.length) {
            result.push(left[0] <= right[0] ? left.shift() : right.shift())
        }
        return result.concat(left.concat(right))
    }

    let len = arr.length, mid = parseInt(len / 2)
    if (len < 2) return arr
    return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

堆排序

时间复杂度所有情况均为Ο(nlogn)

function heapSort(arr) {
    let len = arr.length

    function maxHeapify(start, end) {
        let dad = start, son = dad * 2 + 1
        if (son >= end) return
        if (son + 1 < end && arr[son] < arr[son + 1]) // 比较两个子节点大小，选择较大的
            son++
        if (arr[dad] <= arr[son]) {
            swap(arr, dad, son)
            maxHeapify(son, end) // 递归调整
        }
    }

    // 创建最大堆，从最后一个父节点来时调整
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        maxHeapify(i, len);
    }
    // 堆排序
    for (let i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        maxHeapify(0, i);
    }
}

小结

虽然实际开发中排序这项工作基本不要自己手写，因为大部分语言都有现成的接口可以使用比如js的Array.prototype.sort()，它是用快排实现的并做了一些优化，但是其中有些思想还是值得借鉴的，比如快排中的patition，可能在其他算法问题中有所运用。